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

Theorem brttrcl2 9442
Description: Characterization of elements of the transitive closure of a relation. (Contributed by Scott Fenton, 24-Aug-2024.)
Assertion
Ref Expression
brttrcl2 (𝐴t++𝑅𝐵 ↔ ∃𝑛 ∈ ω ∃𝑓(𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
Distinct variable groups:   𝐴,𝑛,𝑓,𝑎   𝐵,𝑛,𝑓,𝑎   𝑅,𝑛,𝑓,𝑎

Proof of Theorem brttrcl2
Dummy variable 𝑚 is distinct from all other variables.
StepHypRef Expression
1 brttrcl 9441 . 2 (𝐴t++𝑅𝐵 ↔ ∃𝑚 ∈ (ω ∖ 1o)∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
2 df-1o 8282 . . . . . . . . 9 1o = suc ∅
32difeq2i 4059 . . . . . . . 8 (ω ∖ 1o) = (ω ∖ suc ∅)
43eleq2i 2832 . . . . . . 7 (𝑚 ∈ (ω ∖ 1o) ↔ 𝑚 ∈ (ω ∖ suc ∅))
5 peano1 7724 . . . . . . . 8 ∅ ∈ ω
6 eldifsucnn 8469 . . . . . . . 8 (∅ ∈ ω → (𝑚 ∈ (ω ∖ suc ∅) ↔ ∃𝑛 ∈ (ω ∖ ∅)𝑚 = suc 𝑛))
75, 6ax-mp 5 . . . . . . 7 (𝑚 ∈ (ω ∖ suc ∅) ↔ ∃𝑛 ∈ (ω ∖ ∅)𝑚 = suc 𝑛)
8 dif0 4312 . . . . . . . 8 (ω ∖ ∅) = ω
98rexeqi 3346 . . . . . . 7 (∃𝑛 ∈ (ω ∖ ∅)𝑚 = suc 𝑛 ↔ ∃𝑛 ∈ ω 𝑚 = suc 𝑛)
104, 7, 93bitri 297 . . . . . 6 (𝑚 ∈ (ω ∖ 1o) ↔ ∃𝑛 ∈ ω 𝑚 = suc 𝑛)
1110anbi1i 624 . . . . 5 ((𝑚 ∈ (ω ∖ 1o) ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ (∃𝑛 ∈ ω 𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
12 r19.41v 3276 . . . . 5 (∃𝑛 ∈ ω (𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ (∃𝑛 ∈ ω 𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
1311, 12bitr4i 277 . . . 4 ((𝑚 ∈ (ω ∖ 1o) ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ ∃𝑛 ∈ ω (𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
1413exbii 1854 . . 3 (∃𝑚(𝑚 ∈ (ω ∖ 1o) ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ ∃𝑚𝑛 ∈ ω (𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
15 df-rex 3072 . . 3 (∃𝑚 ∈ (ω ∖ 1o)∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎)) ↔ ∃𝑚(𝑚 ∈ (ω ∖ 1o) ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
16 rexcom4 3182 . . 3 (∃𝑛 ∈ ω ∃𝑚(𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ ∃𝑚𝑛 ∈ ω (𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
1714, 15, 163bitr4i 303 . 2 (∃𝑚 ∈ (ω ∖ 1o)∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎)) ↔ ∃𝑛 ∈ ω ∃𝑚(𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
18 vex 3435 . . . . 5 𝑛 ∈ V
1918sucex 7647 . . . 4 suc 𝑛 ∈ V
20 suceq 6329 . . . . . . 7 (𝑚 = suc 𝑛 → suc 𝑚 = suc suc 𝑛)
2120fneq2d 6524 . . . . . 6 (𝑚 = suc 𝑛 → (𝑓 Fn suc 𝑚𝑓 Fn suc suc 𝑛))
22 fveqeq2 6778 . . . . . . 7 (𝑚 = suc 𝑛 → ((𝑓𝑚) = 𝐵 ↔ (𝑓‘suc 𝑛) = 𝐵))
2322anbi2d 629 . . . . . 6 (𝑚 = suc 𝑛 → (((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ↔ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵)))
24 raleq 3341 . . . . . 6 (𝑚 = suc 𝑛 → (∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎) ↔ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
2521, 23, 243anbi123d 1435 . . . . 5 (𝑚 = suc 𝑛 → ((𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎)) ↔ (𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
2625exbidv 1928 . . . 4 (𝑚 = suc 𝑛 → (∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎)) ↔ ∃𝑓(𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎))))
2719, 26ceqsexv 3478 . . 3 (∃𝑚(𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ ∃𝑓(𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
2827rexbii 3180 . 2 (∃𝑛 ∈ ω ∃𝑚(𝑚 = suc 𝑛 ∧ ∃𝑓(𝑓 Fn suc 𝑚 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓𝑚) = 𝐵) ∧ ∀𝑎𝑚 (𝑓𝑎)𝑅(𝑓‘suc 𝑎))) ↔ ∃𝑛 ∈ ω ∃𝑓(𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
291, 17, 283bitri 297 1 (𝐴t++𝑅𝐵 ↔ ∃𝑛 ∈ ω ∃𝑓(𝑓 Fn suc suc 𝑛 ∧ ((𝑓‘∅) = 𝐴 ∧ (𝑓‘suc 𝑛) = 𝐵) ∧ ∀𝑎 ∈ suc 𝑛(𝑓𝑎)𝑅(𝑓‘suc 𝑎)))
Colors of variables: wff setvar class
Syntax hints:  wb 205  wa 396  w3a 1086   = wceq 1542  wex 1786  wcel 2110  wral 3066  wrex 3067  cdif 3889  c0 4262   class class class wbr 5079  suc csuc 6266   Fn wfn 6426  cfv 6431  ωcom 7701  1oc1o 8275  t++cttrcl 9435
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1917  ax-6 1975  ax-7 2015  ax-8 2112  ax-9 2120  ax-10 2141  ax-11 2158  ax-12 2175  ax-ext 2711  ax-sep 5227  ax-nul 5234  ax-pr 5356  ax-un 7580
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1545  df-fal 1555  df-ex 1787  df-nf 1791  df-sb 2072  df-mo 2542  df-eu 2571  df-clab 2718  df-cleq 2732  df-clel 2818  df-nfc 2891  df-ne 2946  df-ral 3071  df-rex 3072  df-reu 3073  df-rab 3075  df-v 3433  df-sbc 3721  df-csb 3838  df-dif 3895  df-un 3897  df-in 3899  df-ss 3909  df-pss 3911  df-nul 4263  df-if 4466  df-pw 4541  df-sn 4568  df-pr 4570  df-tp 4572  df-op 4574  df-uni 4846  df-int 4886  df-iun 4932  df-br 5080  df-opab 5142  df-mpt 5163  df-tr 5197  df-id 5489  df-eprel 5495  df-po 5503  df-so 5504  df-fr 5544  df-we 5546  df-xp 5595  df-rel 5596  df-cnv 5597  df-co 5598  df-dm 5599  df-rn 5600  df-res 5601  df-ima 5602  df-pred 6200  df-ord 6267  df-on 6268  df-lim 6269  df-suc 6270  df-iota 6389  df-fun 6433  df-fn 6434  df-f 6435  df-f1 6436  df-fo 6437  df-f1o 6438  df-fv 6439  df-ov 7272  df-oprab 7273  df-mpo 7274  df-om 7702  df-2nd 7819  df-frecs 8082  df-wrecs 8113  df-recs 8187  df-rdg 8226  df-1o 8282  df-oadd 8286  df-ttrcl 9436
This theorem is referenced by:  ttrclss  9448  ttrclse  9455
  Copyright terms: Public domain W3C validator