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

Theorem wlksnwwlknvbij 28270
Description: There is a bijection between the set of walks of a fixed length and the set of walks represented by words of the same length and starting at the same vertex. (Contributed by Alexander van der Vekens, 22-Jul-2018.) (Revised by AV, 5-Aug-2022.)
Assertion
Ref Expression
wlksnwwlknvbij ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → ∃𝑓 𝑓:{𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋})
Distinct variable groups:   𝑓,𝐺,𝑝,𝑤   𝑓,𝑁,𝑝,𝑤   𝑓,𝑋,𝑝,𝑤

Proof of Theorem wlksnwwlknvbij
Dummy variable 𝑞 is distinct from all other variables.
StepHypRef Expression
1 fvex 6789 . . . . 5 (Walks‘𝐺) ∈ V
21mptrabex 7103 . . . 4 (𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ∈ V
32resex 5941 . . 3 ((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}) ∈ V
4 eqid 2738 . . . 4 (𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) = (𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝))
5 eqid 2738 . . . . 5 {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} = {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁}
6 eqid 2738 . . . . 5 (𝑁 WWalksN 𝐺) = (𝑁 WWalksN 𝐺)
75, 6, 4wlknwwlksnbij 28250 . . . 4 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → (𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)):{𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁}–1-1-onto→(𝑁 WWalksN 𝐺))
8 fveq1 6775 . . . . . 6 (𝑤 = (2nd𝑝) → (𝑤‘0) = ((2nd𝑝)‘0))
98eqeq1d 2740 . . . . 5 (𝑤 = (2nd𝑝) → ((𝑤‘0) = 𝑋 ↔ ((2nd𝑝)‘0) = 𝑋))
1093ad2ant3 1134 . . . 4 (((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) ∧ 𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∧ 𝑤 = (2nd𝑝)) → ((𝑤‘0) = 𝑋 ↔ ((2nd𝑝)‘0) = 𝑋))
114, 7, 10f1oresrab 7001 . . 3 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → ((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}):{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋})
12 f1oeq1 6706 . . . 4 (𝑓 = ((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}) → (𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ↔ ((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}):{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}))
1312spcegv 3535 . . 3 (((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}) ∈ V → (((𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ↦ (2nd𝑝)) ↾ {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}):{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} → ∃𝑓 𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}))
143, 11, 13mpsyl 68 . 2 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → ∃𝑓 𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋})
15 2fveq3 6781 . . . . . . 7 (𝑝 = 𝑞 → (♯‘(1st𝑝)) = (♯‘(1st𝑞)))
1615eqeq1d 2740 . . . . . 6 (𝑝 = 𝑞 → ((♯‘(1st𝑝)) = 𝑁 ↔ (♯‘(1st𝑞)) = 𝑁))
1716rabrabi 3426 . . . . 5 {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋} = {𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}
1817eqcomi 2747 . . . 4 {𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)} = {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}
19 f1oeq2 6707 . . . 4 ({𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)} = {𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋} → (𝑓:{𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ↔ 𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}))
2018, 19mp1i 13 . . 3 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → (𝑓:{𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ↔ 𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}))
2120exbidv 1924 . 2 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → (∃𝑓 𝑓:{𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋} ↔ ∃𝑓 𝑓:{𝑝 ∈ {𝑞 ∈ (Walks‘𝐺) ∣ (♯‘(1st𝑞)) = 𝑁} ∣ ((2nd𝑝)‘0) = 𝑋}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋}))
2214, 21mpbird 256 1 ((𝐺 ∈ USPGraph ∧ 𝑁 ∈ ℕ0) → ∃𝑓 𝑓:{𝑝 ∈ (Walks‘𝐺) ∣ ((♯‘(1st𝑝)) = 𝑁 ∧ ((2nd𝑝)‘0) = 𝑋)}–1-1-onto→{𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑋})
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 396   = wceq 1539  wex 1782  wcel 2106  {crab 3068  Vcvv 3431  cmpt 5159  cres 5593  1-1-ontowf1o 6434  cfv 6435  (class class class)co 7277  1st c1st 7829  2nd c2nd 7830  0cc0 10869  0cn0 12231  chash 14042  USPGraphcuspgr 27516  Walkscwlks 27961   WWalksN cwwlksn 28188
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  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 2709  ax-rep 5211  ax-sep 5225  ax-nul 5232  ax-pow 5290  ax-pr 5354  ax-un 7588  ax-cnex 10925  ax-resscn 10926  ax-1cn 10927  ax-icn 10928  ax-addcl 10929  ax-addrcl 10930  ax-mulcl 10931  ax-mulrcl 10932  ax-mulcom 10933  ax-addass 10934  ax-mulass 10935  ax-distr 10936  ax-i2m1 10937  ax-1ne0 10938  ax-1rid 10939  ax-rnegex 10940  ax-rrecex 10941  ax-cnre 10942  ax-pre-lttri 10943  ax-pre-lttrn 10944  ax-pre-ltadd 10945  ax-pre-mulgt0 10946
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-ifp 1061  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1783  df-nf 1787  df-sb 2068  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2816  df-nfc 2889  df-ne 2944  df-nel 3050  df-ral 3069  df-rex 3070  df-reu 3072  df-rab 3073  df-v 3433  df-sbc 3718  df-csb 3834  df-dif 3891  df-un 3893  df-in 3895  df-ss 3905  df-pss 3907  df-nul 4259  df-if 4462  df-pw 4537  df-sn 4564  df-pr 4566  df-op 4570  df-uni 4842  df-int 4882  df-iun 4928  df-br 5077  df-opab 5139  df-mpt 5160  df-tr 5194  df-id 5491  df-eprel 5497  df-po 5505  df-so 5506  df-fr 5546  df-we 5548  df-xp 5597  df-rel 5598  df-cnv 5599  df-co 5600  df-dm 5601  df-rn 5602  df-res 5603  df-ima 5604  df-pred 6204  df-ord 6271  df-on 6272  df-lim 6273  df-suc 6274  df-iota 6393  df-fun 6437  df-fn 6438  df-f 6439  df-f1 6440  df-fo 6441  df-f1o 6442  df-fv 6443  df-riota 7234  df-ov 7280  df-oprab 7281  df-mpo 7282  df-om 7713  df-1st 7831  df-2nd 7832  df-frecs 8095  df-wrecs 8126  df-recs 8200  df-rdg 8239  df-1o 8295  df-2o 8296  df-oadd 8299  df-er 8496  df-map 8615  df-pm 8616  df-en 8732  df-dom 8733  df-sdom 8734  df-fin 8735  df-dju 9657  df-card 9695  df-pnf 11009  df-mnf 11010  df-xr 11011  df-ltxr 11012  df-le 11013  df-sub 11205  df-neg 11206  df-nn 11972  df-2 12034  df-n0 12232  df-xnn0 12304  df-z 12318  df-uz 12581  df-fz 13238  df-fzo 13381  df-hash 14043  df-word 14216  df-edg 27416  df-uhgr 27426  df-upgr 27450  df-uspgr 27518  df-wlks 27964  df-wwlks 28192  df-wwlksn 28193
This theorem is referenced by:  rusgrnumwlkg  28339
  Copyright terms: Public domain W3C validator