wwlksnextfun - Metamath Proof Explorer

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

Theorem wwlksnextfun 29141

Description: Lemma for wwlksnextbij 29145. (Contributed by Alexander van der Vekens, 7-Aug-2018.) (Revised by AV, 18-Apr-2021.) (Revised by AV, 27-Oct-2022.)

**Hypotheses**
Ref	Expression
wwlksnextbij0.v	⊢ 𝑉 = (Vtx‘𝐺)
wwlksnextbij0.e	⊢ 𝐸 = (Edg‘𝐺)
wwlksnextbij0.d	⊢ 𝐷 = {𝑤 ∈ Word 𝑉 ∣ ((♯‘𝑤) = (𝑁 + 2) ∧ (𝑤 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑤)} ∈ 𝐸)}
wwlksnextbij0.r	⊢ 𝑅 = {𝑛 ∈ 𝑉 ∣ {(lastS‘𝑊), 𝑛} ∈ 𝐸}
wwlksnextbij0.f	⊢ 𝐹 = (𝑡 ∈ 𝐷 ↦ (lastS‘𝑡))

**Assertion**
Ref	Expression
wwlksnextfun	⊢ (𝑁 ∈ ℕ₀ → 𝐹:𝐷⟶𝑅)

Distinct variable groups: 𝑤,𝐺 𝑤,𝑁 𝑤,𝑊 𝑡,𝐷 𝑛,𝐸 𝑤,𝐸 𝑡,𝑁,𝑤 𝑡,𝑅 𝑛,𝑉 𝑤,𝑉 𝑛,𝑊 𝑡,𝑛 Allowed substitution hints: 𝐷(𝑤,𝑛) 𝑅(𝑤,𝑛) 𝐸(𝑡) 𝐹(𝑤,𝑡,𝑛) 𝐺(𝑡,𝑛) 𝑁(𝑛) 𝑉(𝑡) 𝑊(𝑡)

**Proof of Theorem wwlksnextfun**
Step	Hyp	Ref	Expression
1		fveqeq2 6897	. . . . . 6 ⊢ (𝑤 = 𝑡 → ((♯‘𝑤) = (𝑁 + 2) ↔ (♯‘𝑡) = (𝑁 + 2)))
2		oveq1 7412	. . . . . . 7 ⊢ (𝑤 = 𝑡 → (𝑤 prefix (𝑁 + 1)) = (𝑡 prefix (𝑁 + 1)))
3	2	eqeq1d 2734	. . . . . 6 ⊢ (𝑤 = 𝑡 → ((𝑤 prefix (𝑁 + 1)) = 𝑊 ↔ (𝑡 prefix (𝑁 + 1)) = 𝑊))
4		fveq2 6888	. . . . . . . 8 ⊢ (𝑤 = 𝑡 → (lastS‘𝑤) = (lastS‘𝑡))
5	4	preq2d 4743	. . . . . . 7 ⊢ (𝑤 = 𝑡 → {(lastS‘𝑊), (lastS‘𝑤)} = {(lastS‘𝑊), (lastS‘𝑡)})
6	5	eleq1d 2818	. . . . . 6 ⊢ (𝑤 = 𝑡 → ({(lastS‘𝑊), (lastS‘𝑤)} ∈ 𝐸 ↔ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))
7	1, 3, 6	3anbi123d 1436	. . . . 5 ⊢ (𝑤 = 𝑡 → (((♯‘𝑤) = (𝑁 + 2) ∧ (𝑤 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑤)} ∈ 𝐸) ↔ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸)))
8		wwlksnextbij0.d	. . . . 5 ⊢ 𝐷 = {𝑤 ∈ Word 𝑉 ∣ ((♯‘𝑤) = (𝑁 + 2) ∧ (𝑤 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑤)} ∈ 𝐸)}
9	7, 8	elrab2 3685	. . . 4 ⊢ (𝑡 ∈ 𝐷 ↔ (𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸)))
10		simpll 765	. . . . . . . . . . . 12 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → 𝑡 ∈ Word 𝑉)
11		nn0re 12477	. . . . . . . . . . . . . . . 16 ⊢ (𝑁 ∈ ℕ₀ → 𝑁 ∈ ℝ)
12		2re 12282	. . . . . . . . . . . . . . . . 17 ⊢ 2 ∈ ℝ
13	12	a1i 11	. . . . . . . . . . . . . . . 16 ⊢ (𝑁 ∈ ℕ₀ → 2 ∈ ℝ)
14		nn0ge0 12493	. . . . . . . . . . . . . . . 16 ⊢ (𝑁 ∈ ℕ₀ → 0 ≤ 𝑁)
15		2pos 12311	. . . . . . . . . . . . . . . . 17 ⊢ 0 < 2
16	15	a1i 11	. . . . . . . . . . . . . . . 16 ⊢ (𝑁 ∈ ℕ₀ → 0 < 2)
17	11, 13, 14, 16	addgegt0d 11783	. . . . . . . . . . . . . . 15 ⊢ (𝑁 ∈ ℕ₀ → 0 < (𝑁 + 2))
18	17	ad2antlr 725	. . . . . . . . . . . . . 14 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → 0 < (𝑁 + 2))
19		breq2 5151	. . . . . . . . . . . . . . 15 ⊢ ((♯‘𝑡) = (𝑁 + 2) → (0 < (♯‘𝑡) ↔ 0 < (𝑁 + 2)))
20	19	adantl 482	. . . . . . . . . . . . . 14 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → (0 < (♯‘𝑡) ↔ 0 < (𝑁 + 2)))
21	18, 20	mpbird 256	. . . . . . . . . . . . 13 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → 0 < (♯‘𝑡))
22		hashgt0n0 14321	. . . . . . . . . . . . 13 ⊢ ((𝑡 ∈ Word 𝑉 ∧ 0 < (♯‘𝑡)) → 𝑡 ≠ ∅)
23	10, 21, 22	syl2anc 584	. . . . . . . . . . . 12 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → 𝑡 ≠ ∅)
24	10, 23	jca 512	. . . . . . . . . . 11 ⊢ (((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) ∧ (♯‘𝑡) = (𝑁 + 2)) → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅))
25	24	expcom 414	. . . . . . . . . 10 ⊢ ((♯‘𝑡) = (𝑁 + 2) → ((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅)))
26	25	3ad2ant1 1133	. . . . . . . . 9 ⊢ (((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸) → ((𝑡 ∈ Word 𝑉 ∧ 𝑁 ∈ ℕ₀) → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅)))
27	26	expd 416	. . . . . . . 8 ⊢ (((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸) → (𝑡 ∈ Word 𝑉 → (𝑁 ∈ ℕ₀ → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅))))
28	27	impcom 408	. . . . . . 7 ⊢ ((𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸)) → (𝑁 ∈ ℕ₀ → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅)))
29	28	impcom 408	. . . . . 6 ⊢ ((𝑁 ∈ ℕ₀ ∧ (𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))) → (𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅))
30		lswcl 14514	. . . . . 6 ⊢ ((𝑡 ∈ Word 𝑉 ∧ 𝑡 ≠ ∅) → (lastS‘𝑡) ∈ 𝑉)
31	29, 30	syl 17	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ (𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))) → (lastS‘𝑡) ∈ 𝑉)
32		simprr3 1223	. . . . 5 ⊢ ((𝑁 ∈ ℕ₀ ∧ (𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))) → {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸)
33	31, 32	jca 512	. . . 4 ⊢ ((𝑁 ∈ ℕ₀ ∧ (𝑡 ∈ Word 𝑉 ∧ ((♯‘𝑡) = (𝑁 + 2) ∧ (𝑡 prefix (𝑁 + 1)) = 𝑊 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))) → ((lastS‘𝑡) ∈ 𝑉 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))
34	9, 33	sylan2b 594	. . 3 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝑡 ∈ 𝐷) → ((lastS‘𝑡) ∈ 𝑉 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))
35		preq2 4737	. . . . 5 ⊢ (𝑛 = (lastS‘𝑡) → {(lastS‘𝑊), 𝑛} = {(lastS‘𝑊), (lastS‘𝑡)})
36	35	eleq1d 2818	. . . 4 ⊢ (𝑛 = (lastS‘𝑡) → ({(lastS‘𝑊), 𝑛} ∈ 𝐸 ↔ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))
37		wwlksnextbij0.r	. . . 4 ⊢ 𝑅 = {𝑛 ∈ 𝑉 ∣ {(lastS‘𝑊), 𝑛} ∈ 𝐸}
38	36, 37	elrab2 3685	. . 3 ⊢ ((lastS‘𝑡) ∈ 𝑅 ↔ ((lastS‘𝑡) ∈ 𝑉 ∧ {(lastS‘𝑊), (lastS‘𝑡)} ∈ 𝐸))
39	34, 38	sylibr 233	. 2 ⊢ ((𝑁 ∈ ℕ₀ ∧ 𝑡 ∈ 𝐷) → (lastS‘𝑡) ∈ 𝑅)
40		wwlksnextbij0.f	. 2 ⊢ 𝐹 = (𝑡 ∈ 𝐷 ↦ (lastS‘𝑡))
41	39, 40	fmptd 7110	1 ⊢ (𝑁 ∈ ℕ₀ → 𝐹:𝐷⟶𝑅)

Colors of variables: wff setvar class

Syntax hints: → wi 4 ↔ wb 205 ∧ wa 396 ∧ w3a 1087 = wceq 1541 ∈ wcel 2106 ≠ wne 2940 {crab 3432 ∅c0 4321 {cpr 4629 class class class wbr 5147 ↦ cmpt 5230 ⟶wf 6536 ‘cfv 6540 (class class class)co 7405 ℝcr 11105 0cc0 11106 1c1 11107 + caddc 11109 < clt 11244 2c2 12263 ℕ₀cn0 12468 ♯chash 14286 Word cword 14460 lastSclsw 14508 prefix cpfx 14616 Vtxcvtx 28245 Edgcedg 28296

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1797 ax-4 1811 ax-5 1913 ax-6 1971 ax-7 2011 ax-8 2108 ax-9 2116 ax-10 2137 ax-11 2154 ax-12 2171 ax-ext 2703 ax-rep 5284 ax-sep 5298 ax-nul 5305 ax-pow 5362 ax-pr 5426 ax-un 7721 ax-cnex 11162 ax-resscn 11163 ax-1cn 11164 ax-icn 11165 ax-addcl 11166 ax-addrcl 11167 ax-mulcl 11168 ax-mulrcl 11169 ax-mulcom 11170 ax-addass 11171 ax-mulass 11172 ax-distr 11173 ax-i2m1 11174 ax-1ne0 11175 ax-1rid 11176 ax-rnegex 11177 ax-rrecex 11178 ax-cnre 11179 ax-pre-lttri 11180 ax-pre-lttrn 11181 ax-pre-ltadd 11182 ax-pre-mulgt0 11183

This theorem depends on definitions: df-bi 206 df-an 397 df-or 846 df-3or 1088 df-3an 1089 df-tru 1544 df-fal 1554 df-ex 1782 df-nf 1786 df-sb 2068 df-mo 2534 df-eu 2563 df-clab 2710 df-cleq 2724 df-clel 2810 df-nfc 2885 df-ne 2941 df-nel 3047 df-ral 3062 df-rex 3071 df-reu 3377 df-rab 3433 df-v 3476 df-sbc 3777 df-csb 3893 df-dif 3950 df-un 3952 df-in 3954 df-ss 3964 df-pss 3966 df-nul 4322 df-if 4528 df-pw 4603 df-sn 4628 df-pr 4630 df-op 4634 df-uni 4908 df-int 4950 df-iun 4998 df-br 5148 df-opab 5210 df-mpt 5231 df-tr 5265 df-id 5573 df-eprel 5579 df-po 5587 df-so 5588 df-fr 5630 df-we 5632 df-xp 5681 df-rel 5682 df-cnv 5683 df-co 5684 df-dm 5685 df-rn 5686 df-res 5687 df-ima 5688 df-pred 6297 df-ord 6364 df-on 6365 df-lim 6366 df-suc 6367 df-iota 6492 df-fun 6542 df-fn 6543 df-f 6544 df-f1 6545 df-fo 6546 df-f1o 6547 df-fv 6548 df-riota 7361 df-ov 7408 df-oprab 7409 df-mpo 7410 df-om 7852 df-1st 7971 df-2nd 7972 df-frecs 8262 df-wrecs 8293 df-recs 8367 df-rdg 8406 df-1o 8462 df-er 8699 df-en 8936 df-dom 8937 df-sdom 8938 df-fin 8939 df-card 9930 df-pnf 11246 df-mnf 11247 df-xr 11248 df-ltxr 11249 df-le 11250 df-sub 11442 df-neg 11443 df-nn 12209 df-2 12271 df-n0 12469 df-xnn0 12541 df-z 12555 df-uz 12819 df-fz 13481 df-fzo 13624 df-hash 14287 df-word 14461 df-lsw 14509

This theorem is referenced by: wwlksnextinj 29142 wwlksnextsurj 29143

W3C validator