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

Theorem wlkswwlksf1o 27136
Description: The mapping of (ordinary) walks to their sequences of vertices is a bijection in a simple pseudograph. (Contributed by AV, 6-May-2021.)
Hypothesis
Ref Expression
wlkswwlksf1o.f 𝐹 = (𝑤 ∈ (Walks‘𝐺) ↦ (2nd𝑤))
Assertion
Ref Expression
wlkswwlksf1o (𝐺 ∈ USPGraph → 𝐹:(Walks‘𝐺)–1-1-onto→(WWalks‘𝐺))
Distinct variable group:   𝑤,𝐺
Allowed substitution hint:   𝐹(𝑤)

Proof of Theorem wlkswwlksf1o
Dummy variables 𝑥 𝑦 𝑓 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fvex 6424 . . . . . 6 (1st𝑤) ∈ V
2 breq1 4846 . . . . . 6 (𝑓 = (1st𝑤) → (𝑓(Walks‘𝐺)(2nd𝑤) ↔ (1st𝑤)(Walks‘𝐺)(2nd𝑤)))
31, 2spcev 3488 . . . . 5 ((1st𝑤)(Walks‘𝐺)(2nd𝑤) → ∃𝑓 𝑓(Walks‘𝐺)(2nd𝑤))
4 wlkiswwlks 27133 . . . . 5 (𝐺 ∈ USPGraph → (∃𝑓 𝑓(Walks‘𝐺)(2nd𝑤) ↔ (2nd𝑤) ∈ (WWalks‘𝐺)))
53, 4syl5ib 236 . . . 4 (𝐺 ∈ USPGraph → ((1st𝑤)(Walks‘𝐺)(2nd𝑤) → (2nd𝑤) ∈ (WWalks‘𝐺)))
6 wlkcpr 26878 . . . . 5 (𝑤 ∈ (Walks‘𝐺) ↔ (1st𝑤)(Walks‘𝐺)(2nd𝑤))
76biimpi 208 . . . 4 (𝑤 ∈ (Walks‘𝐺) → (1st𝑤)(Walks‘𝐺)(2nd𝑤))
85, 7impel 502 . . 3 ((𝐺 ∈ USPGraph ∧ 𝑤 ∈ (Walks‘𝐺)) → (2nd𝑤) ∈ (WWalks‘𝐺))
9 wlkswwlksf1o.f . . 3 𝐹 = (𝑤 ∈ (Walks‘𝐺) ↦ (2nd𝑤))
108, 9fmptd 6610 . 2 (𝐺 ∈ USPGraph → 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺))
11 simpr 478 . . . 4 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺))
129a1i 11 . . . . . . . . 9 (𝑥 ∈ (Walks‘𝐺) → 𝐹 = (𝑤 ∈ (Walks‘𝐺) ↦ (2nd𝑤)))
13 fveq2 6411 . . . . . . . . . 10 (𝑤 = 𝑥 → (2nd𝑤) = (2nd𝑥))
1413adantl 474 . . . . . . . . 9 ((𝑥 ∈ (Walks‘𝐺) ∧ 𝑤 = 𝑥) → (2nd𝑤) = (2nd𝑥))
15 id 22 . . . . . . . . 9 (𝑥 ∈ (Walks‘𝐺) → 𝑥 ∈ (Walks‘𝐺))
16 fvexd 6426 . . . . . . . . 9 (𝑥 ∈ (Walks‘𝐺) → (2nd𝑥) ∈ V)
1712, 14, 15, 16fvmptd 6513 . . . . . . . 8 (𝑥 ∈ (Walks‘𝐺) → (𝐹𝑥) = (2nd𝑥))
189a1i 11 . . . . . . . . 9 (𝑦 ∈ (Walks‘𝐺) → 𝐹 = (𝑤 ∈ (Walks‘𝐺) ↦ (2nd𝑤)))
19 fveq2 6411 . . . . . . . . . 10 (𝑤 = 𝑦 → (2nd𝑤) = (2nd𝑦))
2019adantl 474 . . . . . . . . 9 ((𝑦 ∈ (Walks‘𝐺) ∧ 𝑤 = 𝑦) → (2nd𝑤) = (2nd𝑦))
21 id 22 . . . . . . . . 9 (𝑦 ∈ (Walks‘𝐺) → 𝑦 ∈ (Walks‘𝐺))
22 fvexd 6426 . . . . . . . . 9 (𝑦 ∈ (Walks‘𝐺) → (2nd𝑦) ∈ V)
2318, 20, 21, 22fvmptd 6513 . . . . . . . 8 (𝑦 ∈ (Walks‘𝐺) → (𝐹𝑦) = (2nd𝑦))
2417, 23eqeqan12d 2815 . . . . . . 7 ((𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺)) → ((𝐹𝑥) = (𝐹𝑦) ↔ (2nd𝑥) = (2nd𝑦)))
2524adantl 474 . . . . . 6 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ (𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺))) → ((𝐹𝑥) = (𝐹𝑦) ↔ (2nd𝑥) = (2nd𝑦)))
26 uspgr2wlkeqi 26897 . . . . . . . 8 ((𝐺 ∈ USPGraph ∧ (𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺)) ∧ (2nd𝑥) = (2nd𝑦)) → 𝑥 = 𝑦)
2726ad4ant134 1218 . . . . . . 7 ((((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ (𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺))) ∧ (2nd𝑥) = (2nd𝑦)) → 𝑥 = 𝑦)
2827ex 402 . . . . . 6 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ (𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺))) → ((2nd𝑥) = (2nd𝑦) → 𝑥 = 𝑦))
2925, 28sylbid 232 . . . . 5 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ (𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 ∈ (Walks‘𝐺))) → ((𝐹𝑥) = (𝐹𝑦) → 𝑥 = 𝑦))
3029ralrimivva 3152 . . . 4 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → ∀𝑥 ∈ (Walks‘𝐺)∀𝑦 ∈ (Walks‘𝐺)((𝐹𝑥) = (𝐹𝑦) → 𝑥 = 𝑦))
31 dff13 6740 . . . 4 (𝐹:(Walks‘𝐺)–1-1→(WWalks‘𝐺) ↔ (𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺) ∧ ∀𝑥 ∈ (Walks‘𝐺)∀𝑦 ∈ (Walks‘𝐺)((𝐹𝑥) = (𝐹𝑦) → 𝑥 = 𝑦)))
3211, 30, 31sylanbrc 579 . . 3 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → 𝐹:(Walks‘𝐺)–1-1→(WWalks‘𝐺))
33 wlkiswwlks 27133 . . . . . . . . . 10 (𝐺 ∈ USPGraph → (∃𝑓 𝑓(Walks‘𝐺)𝑦𝑦 ∈ (WWalks‘𝐺)))
3433adantr 473 . . . . . . . . 9 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → (∃𝑓 𝑓(Walks‘𝐺)𝑦𝑦 ∈ (WWalks‘𝐺)))
35 df-br 4844 . . . . . . . . . . 11 (𝑓(Walks‘𝐺)𝑦 ↔ ⟨𝑓, 𝑦⟩ ∈ (Walks‘𝐺))
36 vex 3388 . . . . . . . . . . . . . 14 𝑓 ∈ V
37 vex 3388 . . . . . . . . . . . . . 14 𝑦 ∈ V
3836, 37op2nd 7410 . . . . . . . . . . . . 13 (2nd ‘⟨𝑓, 𝑦⟩) = 𝑦
3938eqcomi 2808 . . . . . . . . . . . 12 𝑦 = (2nd ‘⟨𝑓, 𝑦⟩)
40 opex 5123 . . . . . . . . . . . . 13 𝑓, 𝑦⟩ ∈ V
41 eleq1 2866 . . . . . . . . . . . . . 14 (𝑥 = ⟨𝑓, 𝑦⟩ → (𝑥 ∈ (Walks‘𝐺) ↔ ⟨𝑓, 𝑦⟩ ∈ (Walks‘𝐺)))
42 fveq2 6411 . . . . . . . . . . . . . . 15 (𝑥 = ⟨𝑓, 𝑦⟩ → (2nd𝑥) = (2nd ‘⟨𝑓, 𝑦⟩))
4342eqeq2d 2809 . . . . . . . . . . . . . 14 (𝑥 = ⟨𝑓, 𝑦⟩ → (𝑦 = (2nd𝑥) ↔ 𝑦 = (2nd ‘⟨𝑓, 𝑦⟩)))
4441, 43anbi12d 625 . . . . . . . . . . . . 13 (𝑥 = ⟨𝑓, 𝑦⟩ → ((𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)) ↔ (⟨𝑓, 𝑦⟩ ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd ‘⟨𝑓, 𝑦⟩))))
4540, 44spcev 3488 . . . . . . . . . . . 12 ((⟨𝑓, 𝑦⟩ ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd ‘⟨𝑓, 𝑦⟩)) → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
4639, 45mpan2 683 . . . . . . . . . . 11 (⟨𝑓, 𝑦⟩ ∈ (Walks‘𝐺) → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
4735, 46sylbi 209 . . . . . . . . . 10 (𝑓(Walks‘𝐺)𝑦 → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
4847exlimiv 2026 . . . . . . . . 9 (∃𝑓 𝑓(Walks‘𝐺)𝑦 → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
4934, 48syl6bir 246 . . . . . . . 8 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → (𝑦 ∈ (WWalks‘𝐺) → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥))))
5049imp 396 . . . . . . 7 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ 𝑦 ∈ (WWalks‘𝐺)) → ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
51 df-rex 3095 . . . . . . 7 (∃𝑥 ∈ (Walks‘𝐺)𝑦 = (2nd𝑥) ↔ ∃𝑥(𝑥 ∈ (Walks‘𝐺) ∧ 𝑦 = (2nd𝑥)))
5250, 51sylibr 226 . . . . . 6 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ 𝑦 ∈ (WWalks‘𝐺)) → ∃𝑥 ∈ (Walks‘𝐺)𝑦 = (2nd𝑥))
5317eqeq2d 2809 . . . . . . 7 (𝑥 ∈ (Walks‘𝐺) → (𝑦 = (𝐹𝑥) ↔ 𝑦 = (2nd𝑥)))
5453rexbiia 3221 . . . . . 6 (∃𝑥 ∈ (Walks‘𝐺)𝑦 = (𝐹𝑥) ↔ ∃𝑥 ∈ (Walks‘𝐺)𝑦 = (2nd𝑥))
5552, 54sylibr 226 . . . . 5 (((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) ∧ 𝑦 ∈ (WWalks‘𝐺)) → ∃𝑥 ∈ (Walks‘𝐺)𝑦 = (𝐹𝑥))
5655ralrimiva 3147 . . . 4 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → ∀𝑦 ∈ (WWalks‘𝐺)∃𝑥 ∈ (Walks‘𝐺)𝑦 = (𝐹𝑥))
57 dffo3 6600 . . . 4 (𝐹:(Walks‘𝐺)–onto→(WWalks‘𝐺) ↔ (𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺) ∧ ∀𝑦 ∈ (WWalks‘𝐺)∃𝑥 ∈ (Walks‘𝐺)𝑦 = (𝐹𝑥)))
5811, 56, 57sylanbrc 579 . . 3 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → 𝐹:(Walks‘𝐺)–onto→(WWalks‘𝐺))
59 df-f1o 6108 . . 3 (𝐹:(Walks‘𝐺)–1-1-onto→(WWalks‘𝐺) ↔ (𝐹:(Walks‘𝐺)–1-1→(WWalks‘𝐺) ∧ 𝐹:(Walks‘𝐺)–onto→(WWalks‘𝐺)))
6032, 58, 59sylanbrc 579 . 2 ((𝐺 ∈ USPGraph ∧ 𝐹:(Walks‘𝐺)⟶(WWalks‘𝐺)) → 𝐹:(Walks‘𝐺)–1-1-onto→(WWalks‘𝐺))
6110, 60mpdan 679 1 (𝐺 ∈ USPGraph → 𝐹:(Walks‘𝐺)–1-1-onto→(WWalks‘𝐺))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 198  wa 385   = wceq 1653  wex 1875  wcel 2157  wral 3089  wrex 3090  Vcvv 3385  cop 4374   class class class wbr 4843  cmpt 4922  wf 6097  1-1wf1 6098  ontowfo 6099  1-1-ontowf1o 6100  cfv 6101  1st c1st 7399  2nd c2nd 7400  USPGraphcuspgr 26384  Walkscwlks 26846  WWalkscwwlks 27076
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1891  ax-4 1905  ax-5 2006  ax-6 2072  ax-7 2107  ax-8 2159  ax-9 2166  ax-10 2185  ax-11 2200  ax-12 2213  ax-13 2377  ax-ext 2777  ax-rep 4964  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5097  ax-un 7183  ax-cnex 10280  ax-resscn 10281  ax-1cn 10282  ax-icn 10283  ax-addcl 10284  ax-addrcl 10285  ax-mulcl 10286  ax-mulrcl 10287  ax-mulcom 10288  ax-addass 10289  ax-mulass 10290  ax-distr 10291  ax-i2m1 10292  ax-1ne0 10293  ax-1rid 10294  ax-rnegex 10295  ax-rrecex 10296  ax-cnre 10297  ax-pre-lttri 10298  ax-pre-lttrn 10299  ax-pre-ltadd 10300  ax-pre-mulgt0 10301
This theorem depends on definitions:  df-bi 199  df-an 386  df-or 875  df-ifp 1087  df-3or 1109  df-3an 1110  df-tru 1657  df-ex 1876  df-nf 1880  df-sb 2065  df-mo 2591  df-eu 2609  df-clab 2786  df-cleq 2792  df-clel 2795  df-nfc 2930  df-ne 2972  df-nel 3075  df-ral 3094  df-rex 3095  df-reu 3096  df-rmo 3097  df-rab 3098  df-v 3387  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4116  df-if 4278  df-pw 4351  df-sn 4369  df-pr 4371  df-tp 4373  df-op 4375  df-uni 4629  df-int 4668  df-iun 4712  df-br 4844  df-opab 4906  df-mpt 4923  df-tr 4946  df-id 5220  df-eprel 5225  df-po 5233  df-so 5234  df-fr 5271  df-we 5273  df-xp 5318  df-rel 5319  df-cnv 5320  df-co 5321  df-dm 5322  df-rn 5323  df-res 5324  df-ima 5325  df-pred 5898  df-ord 5944  df-on 5945  df-lim 5946  df-suc 5947  df-iota 6064  df-fun 6103  df-fn 6104  df-f 6105  df-f1 6106  df-fo 6107  df-f1o 6108  df-fv 6109  df-riota 6839  df-ov 6881  df-oprab 6882  df-mpt2 6883  df-om 7300  df-1st 7401  df-2nd 7402  df-wrecs 7645  df-recs 7707  df-rdg 7745  df-1o 7799  df-2o 7800  df-oadd 7803  df-er 7982  df-map 8097  df-pm 8098  df-en 8196  df-dom 8197  df-sdom 8198  df-fin 8199  df-card 9051  df-cda 9278  df-pnf 10365  df-mnf 10366  df-xr 10367  df-ltxr 10368  df-le 10369  df-sub 10558  df-neg 10559  df-nn 11313  df-2 11376  df-n0 11581  df-xnn0 11653  df-z 11667  df-uz 11931  df-fz 12581  df-fzo 12721  df-hash 13371  df-word 13535  df-edg 26283  df-uhgr 26293  df-upgr 26317  df-uspgr 26386  df-wlks 26849  df-wwlks 27081
This theorem is referenced by:  wlkswwlksen  27137  wlknwwlksnbij  27150
  Copyright terms: Public domain W3C validator