swrdcl - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > swrdcl		Structured version Visualization version GIF version

Theorem swrdcl 14679

Description: Closure of the subword extractor. (Contributed by Stefan O'Rear, 16-Aug-2015.) (Revised by Mario Carneiro, 26-Feb-2016.)

**Assertion**
Ref	Expression
swrdcl	⊢ (𝑆 ∈ Word 𝐴 → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)

Proof of Theorem swrdcl Dummy variables 𝑠 𝑏 𝑥 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		eleq1 2826	. 2 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) = ∅ → ((𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴 ↔ ∅ ∈ Word 𝐴))
2		n0 4358	. . . 4 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) ≠ ∅ ↔ ∃𝑥 𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩))
3		df-substr 14675	. . . . . . 7 ⊢ substr = (𝑠 ∈ V, 𝑏 ∈ (ℤ × ℤ) ↦ if(((1^st ‘𝑏)..^(2^nd ‘𝑏)) ⊆ dom 𝑠, (𝑥 ∈ (0..^((2^nd ‘𝑏) − (1^st ‘𝑏))) ↦ (𝑠‘(𝑥 + (1^st ‘𝑏)))), ∅))
4	3	elmpocl2 7675	. . . . . 6 ⊢ (𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → ⟨𝐹, 𝐿⟩ ∈ (ℤ × ℤ))
5		opelxp 5724	. . . . . 6 ⊢ (⟨𝐹, 𝐿⟩ ∈ (ℤ × ℤ) ↔ (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
6	4, 5	sylib 218	. . . . 5 ⊢ (𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
7	6	exlimiv 1927	. . . 4 ⊢ (∃𝑥 𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
8	2, 7	sylbi 217	. . 3 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) ≠ ∅ → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
9		swrdval 14677	. . . . 5 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → (𝑆 substr ⟨𝐹, 𝐿⟩) = if((𝐹..^𝐿) ⊆ dom 𝑆, (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))), ∅))
10		wrdf 14553	. . . . . . . . . . 11 ⊢ (𝑆 ∈ Word 𝐴 → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
11	10	3ad2ant1 1132	. . . . . . . . . 10 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
12	11	ad2antrr 726	. . . . . . . . 9 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
13		simplr 769	. . . . . . . . . . 11 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝐹..^𝐿) ⊆ dom 𝑆)
14		simpr 484	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝑥 ∈ (0..^(𝐿 − 𝐹)))
15		simpll3 1213	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝐿 ∈ ℤ)
16		simpll2 1212	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝐹 ∈ ℤ)
17		fzoaddel2 13755	. . . . . . . . . . . 12 ⊢ ((𝑥 ∈ (0..^(𝐿 − 𝐹)) ∧ 𝐿 ∈ ℤ ∧ 𝐹 ∈ ℤ) → (𝑥 + 𝐹) ∈ (𝐹..^𝐿))
18	14, 15, 16, 17	syl3anc 1370	. . . . . . . . . . 11 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ (𝐹..^𝐿))
19	13, 18	sseldd 3995	. . . . . . . . . 10 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ dom 𝑆)
20	12	fdmd 6746	. . . . . . . . . 10 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → dom 𝑆 = (0..^(♯‘𝑆)))
21	19, 20	eleqtrd 2840	. . . . . . . . 9 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ (0..^(♯‘𝑆)))
22	12, 21	ffvelcdmd 7104	. . . . . . . 8 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑆‘(𝑥 + 𝐹)) ∈ 𝐴)
23	22	fmpttd 7134	. . . . . . 7 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))):(0..^(𝐿 − 𝐹))⟶𝐴)
24		iswrdi 14552	. . . . . . 7 ⊢ ((𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))):(0..^(𝐿 − 𝐹))⟶𝐴 → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))) ∈ Word 𝐴)
25	23, 24	syl 17	. . . . . 6 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))) ∈ Word 𝐴)
26		wrd0 14573	. . . . . . 7 ⊢ ∅ ∈ Word 𝐴
27	26	a1i 11	. . . . . 6 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ ¬ (𝐹..^𝐿) ⊆ dom 𝑆) → ∅ ∈ Word 𝐴)
28	25, 27	ifclda 4565	. . . . 5 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → if((𝐹..^𝐿) ⊆ dom 𝑆, (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))), ∅) ∈ Word 𝐴)
29	9, 28	eqeltrd 2838	. . . 4 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)
30	29	3expb 1119	. . 3 ⊢ ((𝑆 ∈ Word 𝐴 ∧ (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ)) → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)
31	8, 30	sylan2 593	. 2 ⊢ ((𝑆 ∈ Word 𝐴 ∧ (𝑆 substr ⟨𝐹, 𝐿⟩) ≠ ∅) → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)
32	26	a1i 11	. 2 ⊢ (𝑆 ∈ Word 𝐴 → ∅ ∈ Word 𝐴)
33	1, 31, 32	pm2.61ne 3024	1 ⊢ (𝑆 ∈ Word 𝐴 → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ∧ wa 395 ∧ w3a 1086 ∃wex 1775 ∈ wcel 2105 ≠ wne 2937 Vcvv 3477 ⊆ wss 3962 ∅c0 4338 ifcif 4530 ⟨cop 4636 ↦ cmpt 5230 × cxp 5686 dom cdm 5688 ⟶wf 6558 ‘cfv 6562 (class class class)co 7430 1^st c1st 8010 2^nd c2nd 8011 0cc0 11152 + caddc 11155 − cmin 11489 ℤcz 12610 ..^cfzo 13690 ♯chash 14365 Word cword 14548 substr csubstr 14674

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1791 ax-4 1805 ax-5 1907 ax-6 1964 ax-7 2004 ax-8 2107 ax-9 2115 ax-10 2138 ax-11 2154 ax-12 2174 ax-ext 2705 ax-rep 5284 ax-sep 5301 ax-nul 5311 ax-pow 5370 ax-pr 5437 ax-un 7753 ax-cnex 11208 ax-resscn 11209 ax-1cn 11210 ax-icn 11211 ax-addcl 11212 ax-addrcl 11213 ax-mulcl 11214 ax-mulrcl 11215 ax-mulcom 11216 ax-addass 11217 ax-mulass 11218 ax-distr 11219 ax-i2m1 11220 ax-1ne0 11221 ax-1rid 11222 ax-rnegex 11223 ax-rrecex 11224 ax-cnre 11225 ax-pre-lttri 11226 ax-pre-lttrn 11227 ax-pre-ltadd 11228 ax-pre-mulgt0 11229

This theorem depends on definitions: df-bi 207 df-an 396 df-or 848 df-3or 1087 df-3an 1088 df-tru 1539 df-fal 1549 df-ex 1776 df-nf 1780 df-sb 2062 df-mo 2537 df-eu 2566 df-clab 2712 df-cleq 2726 df-clel 2813 df-nfc 2889 df-ne 2938 df-nel 3044 df-ral 3059 df-rex 3068 df-reu 3378 df-rab 3433 df-v 3479 df-sbc 3791 df-csb 3908 df-dif 3965 df-un 3967 df-in 3969 df-ss 3979 df-pss 3982 df-nul 4339 df-if 4531 df-pw 4606 df-sn 4631 df-pr 4633 df-op 4637 df-uni 4912 df-int 4951 df-iun 4997 df-br 5148 df-opab 5210 df-mpt 5231 df-tr 5265 df-id 5582 df-eprel 5588 df-po 5596 df-so 5597 df-fr 5640 df-we 5642 df-xp 5694 df-rel 5695 df-cnv 5696 df-co 5697 df-dm 5698 df-rn 5699 df-res 5700 df-ima 5701 df-pred 6322 df-ord 6388 df-on 6389 df-lim 6390 df-suc 6391 df-iota 6515 df-fun 6564 df-fn 6565 df-f 6566 df-f1 6567 df-fo 6568 df-f1o 6569 df-fv 6570 df-riota 7387 df-ov 7433 df-oprab 7434 df-mpo 7435 df-om 7887 df-1st 8012 df-2nd 8013 df-frecs 8304 df-wrecs 8335 df-recs 8409 df-rdg 8448 df-1o 8504 df-er 8743 df-en 8984 df-dom 8985 df-sdom 8986 df-fin 8987 df-card 9976 df-pnf 11294 df-mnf 11295 df-xr 11296 df-ltxr 11297 df-le 11298 df-sub 11491 df-neg 11492 df-nn 12264 df-n0 12524 df-z 12611 df-uz 12876 df-fz 13544 df-fzo 13691 df-hash 14366 df-word 14549 df-substr 14675

This theorem is referenced by: swrdf 14684 swrdspsleq 14699 swrds1 14700 ccatswrd 14702 swrdccat2 14703 pfxcl 14711 ccatpfx 14735 swrdswrd 14739 lenrevpfxcctswrd 14746 pfxccatin12 14767 swrdccat 14769 swrdccat3blem 14773 splcl 14786 spllen 14788 splfv1 14789 splfv2a 14790 splval2 14791 cshwcl 14832 cshwlen 14833 cshwidxmod 14837 gsumspl 18869 psgnunilem2 19527 efgredleme 19775 efgredlemc 19777 efgcpbllemb 19787 frgpuplem 19804 wrdsplex 32904 splfv3 32927 gsumwrd2dccatlem 33051 gsumwrd2dccat 33052 cycpmco2f1 33126 cycpmco2rn 33127 cycpmco2lem2 33129 cycpmco2lem3 33130 cycpmco2lem4 33131 cycpmco2lem5 33132 cycpmco2lem6 33133 cycpmco2 33135 elrgspnlem2 33232 revpfxsfxrev 35099

W3C validator