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

Theorem clwlkclwwlkf 27162
Description: 𝐹 is a function from the nonempty closed walks into the closed walks as word in a simple pseudograph. (Contributed by AV, 23-May-2022.)
Hypotheses
Ref Expression
clwlkclwwlkf.c 𝐶 = {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))}
clwlkclwwlkf.f 𝐹 = (𝑐𝐶 ↦ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩))
Assertion
Ref Expression
clwlkclwwlkf (𝐺 ∈ USPGraph → 𝐹:𝐶⟶(ClWWalks‘𝐺))
Distinct variable groups:   𝑤,𝐺,𝑐   𝐶,𝑐
Allowed substitution hints:   𝐶(𝑤)   𝐹(𝑤,𝑐)

Proof of Theorem clwlkclwwlkf
Dummy variable 𝑓 is distinct from all other variables.
StepHypRef Expression
1 clwlkclwwlkf.c . . . . 5 𝐶 = {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))}
2 eqid 2769 . . . . 5 (1st𝑐) = (1st𝑐)
3 eqid 2769 . . . . 5 (2nd𝑐) = (2nd𝑐)
41, 2, 3clwlkclwwlkflem 27158 . . . 4 (𝑐𝐶 → ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ))
5 isclwlk 26910 . . . . . . . 8 ((1st𝑐)(ClWalks‘𝐺)(2nd𝑐) ↔ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐)))))
6 fvex 6341 . . . . . . . . . 10 (1st𝑐) ∈ V
76jctl 566 . . . . . . . . 9 ((1st𝑐)(ClWalks‘𝐺)(2nd𝑐) → ((1st𝑐) ∈ V ∧ (1st𝑐)(ClWalks‘𝐺)(2nd𝑐)))
8 breq1 4786 . . . . . . . . . 10 (𝑓 = (1st𝑐) → (𝑓(ClWalks‘𝐺)(2nd𝑐) ↔ (1st𝑐)(ClWalks‘𝐺)(2nd𝑐)))
98rspcev 3457 . . . . . . . . 9 (((1st𝑐) ∈ V ∧ (1st𝑐)(ClWalks‘𝐺)(2nd𝑐)) → ∃𝑓 ∈ V 𝑓(ClWalks‘𝐺)(2nd𝑐))
10 rexex 3148 . . . . . . . . 9 (∃𝑓 ∈ V 𝑓(ClWalks‘𝐺)(2nd𝑐) → ∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐))
117, 9, 103syl 18 . . . . . . . 8 ((1st𝑐)(ClWalks‘𝐺)(2nd𝑐) → ∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐))
125, 11sylbir 225 . . . . . . 7 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐)))) → ∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐))
13123adant3 1124 . . . . . 6 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ) → ∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐))
1413adantl 474 . . . . 5 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → ∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐))
15 simpl 475 . . . . . 6 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → 𝐺 ∈ USPGraph)
16 eqid 2769 . . . . . . . . 9 (Vtx‘𝐺) = (Vtx‘𝐺)
1716wlkpwrd 26754 . . . . . . . 8 ((1st𝑐)(Walks‘𝐺)(2nd𝑐) → (2nd𝑐) ∈ Word (Vtx‘𝐺))
18173ad2ant1 1125 . . . . . . 7 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ) → (2nd𝑐) ∈ Word (Vtx‘𝐺))
1918adantl 474 . . . . . 6 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → (2nd𝑐) ∈ Word (Vtx‘𝐺))
20 elnnnn0c 11538 . . . . . . . . . 10 ((♯‘(1st𝑐)) ∈ ℕ ↔ ((♯‘(1st𝑐)) ∈ ℕ0 ∧ 1 ≤ (♯‘(1st𝑐))))
21 nn0re 11501 . . . . . . . . . . . . . 14 ((♯‘(1st𝑐)) ∈ ℕ0 → (♯‘(1st𝑐)) ∈ ℝ)
22 1e2m1 11336 . . . . . . . . . . . . . . . . 17 1 = (2 − 1)
2322breq1i 4790 . . . . . . . . . . . . . . . 16 (1 ≤ (♯‘(1st𝑐)) ↔ (2 − 1) ≤ (♯‘(1st𝑐)))
2423biimpi 206 . . . . . . . . . . . . . . 15 (1 ≤ (♯‘(1st𝑐)) → (2 − 1) ≤ (♯‘(1st𝑐)))
25 2re 11290 . . . . . . . . . . . . . . . 16 2 ∈ ℝ
26 1re 10239 . . . . . . . . . . . . . . . 16 1 ∈ ℝ
27 lesubadd 10700 . . . . . . . . . . . . . . . 16 ((2 ∈ ℝ ∧ 1 ∈ ℝ ∧ (♯‘(1st𝑐)) ∈ ℝ) → ((2 − 1) ≤ (♯‘(1st𝑐)) ↔ 2 ≤ ((♯‘(1st𝑐)) + 1)))
2825, 26, 27mp3an12 1560 . . . . . . . . . . . . . . 15 ((♯‘(1st𝑐)) ∈ ℝ → ((2 − 1) ≤ (♯‘(1st𝑐)) ↔ 2 ≤ ((♯‘(1st𝑐)) + 1)))
2924, 28syl5ib 234 . . . . . . . . . . . . . 14 ((♯‘(1st𝑐)) ∈ ℝ → (1 ≤ (♯‘(1st𝑐)) → 2 ≤ ((♯‘(1st𝑐)) + 1)))
3021, 29syl 17 . . . . . . . . . . . . 13 ((♯‘(1st𝑐)) ∈ ℕ0 → (1 ≤ (♯‘(1st𝑐)) → 2 ≤ ((♯‘(1st𝑐)) + 1)))
3130adantl 474 . . . . . . . . . . . 12 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ (♯‘(1st𝑐)) ∈ ℕ0) → (1 ≤ (♯‘(1st𝑐)) → 2 ≤ ((♯‘(1st𝑐)) + 1)))
32 wlklenvp1 26755 . . . . . . . . . . . . . 14 ((1st𝑐)(Walks‘𝐺)(2nd𝑐) → (♯‘(2nd𝑐)) = ((♯‘(1st𝑐)) + 1))
3332adantr 473 . . . . . . . . . . . . 13 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ (♯‘(1st𝑐)) ∈ ℕ0) → (♯‘(2nd𝑐)) = ((♯‘(1st𝑐)) + 1))
3433breq2d 4795 . . . . . . . . . . . 12 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ (♯‘(1st𝑐)) ∈ ℕ0) → (2 ≤ (♯‘(2nd𝑐)) ↔ 2 ≤ ((♯‘(1st𝑐)) + 1)))
3531, 34sylibrd 249 . . . . . . . . . . 11 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ (♯‘(1st𝑐)) ∈ ℕ0) → (1 ≤ (♯‘(1st𝑐)) → 2 ≤ (♯‘(2nd𝑐))))
3635expimpd 629 . . . . . . . . . 10 ((1st𝑐)(Walks‘𝐺)(2nd𝑐) → (((♯‘(1st𝑐)) ∈ ℕ0 ∧ 1 ≤ (♯‘(1st𝑐))) → 2 ≤ (♯‘(2nd𝑐))))
3720, 36syl5bi 232 . . . . . . . . 9 ((1st𝑐)(Walks‘𝐺)(2nd𝑐) → ((♯‘(1st𝑐)) ∈ ℕ → 2 ≤ (♯‘(2nd𝑐))))
3837a1d 25 . . . . . . . 8 ((1st𝑐)(Walks‘𝐺)(2nd𝑐) → (((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) → ((♯‘(1st𝑐)) ∈ ℕ → 2 ≤ (♯‘(2nd𝑐)))))
39383imp 1099 . . . . . . 7 (((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ) → 2 ≤ (♯‘(2nd𝑐)))
4039adantl 474 . . . . . 6 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → 2 ≤ (♯‘(2nd𝑐)))
41 eqid 2769 . . . . . . 7 (iEdg‘𝐺) = (iEdg‘𝐺)
4216, 41clwlkclwwlk 27156 . . . . . 6 ((𝐺 ∈ USPGraph ∧ (2nd𝑐) ∈ Word (Vtx‘𝐺) ∧ 2 ≤ (♯‘(2nd𝑐))) → (∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐) ↔ ((lastS‘(2nd𝑐)) = ((2nd𝑐)‘0) ∧ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩) ∈ (ClWWalks‘𝐺))))
4315, 19, 40, 42syl3anc 1474 . . . . 5 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → (∃𝑓 𝑓(ClWalks‘𝐺)(2nd𝑐) ↔ ((lastS‘(2nd𝑐)) = ((2nd𝑐)‘0) ∧ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩) ∈ (ClWWalks‘𝐺))))
4414, 43mpbid 222 . . . 4 ((𝐺 ∈ USPGraph ∧ ((1st𝑐)(Walks‘𝐺)(2nd𝑐) ∧ ((2nd𝑐)‘0) = ((2nd𝑐)‘(♯‘(1st𝑐))) ∧ (♯‘(1st𝑐)) ∈ ℕ)) → ((lastS‘(2nd𝑐)) = ((2nd𝑐)‘0) ∧ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩) ∈ (ClWWalks‘𝐺)))
454, 44sylan2 493 . . 3 ((𝐺 ∈ USPGraph ∧ 𝑐𝐶) → ((lastS‘(2nd𝑐)) = ((2nd𝑐)‘0) ∧ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩) ∈ (ClWWalks‘𝐺)))
4645simprd 483 . 2 ((𝐺 ∈ USPGraph ∧ 𝑐𝐶) → ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩) ∈ (ClWWalks‘𝐺))
47 clwlkclwwlkf.f . 2 𝐹 = (𝑐𝐶 ↦ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩))
4846, 47fmptd 6526 1 (𝐺 ∈ USPGraph → 𝐹:𝐶⟶(ClWWalks‘𝐺))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wa 383  w3a 1069   = wceq 1629  wex 1850  wcel 2143  wrex 3060  {crab 3063  Vcvv 3348  cop 4319   class class class wbr 4783  cmpt 4860  wf 6026  cfv 6030  (class class class)co 6791  1st c1st 7311  2nd c2nd 7312  cr 10135  0cc0 10136  1c1 10137   + caddc 10139  cle 10275  cmin 10466  cn 11220  2c2 11270  0cn0 11492  chash 13324  Word cword 13490  lastSclsw 13491   substr csubstr 13494  Vtxcvtx 26101  iEdgciedg 26102  USPGraphcuspgr 26271  Walkscwlks 26733  ClWalkscclwlks 26907  ClWWalkscclwwlk 27135
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1868  ax-4 1883  ax-5 1989  ax-6 2055  ax-7 2091  ax-8 2145  ax-9 2152  ax-10 2172  ax-11 2188  ax-12 2201  ax-13 2406  ax-ext 2749  ax-rep 4901  ax-sep 4911  ax-nul 4919  ax-pow 4970  ax-pr 5033  ax-un 7094  ax-cnex 10192  ax-resscn 10193  ax-1cn 10194  ax-icn 10195  ax-addcl 10196  ax-addrcl 10197  ax-mulcl 10198  ax-mulrcl 10199  ax-mulcom 10200  ax-addass 10201  ax-mulass 10202  ax-distr 10203  ax-i2m1 10204  ax-1ne0 10205  ax-1rid 10206  ax-rnegex 10207  ax-rrecex 10208  ax-cnre 10209  ax-pre-lttri 10210  ax-pre-lttrn 10211  ax-pre-ltadd 10212  ax-pre-mulgt0 10213
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-ifp 1048  df-3or 1070  df-3an 1071  df-tru 1632  df-ex 1851  df-nf 1856  df-sb 2048  df-eu 2620  df-mo 2621  df-clab 2756  df-cleq 2762  df-clel 2765  df-nfc 2900  df-ne 2942  df-nel 3045  df-ral 3064  df-rex 3065  df-reu 3066  df-rmo 3067  df-rab 3068  df-v 3350  df-sbc 3585  df-csb 3680  df-dif 3723  df-un 3725  df-in 3727  df-ss 3734  df-pss 3736  df-nul 4061  df-if 4223  df-pw 4296  df-sn 4314  df-pr 4316  df-tp 4318  df-op 4320  df-uni 4572  df-int 4609  df-iun 4653  df-br 4784  df-opab 4844  df-mpt 4861  df-tr 4884  df-id 5156  df-eprel 5161  df-po 5169  df-so 5170  df-fr 5207  df-we 5209  df-xp 5254  df-rel 5255  df-cnv 5256  df-co 5257  df-dm 5258  df-rn 5259  df-res 5260  df-ima 5261  df-pred 5822  df-ord 5868  df-on 5869  df-lim 5870  df-suc 5871  df-iota 5993  df-fun 6032  df-fn 6033  df-f 6034  df-f1 6035  df-fo 6036  df-f1o 6037  df-fv 6038  df-riota 6752  df-ov 6794  df-oprab 6795  df-mpt2 6796  df-om 7211  df-1st 7313  df-2nd 7314  df-wrecs 7557  df-recs 7619  df-rdg 7657  df-1o 7711  df-2o 7712  df-oadd 7715  df-er 7894  df-map 8009  df-pm 8010  df-en 8108  df-dom 8109  df-sdom 8110  df-fin 8111  df-card 8963  df-cda 9190  df-pnf 10276  df-mnf 10277  df-xr 10278  df-ltxr 10279  df-le 10280  df-sub 10468  df-neg 10469  df-nn 11221  df-2 11279  df-n0 11493  df-xnn0 11564  df-z 11578  df-uz 11888  df-fz 12533  df-fzo 12673  df-hash 13325  df-word 13498  df-lsw 13499  df-substr 13502  df-edg 26167  df-uhgr 26180  df-upgr 26204  df-uspgr 26273  df-wlks 26736  df-clwlks 26908  df-clwwlk 27136
This theorem is referenced by:  clwlkclwwlkfo  27163  clwlkclwwlkf1  27164
  Copyright terms: Public domain W3C validator