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

Theorem r1tr 9251
 Description: The cumulative hierarchy of sets is transitive. Lemma 7T of [Enderton] p. 202. (Contributed by NM, 8-Sep-2003.) (Revised by Mario Carneiro, 16-Nov-2014.)
Assertion
Ref Expression
r1tr Tr (𝑅1𝐴)

Proof of Theorem r1tr
Dummy variables 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 r1funlim 9241 . . . . . 6 (Fun 𝑅1 ∧ Lim dom 𝑅1)
21simpri 489 . . . . 5 Lim dom 𝑅1
3 limord 6233 . . . . 5 (Lim dom 𝑅1 → Ord dom 𝑅1)
4 ordsson 7509 . . . . 5 (Ord dom 𝑅1 → dom 𝑅1 ⊆ On)
52, 3, 4mp2b 10 . . . 4 dom 𝑅1 ⊆ On
65sseli 3890 . . 3 (𝐴 ∈ dom 𝑅1𝐴 ∈ On)
7 fveq2 6663 . . . . . 6 (𝑥 = ∅ → (𝑅1𝑥) = (𝑅1‘∅))
8 r10 9243 . . . . . 6 (𝑅1‘∅) = ∅
97, 8eqtrdi 2809 . . . . 5 (𝑥 = ∅ → (𝑅1𝑥) = ∅)
10 treq 5148 . . . . 5 ((𝑅1𝑥) = ∅ → (Tr (𝑅1𝑥) ↔ Tr ∅))
119, 10syl 17 . . . 4 (𝑥 = ∅ → (Tr (𝑅1𝑥) ↔ Tr ∅))
12 fveq2 6663 . . . . 5 (𝑥 = 𝑦 → (𝑅1𝑥) = (𝑅1𝑦))
13 treq 5148 . . . . 5 ((𝑅1𝑥) = (𝑅1𝑦) → (Tr (𝑅1𝑥) ↔ Tr (𝑅1𝑦)))
1412, 13syl 17 . . . 4 (𝑥 = 𝑦 → (Tr (𝑅1𝑥) ↔ Tr (𝑅1𝑦)))
15 fveq2 6663 . . . . 5 (𝑥 = suc 𝑦 → (𝑅1𝑥) = (𝑅1‘suc 𝑦))
16 treq 5148 . . . . 5 ((𝑅1𝑥) = (𝑅1‘suc 𝑦) → (Tr (𝑅1𝑥) ↔ Tr (𝑅1‘suc 𝑦)))
1715, 16syl 17 . . . 4 (𝑥 = suc 𝑦 → (Tr (𝑅1𝑥) ↔ Tr (𝑅1‘suc 𝑦)))
18 fveq2 6663 . . . . 5 (𝑥 = 𝐴 → (𝑅1𝑥) = (𝑅1𝐴))
19 treq 5148 . . . . 5 ((𝑅1𝑥) = (𝑅1𝐴) → (Tr (𝑅1𝑥) ↔ Tr (𝑅1𝐴)))
2018, 19syl 17 . . . 4 (𝑥 = 𝐴 → (Tr (𝑅1𝑥) ↔ Tr (𝑅1𝐴)))
21 tr0 5153 . . . 4 Tr ∅
22 limsuc 7569 . . . . . . . 8 (Lim dom 𝑅1 → (𝑦 ∈ dom 𝑅1 ↔ suc 𝑦 ∈ dom 𝑅1))
232, 22ax-mp 5 . . . . . . 7 (𝑦 ∈ dom 𝑅1 ↔ suc 𝑦 ∈ dom 𝑅1)
24 simpr 488 . . . . . . . . 9 ((𝑦 ∈ On ∧ Tr (𝑅1𝑦)) → Tr (𝑅1𝑦))
25 pwtr 5317 . . . . . . . . 9 (Tr (𝑅1𝑦) ↔ Tr 𝒫 (𝑅1𝑦))
2624, 25sylib 221 . . . . . . . 8 ((𝑦 ∈ On ∧ Tr (𝑅1𝑦)) → Tr 𝒫 (𝑅1𝑦))
27 r1sucg 9244 . . . . . . . . 9 (𝑦 ∈ dom 𝑅1 → (𝑅1‘suc 𝑦) = 𝒫 (𝑅1𝑦))
28 treq 5148 . . . . . . . . 9 ((𝑅1‘suc 𝑦) = 𝒫 (𝑅1𝑦) → (Tr (𝑅1‘suc 𝑦) ↔ Tr 𝒫 (𝑅1𝑦)))
2927, 28syl 17 . . . . . . . 8 (𝑦 ∈ dom 𝑅1 → (Tr (𝑅1‘suc 𝑦) ↔ Tr 𝒫 (𝑅1𝑦)))
3026, 29syl5ibrcom 250 . . . . . . 7 ((𝑦 ∈ On ∧ Tr (𝑅1𝑦)) → (𝑦 ∈ dom 𝑅1 → Tr (𝑅1‘suc 𝑦)))
3123, 30syl5bir 246 . . . . . 6 ((𝑦 ∈ On ∧ Tr (𝑅1𝑦)) → (suc 𝑦 ∈ dom 𝑅1 → Tr (𝑅1‘suc 𝑦)))
32 ndmfv 6693 . . . . . . . 8 (¬ suc 𝑦 ∈ dom 𝑅1 → (𝑅1‘suc 𝑦) = ∅)
33 treq 5148 . . . . . . . 8 ((𝑅1‘suc 𝑦) = ∅ → (Tr (𝑅1‘suc 𝑦) ↔ Tr ∅))
3432, 33syl 17 . . . . . . 7 (¬ suc 𝑦 ∈ dom 𝑅1 → (Tr (𝑅1‘suc 𝑦) ↔ Tr ∅))
3521, 34mpbiri 261 . . . . . 6 (¬ suc 𝑦 ∈ dom 𝑅1 → Tr (𝑅1‘suc 𝑦))
3631, 35pm2.61d1 183 . . . . 5 ((𝑦 ∈ On ∧ Tr (𝑅1𝑦)) → Tr (𝑅1‘suc 𝑦))
3736ex 416 . . . 4 (𝑦 ∈ On → (Tr (𝑅1𝑦) → Tr (𝑅1‘suc 𝑦)))
38 triun 5155 . . . . . . . 8 (∀𝑦𝑥 Tr (𝑅1𝑦) → Tr 𝑦𝑥 (𝑅1𝑦))
39 r1limg 9246 . . . . . . . . . 10 ((𝑥 ∈ dom 𝑅1 ∧ Lim 𝑥) → (𝑅1𝑥) = 𝑦𝑥 (𝑅1𝑦))
4039ancoms 462 . . . . . . . . 9 ((Lim 𝑥𝑥 ∈ dom 𝑅1) → (𝑅1𝑥) = 𝑦𝑥 (𝑅1𝑦))
41 treq 5148 . . . . . . . . 9 ((𝑅1𝑥) = 𝑦𝑥 (𝑅1𝑦) → (Tr (𝑅1𝑥) ↔ Tr 𝑦𝑥 (𝑅1𝑦)))
4240, 41syl 17 . . . . . . . 8 ((Lim 𝑥𝑥 ∈ dom 𝑅1) → (Tr (𝑅1𝑥) ↔ Tr 𝑦𝑥 (𝑅1𝑦)))
4338, 42syl5ibr 249 . . . . . . 7 ((Lim 𝑥𝑥 ∈ dom 𝑅1) → (∀𝑦𝑥 Tr (𝑅1𝑦) → Tr (𝑅1𝑥)))
4443impancom 455 . . . . . 6 ((Lim 𝑥 ∧ ∀𝑦𝑥 Tr (𝑅1𝑦)) → (𝑥 ∈ dom 𝑅1 → Tr (𝑅1𝑥)))
45 ndmfv 6693 . . . . . . . 8 𝑥 ∈ dom 𝑅1 → (𝑅1𝑥) = ∅)
4645, 10syl 17 . . . . . . 7 𝑥 ∈ dom 𝑅1 → (Tr (𝑅1𝑥) ↔ Tr ∅))
4721, 46mpbiri 261 . . . . . 6 𝑥 ∈ dom 𝑅1 → Tr (𝑅1𝑥))
4844, 47pm2.61d1 183 . . . . 5 ((Lim 𝑥 ∧ ∀𝑦𝑥 Tr (𝑅1𝑦)) → Tr (𝑅1𝑥))
4948ex 416 . . . 4 (Lim 𝑥 → (∀𝑦𝑥 Tr (𝑅1𝑦) → Tr (𝑅1𝑥)))
5011, 14, 17, 20, 21, 37, 49tfinds 7579 . . 3 (𝐴 ∈ On → Tr (𝑅1𝐴))
516, 50syl 17 . 2 (𝐴 ∈ dom 𝑅1 → Tr (𝑅1𝐴))
52 ndmfv 6693 . . . 4 𝐴 ∈ dom 𝑅1 → (𝑅1𝐴) = ∅)
53 treq 5148 . . . 4 ((𝑅1𝐴) = ∅ → (Tr (𝑅1𝐴) ↔ Tr ∅))
5452, 53syl 17 . . 3 𝐴 ∈ dom 𝑅1 → (Tr (𝑅1𝐴) ↔ Tr ∅))
5521, 54mpbiri 261 . 2 𝐴 ∈ dom 𝑅1 → Tr (𝑅1𝐴))
5651, 55pm2.61i 185 1 Tr (𝑅1𝐴)
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   ↔ wb 209   ∧ wa 399   = wceq 1538   ∈ wcel 2111  ∀wral 3070   ⊆ wss 3860  ∅c0 4227  𝒫 cpw 4497  ∪ ciun 4886  Tr wtr 5142  dom cdm 5528  Ord word 6173  Oncon0 6174  Lim wlim 6175  suc csuc 6176  Fun wfun 6334  ‘cfv 6340  𝑅1cr1 9237 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2113  ax-9 2121  ax-10 2142  ax-11 2158  ax-12 2175  ax-ext 2729  ax-sep 5173  ax-nul 5180  ax-pow 5238  ax-pr 5302  ax-un 7465 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-fal 1551  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2557  df-eu 2588  df-clab 2736  df-cleq 2750  df-clel 2830  df-nfc 2901  df-ne 2952  df-ral 3075  df-rex 3076  df-reu 3077  df-rab 3079  df-v 3411  df-sbc 3699  df-csb 3808  df-dif 3863  df-un 3865  df-in 3867  df-ss 3877  df-pss 3879  df-nul 4228  df-if 4424  df-pw 4499  df-sn 4526  df-pr 4528  df-tp 4530  df-op 4532  df-uni 4802  df-iun 4888  df-br 5037  df-opab 5099  df-mpt 5117  df-tr 5143  df-id 5434  df-eprel 5439  df-po 5447  df-so 5448  df-fr 5487  df-we 5489  df-xp 5534  df-rel 5535  df-cnv 5536  df-co 5537  df-dm 5538  df-rn 5539  df-res 5540  df-ima 5541  df-pred 6131  df-ord 6177  df-on 6178  df-lim 6179  df-suc 6180  df-iota 6299  df-fun 6342  df-fn 6343  df-f 6344  df-f1 6345  df-fo 6346  df-f1o 6347  df-fv 6348  df-om 7586  df-wrecs 7963  df-recs 8024  df-rdg 8062  df-r1 9239 This theorem is referenced by:  r1tr2  9252  r1ordg  9253  r1ord3g  9254  r1ord2  9256  r1sssuc  9258  r1pwss  9259  r1val1  9261  rankwflemb  9268  r1elwf  9271  r1elssi  9280  uniwf  9294  tcrank  9359  ackbij2lem3  9714  r1limwun  10209  tskr1om2  10241  inagrud  41422
 Copyright terms: Public domain W3C validator