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 14627

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 2817	. 2 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) = ∅ → ((𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴 ↔ ∅ ∈ Word 𝐴))
2		n0 4347	. . . 4 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) ≠ ∅ ↔ ∃𝑥 𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩))
3		df-substr 14623	. . . . . . 7 ⊢ substr = (𝑠 ∈ V, 𝑏 ∈ (ℤ × ℤ) ↦ if(((1^st ‘𝑏)..^(2^nd ‘𝑏)) ⊆ dom 𝑠, (𝑥 ∈ (0..^((2^nd ‘𝑏) − (1^st ‘𝑏))) ↦ (𝑠‘(𝑥 + (1^st ‘𝑏)))), ∅))
4	3	elmpocl2 7664	. . . . . 6 ⊢ (𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → ⟨𝐹, 𝐿⟩ ∈ (ℤ × ℤ))
5		opelxp 5714	. . . . . 6 ⊢ (⟨𝐹, 𝐿⟩ ∈ (ℤ × ℤ) ↔ (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
6	4, 5	sylib 217	. . . . 5 ⊢ (𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
7	6	exlimiv 1926	. . . 4 ⊢ (∃𝑥 𝑥 ∈ (𝑆 substr ⟨𝐹, 𝐿⟩) → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
8	2, 7	sylbi 216	. . 3 ⊢ ((𝑆 substr ⟨𝐹, 𝐿⟩) ≠ ∅ → (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ))
9		swrdval 14625	. . . . 5 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → (𝑆 substr ⟨𝐹, 𝐿⟩) = if((𝐹..^𝐿) ⊆ dom 𝑆, (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))), ∅))
10		wrdf 14501	. . . . . . . . . . 11 ⊢ (𝑆 ∈ Word 𝐴 → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
11	10	3ad2ant1 1131	. . . . . . . . . 10 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
12	11	ad2antrr 725	. . . . . . . . 9 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝑆:(0..^(♯‘𝑆))⟶𝐴)
13		simplr 768	. . . . . . . . . . 11 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝐹..^𝐿) ⊆ dom 𝑆)
14		simpr 484	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝑥 ∈ (0..^(𝐿 − 𝐹)))
15		simpll3 1212	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝐿 ∈ ℤ)
16		simpll2 1211	. . . . . . . . . . . 12 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → 𝐹 ∈ ℤ)
17		fzoaddel2 13720	. . . . . . . . . . . 12 ⊢ ((𝑥 ∈ (0..^(𝐿 − 𝐹)) ∧ 𝐿 ∈ ℤ ∧ 𝐹 ∈ ℤ) → (𝑥 + 𝐹) ∈ (𝐹..^𝐿))
18	14, 15, 16, 17	syl3anc 1369	. . . . . . . . . . 11 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ (𝐹..^𝐿))
19	13, 18	sseldd 3981	. . . . . . . . . 10 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ dom 𝑆)
20	12	fdmd 6733	. . . . . . . . . 10 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → dom 𝑆 = (0..^(♯‘𝑆)))
21	19, 20	eleqtrd 2831	. . . . . . . . 9 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑥 + 𝐹) ∈ (0..^(♯‘𝑆)))
22	12, 21	ffvelcdmd 7095	. . . . . . . 8 ⊢ ((((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) ∧ 𝑥 ∈ (0..^(𝐿 − 𝐹))) → (𝑆‘(𝑥 + 𝐹)) ∈ 𝐴)
23	22	fmpttd 7125	. . . . . . 7 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))):(0..^(𝐿 − 𝐹))⟶𝐴)
24		iswrdi 14500	. . . . . . 7 ⊢ ((𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))):(0..^(𝐿 − 𝐹))⟶𝐴 → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))) ∈ Word 𝐴)
25	23, 24	syl 17	. . . . . 6 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ (𝐹..^𝐿) ⊆ dom 𝑆) → (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))) ∈ Word 𝐴)
26		wrd0 14521	. . . . . . 7 ⊢ ∅ ∈ Word 𝐴
27	26	a1i 11	. . . . . 6 ⊢ (((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) ∧ ¬ (𝐹..^𝐿) ⊆ dom 𝑆) → ∅ ∈ Word 𝐴)
28	25, 27	ifclda 4564	. . . . 5 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → if((𝐹..^𝐿) ⊆ dom 𝑆, (𝑥 ∈ (0..^(𝐿 − 𝐹)) ↦ (𝑆‘(𝑥 + 𝐹))), ∅) ∈ Word 𝐴)
29	9, 28	eqeltrd 2829	. . . 4 ⊢ ((𝑆 ∈ Word 𝐴 ∧ 𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ) → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)
30	29	3expb 1118	. . 3 ⊢ ((𝑆 ∈ Word 𝐴 ∧ (𝐹 ∈ ℤ ∧ 𝐿 ∈ ℤ)) → (𝑆 substr ⟨𝐹, 𝐿⟩) ∈ Word 𝐴)
31	8, 30	sylan2 592	. 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 1085 ∃wex 1774 ∈ wcel 2099 ≠ wne 2937 Vcvv 3471 ⊆ wss 3947 ∅c0 4323 ifcif 4529 ⟨cop 4635 ↦ cmpt 5231 × cxp 5676 dom cdm 5678 ⟶wf 6544 ‘cfv 6548 (class class class)co 7420 1^st c1st 7991 2^nd c2nd 7992 0cc0 11138 + caddc 11141 − cmin 11474 ℤcz 12588 ..^cfzo 13659 ♯chash 14321 Word cword 14496 substr csubstr 14622

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1790 ax-4 1804 ax-5 1906 ax-6 1964 ax-7 2004 ax-8 2101 ax-9 2109 ax-10 2130 ax-11 2147 ax-12 2167 ax-ext 2699 ax-rep 5285 ax-sep 5299 ax-nul 5306 ax-pow 5365 ax-pr 5429 ax-un 7740 ax-cnex 11194 ax-resscn 11195 ax-1cn 11196 ax-icn 11197 ax-addcl 11198 ax-addrcl 11199 ax-mulcl 11200 ax-mulrcl 11201 ax-mulcom 11202 ax-addass 11203 ax-mulass 11204 ax-distr 11205 ax-i2m1 11206 ax-1ne0 11207 ax-1rid 11208 ax-rnegex 11209 ax-rrecex 11210 ax-cnre 11211 ax-pre-lttri 11212 ax-pre-lttrn 11213 ax-pre-ltadd 11214 ax-pre-mulgt0 11215

This theorem depends on definitions: df-bi 206 df-an 396 df-or 847 df-3or 1086 df-3an 1087 df-tru 1537 df-fal 1547 df-ex 1775 df-nf 1779 df-sb 2061 df-mo 2530 df-eu 2559 df-clab 2706 df-cleq 2720 df-clel 2806 df-nfc 2881 df-ne 2938 df-nel 3044 df-ral 3059 df-rex 3068 df-reu 3374 df-rab 3430 df-v 3473 df-sbc 3777 df-csb 3893 df-dif 3950 df-un 3952 df-in 3954 df-ss 3964 df-pss 3966 df-nul 4324 df-if 4530 df-pw 4605 df-sn 4630 df-pr 4632 df-op 4636 df-uni 4909 df-int 4950 df-iun 4998 df-br 5149 df-opab 5211 df-mpt 5232 df-tr 5266 df-id 5576 df-eprel 5582 df-po 5590 df-so 5591 df-fr 5633 df-we 5635 df-xp 5684 df-rel 5685 df-cnv 5686 df-co 5687 df-dm 5688 df-rn 5689 df-res 5690 df-ima 5691 df-pred 6305 df-ord 6372 df-on 6373 df-lim 6374 df-suc 6375 df-iota 6500 df-fun 6550 df-fn 6551 df-f 6552 df-f1 6553 df-fo 6554 df-f1o 6555 df-fv 6556 df-riota 7376 df-ov 7423 df-oprab 7424 df-mpo 7425 df-om 7871 df-1st 7993 df-2nd 7994 df-frecs 8286 df-wrecs 8317 df-recs 8391 df-rdg 8430 df-1o 8486 df-er 8724 df-en 8964 df-dom 8965 df-sdom 8966 df-fin 8967 df-card 9962 df-pnf 11280 df-mnf 11281 df-xr 11282 df-ltxr 11283 df-le 11284 df-sub 11476 df-neg 11477 df-nn 12243 df-n0 12503 df-z 12589 df-uz 12853 df-fz 13517 df-fzo 13660 df-hash 14322 df-word 14497 df-substr 14623

This theorem is referenced by: swrdf 14632 swrdspsleq 14647 swrds1 14648 ccatswrd 14650 swrdccat2 14651 pfxcl 14659 ccatpfx 14683 swrdswrd 14687 lenrevpfxcctswrd 14694 pfxccatin12 14715 swrdccat 14717 swrdccat3blem 14721 splcl 14734 spllen 14736 splfv1 14737 splfv2a 14738 splval2 14739 cshwcl 14780 cshwlen 14781 cshwidxmod 14785 gsumspl 18795 psgnunilem2 19449 efgredleme 19697 efgredlemc 19699 efgcpbllemb 19709 frgpuplem 19726 wrdsplex 32661 splfv3 32679 cycpmco2f1 32845 cycpmco2rn 32846 cycpmco2lem2 32848 cycpmco2lem3 32849 cycpmco2lem4 32850 cycpmco2lem5 32851 cycpmco2lem6 32852 cycpmco2 32854 revpfxsfxrev 34725

W3C validator