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

Theorem clwlkclwwlken 27166
Description: The set of the nonempty closed walks and the set of closed walks as word are equinumerous in a simple pseudograph. (Contributed by AV, 25-May-2022.)
Assertion
Ref Expression
clwlkclwwlken (𝐺 ∈ USPGraph → {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ≈ (ClWWalks‘𝐺))
Distinct variable group:   𝑤,𝐺

Proof of Theorem clwlkclwwlken
Dummy variables 𝑐 𝑑 𝑢 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fvex 6341 . . 3 (ClWalks‘𝐺) ∈ V
21rabex 4942 . 2 {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ∈ V
3 fvex 6341 . 2 (ClWWalks‘𝐺) ∈ V
4 fveq2 6331 . . . . . 6 (𝑤 = 𝑢 → (1st𝑤) = (1st𝑢))
54fveq2d 6335 . . . . 5 (𝑤 = 𝑢 → (♯‘(1st𝑤)) = (♯‘(1st𝑢)))
65breq2d 4795 . . . 4 (𝑤 = 𝑢 → (1 ≤ (♯‘(1st𝑤)) ↔ 1 ≤ (♯‘(1st𝑢))))
76cbvrabv 3347 . . 3 {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} = {𝑢 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑢))}
8 fveq2 6331 . . . . 5 (𝑑 = 𝑐 → (2nd𝑑) = (2nd𝑐))
98fveq2d 6335 . . . . . . 7 (𝑑 = 𝑐 → (♯‘(2nd𝑑)) = (♯‘(2nd𝑐)))
109oveq1d 6806 . . . . . 6 (𝑑 = 𝑐 → ((♯‘(2nd𝑑)) − 1) = ((♯‘(2nd𝑐)) − 1))
1110opeq2d 4543 . . . . 5 (𝑑 = 𝑐 → ⟨0, ((♯‘(2nd𝑑)) − 1)⟩ = ⟨0, ((♯‘(2nd𝑐)) − 1)⟩)
128, 11oveq12d 6809 . . . 4 (𝑑 = 𝑐 → ((2nd𝑑) substr ⟨0, ((♯‘(2nd𝑑)) − 1)⟩) = ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩))
1312cbvmptv 4881 . . 3 (𝑑 ∈ {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ↦ ((2nd𝑑) substr ⟨0, ((♯‘(2nd𝑑)) − 1)⟩)) = (𝑐 ∈ {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ↦ ((2nd𝑐) substr ⟨0, ((♯‘(2nd𝑐)) − 1)⟩))
147, 13clwlkclwwlkf1o 27165 . 2 (𝐺 ∈ USPGraph → (𝑑 ∈ {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ↦ ((2nd𝑑) substr ⟨0, ((♯‘(2nd𝑑)) − 1)⟩)):{𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))}–1-1-onto→(ClWWalks‘𝐺))
15 f1oen2g 8124 . 2 (({𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ∈ V ∧ (ClWWalks‘𝐺) ∈ V ∧ (𝑑 ∈ {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ↦ ((2nd𝑑) substr ⟨0, ((♯‘(2nd𝑑)) − 1)⟩)):{𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))}–1-1-onto→(ClWWalks‘𝐺)) → {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ≈ (ClWWalks‘𝐺))
162, 3, 14, 15mp3an12i 1574 1 (𝐺 ∈ USPGraph → {𝑤 ∈ (ClWalks‘𝐺) ∣ 1 ≤ (♯‘(1st𝑤))} ≈ (ClWWalks‘𝐺))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wcel 2143  {crab 3063  Vcvv 3348  cop 4319   class class class wbr 4783  cmpt 4860  1-1-ontowf1o 6029  cfv 6030  (class class class)co 6791  1st c1st 7311  2nd c2nd 7312  cen 8104  0cc0 10136  1c1 10137  cle 10275  cmin 10466  chash 13324   substr csubstr 13494  USPGraphcuspgr 26271  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-rp 12035  df-fz 12533  df-fzo 12673  df-hash 13325  df-word 13498  df-lsw 13499  df-concat 13500  df-s1 13501  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: (None)
  Copyright terms: Public domain W3C validator