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

Theorem wspthsn 29878
Description: The set of simple paths of a fixed length as word. (Contributed by Alexander van der Vekens, 1-Mar-2018.) (Revised by AV, 11-May-2021.)
Assertion
Ref Expression
wspthsn (𝑁 WSPathsN 𝐺) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤}
Distinct variable groups:   𝑓,𝐺,𝑤   𝑤,𝑁
Allowed substitution hint:   𝑁(𝑓)

Proof of Theorem wspthsn
Dummy variables 𝑔 𝑛 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 oveq12 7440 . . . 4 ((𝑛 = 𝑁𝑔 = 𝐺) → (𝑛 WWalksN 𝑔) = (𝑁 WWalksN 𝐺))
2 fveq2 6907 . . . . . . 7 (𝑔 = 𝐺 → (SPaths‘𝑔) = (SPaths‘𝐺))
32breqd 5159 . . . . . 6 (𝑔 = 𝐺 → (𝑓(SPaths‘𝑔)𝑤𝑓(SPaths‘𝐺)𝑤))
43exbidv 1919 . . . . 5 (𝑔 = 𝐺 → (∃𝑓 𝑓(SPaths‘𝑔)𝑤 ↔ ∃𝑓 𝑓(SPaths‘𝐺)𝑤))
54adantl 481 . . . 4 ((𝑛 = 𝑁𝑔 = 𝐺) → (∃𝑓 𝑓(SPaths‘𝑔)𝑤 ↔ ∃𝑓 𝑓(SPaths‘𝐺)𝑤))
61, 5rabeqbidv 3452 . . 3 ((𝑛 = 𝑁𝑔 = 𝐺) → {𝑤 ∈ (𝑛 WWalksN 𝑔) ∣ ∃𝑓 𝑓(SPaths‘𝑔)𝑤} = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤})
7 df-wspthsn 29863 . . 3 WSPathsN = (𝑛 ∈ ℕ0, 𝑔 ∈ V ↦ {𝑤 ∈ (𝑛 WWalksN 𝑔) ∣ ∃𝑓 𝑓(SPaths‘𝑔)𝑤})
8 ovex 7464 . . . 4 (𝑁 WWalksN 𝐺) ∈ V
98rabex 5345 . . 3 {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤} ∈ V
106, 7, 9ovmpoa 7588 . 2 ((𝑁 ∈ ℕ0𝐺 ∈ V) → (𝑁 WSPathsN 𝐺) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤})
117mpondm0 7673 . . 3 (¬ (𝑁 ∈ ℕ0𝐺 ∈ V) → (𝑁 WSPathsN 𝐺) = ∅)
12 df-wwlksn 29861 . . . . . 6 WWalksN = (𝑛 ∈ ℕ0, 𝑔 ∈ V ↦ {𝑤 ∈ (WWalks‘𝑔) ∣ (♯‘𝑤) = (𝑛 + 1)})
1312mpondm0 7673 . . . . 5 (¬ (𝑁 ∈ ℕ0𝐺 ∈ V) → (𝑁 WWalksN 𝐺) = ∅)
1413rabeqdv 3449 . . . 4 (¬ (𝑁 ∈ ℕ0𝐺 ∈ V) → {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤} = {𝑤 ∈ ∅ ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤})
15 rab0 4392 . . . 4 {𝑤 ∈ ∅ ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤} = ∅
1614, 15eqtrdi 2791 . . 3 (¬ (𝑁 ∈ ℕ0𝐺 ∈ V) → {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤} = ∅)
1711, 16eqtr4d 2778 . 2 (¬ (𝑁 ∈ ℕ0𝐺 ∈ V) → (𝑁 WSPathsN 𝐺) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤})
1810, 17pm2.61i 182 1 (𝑁 WSPathsN 𝐺) = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ ∃𝑓 𝑓(SPaths‘𝐺)𝑤}
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wb 206  wa 395   = wceq 1537  wex 1776  wcel 2106  {crab 3433  Vcvv 3478  c0 4339   class class class wbr 5148  cfv 6563  (class class class)co 7431  1c1 11154   + caddc 11156  0cn0 12524  chash 14366  SPathscspths 29746  WWalkscwwlks 29855   WWalksN cwwlksn 29856   WSPathsN cwwspthsn 29858
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1792  ax-4 1806  ax-5 1908  ax-6 1965  ax-7 2005  ax-8 2108  ax-9 2116  ax-10 2139  ax-11 2155  ax-12 2175  ax-ext 2706  ax-sep 5302  ax-nul 5312  ax-pr 5438
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3an 1088  df-tru 1540  df-fal 1550  df-ex 1777  df-nf 1781  df-sb 2063  df-mo 2538  df-eu 2567  df-clab 2713  df-cleq 2727  df-clel 2814  df-nfc 2890  df-ne 2939  df-ral 3060  df-rex 3069  df-rab 3434  df-v 3480  df-sbc 3792  df-dif 3966  df-un 3968  df-in 3970  df-ss 3980  df-nul 4340  df-if 4532  df-pw 4607  df-sn 4632  df-pr 4634  df-op 4638  df-uni 4913  df-br 5149  df-opab 5211  df-id 5583  df-xp 5695  df-rel 5696  df-cnv 5697  df-co 5698  df-dm 5699  df-iota 6516  df-fun 6565  df-fv 6571  df-ov 7434  df-oprab 7435  df-mpo 7436  df-wwlksn 29861  df-wspthsn 29863
This theorem is referenced by:  iswspthn  29879  wspn0  29954
  Copyright terms: Public domain W3C validator