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

Theorem trcl 9148
Description: For any set 𝐴, show the properties of its transitive closure 𝐶. Similar to Theorem 9.1 of [TakeutiZaring] p. 73 except that we show an explicit expression for the transitive closure rather than just its existence. See tz9.1 9149 for an abbreviated version showing existence. (Contributed by NM, 14-Sep-2003.) (Revised by Mario Carneiro, 11-Sep-2015.)
Hypotheses
Ref Expression
trcl.1 𝐴 ∈ V
trcl.2 𝐹 = (rec((𝑧 ∈ V ↦ (𝑧 𝑧)), 𝐴) ↾ ω)
trcl.3 𝐶 = 𝑦 ∈ ω (𝐹𝑦)
Assertion
Ref Expression
trcl (𝐴𝐶 ∧ Tr 𝐶 ∧ ∀𝑥((𝐴𝑥 ∧ Tr 𝑥) → 𝐶𝑥))
Distinct variable groups:   𝑥,𝑧   𝑥,𝑦,𝐴   𝑥,𝐹,𝑦
Allowed substitution hints:   𝐴(𝑧)   𝐶(𝑥,𝑦,𝑧)   𝐹(𝑧)

Proof of Theorem trcl
Dummy variables 𝑣 𝑢 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 peano1 7579 . . . . 5 ∅ ∈ ω
2 trcl.2 . . . . . . . 8 𝐹 = (rec((𝑧 ∈ V ↦ (𝑧 𝑧)), 𝐴) ↾ ω)
32fveq1i 6647 . . . . . . 7 (𝐹‘∅) = ((rec((𝑧 ∈ V ↦ (𝑧 𝑧)), 𝐴) ↾ ω)‘∅)
4 trcl.1 . . . . . . . 8 𝐴 ∈ V
5 fr0g 8049 . . . . . . . 8 (𝐴 ∈ V → ((rec((𝑧 ∈ V ↦ (𝑧 𝑧)), 𝐴) ↾ ω)‘∅) = 𝐴)
64, 5ax-mp 5 . . . . . . 7 ((rec((𝑧 ∈ V ↦ (𝑧 𝑧)), 𝐴) ↾ ω)‘∅) = 𝐴
73, 6eqtr2i 2844 . . . . . 6 𝐴 = (𝐹‘∅)
87eqimssi 4004 . . . . 5 𝐴 ⊆ (𝐹‘∅)
9 fveq2 6646 . . . . . . 7 (𝑦 = ∅ → (𝐹𝑦) = (𝐹‘∅))
109sseq2d 3978 . . . . . 6 (𝑦 = ∅ → (𝐴 ⊆ (𝐹𝑦) ↔ 𝐴 ⊆ (𝐹‘∅)))
1110rspcev 3602 . . . . 5 ((∅ ∈ ω ∧ 𝐴 ⊆ (𝐹‘∅)) → ∃𝑦 ∈ ω 𝐴 ⊆ (𝐹𝑦))
121, 8, 11mp2an 690 . . . 4 𝑦 ∈ ω 𝐴 ⊆ (𝐹𝑦)
13 ssiun 4946 . . . 4 (∃𝑦 ∈ ω 𝐴 ⊆ (𝐹𝑦) → 𝐴 𝑦 ∈ ω (𝐹𝑦))
1412, 13ax-mp 5 . . 3 𝐴 𝑦 ∈ ω (𝐹𝑦)
15 trcl.3 . . 3 𝐶 = 𝑦 ∈ ω (𝐹𝑦)
1614, 15sseqtrri 3983 . 2 𝐴𝐶
17 dftr2 5150 . . . 4 (Tr 𝑦 ∈ ω (𝐹𝑦) ↔ ∀𝑣𝑢((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) → 𝑣 𝑦 ∈ ω (𝐹𝑦)))
18 eliun 4899 . . . . . . . . 9 (𝑢 𝑦 ∈ ω (𝐹𝑦) ↔ ∃𝑦 ∈ ω 𝑢 ∈ (𝐹𝑦))
1918anbi2i 624 . . . . . . . 8 ((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) ↔ (𝑣𝑢 ∧ ∃𝑦 ∈ ω 𝑢 ∈ (𝐹𝑦)))
20 r19.42v 3337 . . . . . . . 8 (∃𝑦 ∈ ω (𝑣𝑢𝑢 ∈ (𝐹𝑦)) ↔ (𝑣𝑢 ∧ ∃𝑦 ∈ ω 𝑢 ∈ (𝐹𝑦)))
2119, 20bitr4i 280 . . . . . . 7 ((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) ↔ ∃𝑦 ∈ ω (𝑣𝑢𝑢 ∈ (𝐹𝑦)))
22 elunii 4819 . . . . . . . . 9 ((𝑣𝑢𝑢 ∈ (𝐹𝑦)) → 𝑣 (𝐹𝑦))
23 ssun2 4128 . . . . . . . . . . 11 (𝐹𝑦) ⊆ ((𝐹𝑦) ∪ (𝐹𝑦))
24 fvex 6659 . . . . . . . . . . . . 13 (𝐹𝑦) ∈ V
2524uniex 7445 . . . . . . . . . . . . 13 (𝐹𝑦) ∈ V
2624, 25unex 7447 . . . . . . . . . . . 12 ((𝐹𝑦) ∪ (𝐹𝑦)) ∈ V
27 id 22 . . . . . . . . . . . . . 14 (𝑥 = 𝑧𝑥 = 𝑧)
28 unieq 4825 . . . . . . . . . . . . . 14 (𝑥 = 𝑧 𝑥 = 𝑧)
2927, 28uneq12d 4119 . . . . . . . . . . . . 13 (𝑥 = 𝑧 → (𝑥 𝑥) = (𝑧 𝑧))
30 id 22 . . . . . . . . . . . . . 14 (𝑥 = (𝐹𝑦) → 𝑥 = (𝐹𝑦))
31 unieq 4825 . . . . . . . . . . . . . 14 (𝑥 = (𝐹𝑦) → 𝑥 = (𝐹𝑦))
3230, 31uneq12d 4119 . . . . . . . . . . . . 13 (𝑥 = (𝐹𝑦) → (𝑥 𝑥) = ((𝐹𝑦) ∪ (𝐹𝑦)))
332, 29, 32frsucmpt2w 8053 . . . . . . . . . . . 12 ((𝑦 ∈ ω ∧ ((𝐹𝑦) ∪ (𝐹𝑦)) ∈ V) → (𝐹‘suc 𝑦) = ((𝐹𝑦) ∪ (𝐹𝑦)))
3426, 33mpan2 689 . . . . . . . . . . 11 (𝑦 ∈ ω → (𝐹‘suc 𝑦) = ((𝐹𝑦) ∪ (𝐹𝑦)))
3523, 34sseqtrrid 3999 . . . . . . . . . 10 (𝑦 ∈ ω → (𝐹𝑦) ⊆ (𝐹‘suc 𝑦))
3635sseld 3945 . . . . . . . . 9 (𝑦 ∈ ω → (𝑣 (𝐹𝑦) → 𝑣 ∈ (𝐹‘suc 𝑦)))
3722, 36syl5 34 . . . . . . . 8 (𝑦 ∈ ω → ((𝑣𝑢𝑢 ∈ (𝐹𝑦)) → 𝑣 ∈ (𝐹‘suc 𝑦)))
3837reximia 3229 . . . . . . 7 (∃𝑦 ∈ ω (𝑣𝑢𝑢 ∈ (𝐹𝑦)) → ∃𝑦 ∈ ω 𝑣 ∈ (𝐹‘suc 𝑦))
3921, 38sylbi 219 . . . . . 6 ((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) → ∃𝑦 ∈ ω 𝑣 ∈ (𝐹‘suc 𝑦))
40 peano2 7580 . . . . . . . . . 10 (𝑦 ∈ ω → suc 𝑦 ∈ ω)
41 fveq2 6646 . . . . . . . . . . . . 13 (𝑢 = suc 𝑦 → (𝐹𝑢) = (𝐹‘suc 𝑦))
4241eleq2d 2896 . . . . . . . . . . . 12 (𝑢 = suc 𝑦 → (𝑣 ∈ (𝐹𝑢) ↔ 𝑣 ∈ (𝐹‘suc 𝑦)))
4342rspcev 3602 . . . . . . . . . . 11 ((suc 𝑦 ∈ ω ∧ 𝑣 ∈ (𝐹‘suc 𝑦)) → ∃𝑢 ∈ ω 𝑣 ∈ (𝐹𝑢))
4443ex 415 . . . . . . . . . 10 (suc 𝑦 ∈ ω → (𝑣 ∈ (𝐹‘suc 𝑦) → ∃𝑢 ∈ ω 𝑣 ∈ (𝐹𝑢)))
4540, 44syl 17 . . . . . . . . 9 (𝑦 ∈ ω → (𝑣 ∈ (𝐹‘suc 𝑦) → ∃𝑢 ∈ ω 𝑣 ∈ (𝐹𝑢)))
4645rexlimiv 3267 . . . . . . . 8 (∃𝑦 ∈ ω 𝑣 ∈ (𝐹‘suc 𝑦) → ∃𝑢 ∈ ω 𝑣 ∈ (𝐹𝑢))
47 fveq2 6646 . . . . . . . . . 10 (𝑦 = 𝑢 → (𝐹𝑦) = (𝐹𝑢))
4847eleq2d 2896 . . . . . . . . 9 (𝑦 = 𝑢 → (𝑣 ∈ (𝐹𝑦) ↔ 𝑣 ∈ (𝐹𝑢)))
4948cbvrexvw 3429 . . . . . . . 8 (∃𝑦 ∈ ω 𝑣 ∈ (𝐹𝑦) ↔ ∃𝑢 ∈ ω 𝑣 ∈ (𝐹𝑢))
5046, 49sylibr 236 . . . . . . 7 (∃𝑦 ∈ ω 𝑣 ∈ (𝐹‘suc 𝑦) → ∃𝑦 ∈ ω 𝑣 ∈ (𝐹𝑦))
51 eliun 4899 . . . . . . 7 (𝑣 𝑦 ∈ ω (𝐹𝑦) ↔ ∃𝑦 ∈ ω 𝑣 ∈ (𝐹𝑦))
5250, 51sylibr 236 . . . . . 6 (∃𝑦 ∈ ω 𝑣 ∈ (𝐹‘suc 𝑦) → 𝑣 𝑦 ∈ ω (𝐹𝑦))
5339, 52syl 17 . . . . 5 ((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) → 𝑣 𝑦 ∈ ω (𝐹𝑦))
5453ax-gen 1796 . . . 4 𝑢((𝑣𝑢𝑢 𝑦 ∈ ω (𝐹𝑦)) → 𝑣 𝑦 ∈ ω (𝐹𝑦))
5517, 54mpgbir 1800 . . 3 Tr 𝑦 ∈ ω (𝐹𝑦)
56 treq 5154 . . . 4 (𝐶 = 𝑦 ∈ ω (𝐹𝑦) → (Tr 𝐶 ↔ Tr 𝑦 ∈ ω (𝐹𝑦)))
5715, 56ax-mp 5 . . 3 (Tr 𝐶 ↔ Tr 𝑦 ∈ ω (𝐹𝑦))
5855, 57mpbir 233 . 2 Tr 𝐶
59 fveq2 6646 . . . . . . . 8 (𝑣 = ∅ → (𝐹𝑣) = (𝐹‘∅))
6059sseq1d 3977 . . . . . . 7 (𝑣 = ∅ → ((𝐹𝑣) ⊆ 𝑥 ↔ (𝐹‘∅) ⊆ 𝑥))
61 fveq2 6646 . . . . . . . 8 (𝑣 = 𝑦 → (𝐹𝑣) = (𝐹𝑦))
6261sseq1d 3977 . . . . . . 7 (𝑣 = 𝑦 → ((𝐹𝑣) ⊆ 𝑥 ↔ (𝐹𝑦) ⊆ 𝑥))
63 fveq2 6646 . . . . . . . 8 (𝑣 = suc 𝑦 → (𝐹𝑣) = (𝐹‘suc 𝑦))
6463sseq1d 3977 . . . . . . 7 (𝑣 = suc 𝑦 → ((𝐹𝑣) ⊆ 𝑥 ↔ (𝐹‘suc 𝑦) ⊆ 𝑥))
653, 6eqtri 2843 . . . . . . . . . 10 (𝐹‘∅) = 𝐴
6665sseq1i 3974 . . . . . . . . 9 ((𝐹‘∅) ⊆ 𝑥𝐴𝑥)
6766biimpri 230 . . . . . . . 8 (𝐴𝑥 → (𝐹‘∅) ⊆ 𝑥)
6867adantr 483 . . . . . . 7 ((𝐴𝑥 ∧ Tr 𝑥) → (𝐹‘∅) ⊆ 𝑥)
69 uniss 4822 . . . . . . . . . . . . 13 ((𝐹𝑦) ⊆ 𝑥 (𝐹𝑦) ⊆ 𝑥)
70 df-tr 5149 . . . . . . . . . . . . . 14 (Tr 𝑥 𝑥𝑥)
71 sstr2 3953 . . . . . . . . . . . . . 14 ( (𝐹𝑦) ⊆ 𝑥 → ( 𝑥𝑥 (𝐹𝑦) ⊆ 𝑥))
7270, 71syl5bi 244 . . . . . . . . . . . . 13 ( (𝐹𝑦) ⊆ 𝑥 → (Tr 𝑥 (𝐹𝑦) ⊆ 𝑥))
7369, 72syl 17 . . . . . . . . . . . 12 ((𝐹𝑦) ⊆ 𝑥 → (Tr 𝑥 (𝐹𝑦) ⊆ 𝑥))
7473anc2li 558 . . . . . . . . . . 11 ((𝐹𝑦) ⊆ 𝑥 → (Tr 𝑥 → ((𝐹𝑦) ⊆ 𝑥 (𝐹𝑦) ⊆ 𝑥)))
75 unss 4139 . . . . . . . . . . 11 (((𝐹𝑦) ⊆ 𝑥 (𝐹𝑦) ⊆ 𝑥) ↔ ((𝐹𝑦) ∪ (𝐹𝑦)) ⊆ 𝑥)
7674, 75syl6ib 253 . . . . . . . . . 10 ((𝐹𝑦) ⊆ 𝑥 → (Tr 𝑥 → ((𝐹𝑦) ∪ (𝐹𝑦)) ⊆ 𝑥))
7734sseq1d 3977 . . . . . . . . . . 11 (𝑦 ∈ ω → ((𝐹‘suc 𝑦) ⊆ 𝑥 ↔ ((𝐹𝑦) ∪ (𝐹𝑦)) ⊆ 𝑥))
7877biimprd 250 . . . . . . . . . 10 (𝑦 ∈ ω → (((𝐹𝑦) ∪ (𝐹𝑦)) ⊆ 𝑥 → (𝐹‘suc 𝑦) ⊆ 𝑥))
7976, 78syl9r 78 . . . . . . . . 9 (𝑦 ∈ ω → ((𝐹𝑦) ⊆ 𝑥 → (Tr 𝑥 → (𝐹‘suc 𝑦) ⊆ 𝑥)))
8079com23 86 . . . . . . . 8 (𝑦 ∈ ω → (Tr 𝑥 → ((𝐹𝑦) ⊆ 𝑥 → (𝐹‘suc 𝑦) ⊆ 𝑥)))
8180adantld 493 . . . . . . 7 (𝑦 ∈ ω → ((𝐴𝑥 ∧ Tr 𝑥) → ((𝐹𝑦) ⊆ 𝑥 → (𝐹‘suc 𝑦) ⊆ 𝑥)))
8260, 62, 64, 68, 81finds2 7588 . . . . . 6 (𝑣 ∈ ω → ((𝐴𝑥 ∧ Tr 𝑥) → (𝐹𝑣) ⊆ 𝑥))
8382com12 32 . . . . 5 ((𝐴𝑥 ∧ Tr 𝑥) → (𝑣 ∈ ω → (𝐹𝑣) ⊆ 𝑥))
8483ralrimiv 3168 . . . 4 ((𝐴𝑥 ∧ Tr 𝑥) → ∀𝑣 ∈ ω (𝐹𝑣) ⊆ 𝑥)
85 fveq2 6646 . . . . . . . 8 (𝑦 = 𝑣 → (𝐹𝑦) = (𝐹𝑣))
8685cbviunv 4941 . . . . . . 7 𝑦 ∈ ω (𝐹𝑦) = 𝑣 ∈ ω (𝐹𝑣)
8715, 86eqtri 2843 . . . . . 6 𝐶 = 𝑣 ∈ ω (𝐹𝑣)
8887sseq1i 3974 . . . . 5 (𝐶𝑥 𝑣 ∈ ω (𝐹𝑣) ⊆ 𝑥)
89 iunss 4945 . . . . 5 ( 𝑣 ∈ ω (𝐹𝑣) ⊆ 𝑥 ↔ ∀𝑣 ∈ ω (𝐹𝑣) ⊆ 𝑥)
9088, 89bitri 277 . . . 4 (𝐶𝑥 ↔ ∀𝑣 ∈ ω (𝐹𝑣) ⊆ 𝑥)
9184, 90sylibr 236 . . 3 ((𝐴𝑥 ∧ Tr 𝑥) → 𝐶𝑥)
9291ax-gen 1796 . 2 𝑥((𝐴𝑥 ∧ Tr 𝑥) → 𝐶𝑥)
9316, 58, 923pm3.2i 1335 1 (𝐴𝐶 ∧ Tr 𝐶 ∧ ∀𝑥((𝐴𝑥 ∧ Tr 𝑥) → 𝐶𝑥))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 208  wa 398  w3a 1083  wal 1535   = wceq 1537  wcel 2114  wral 3125  wrex 3126  Vcvv 3473  cun 3911  wss 3913  c0 4269   cuni 4814   ciun 4895  cmpt 5122  Tr wtr 5148  cres 5533  suc csuc 6169  cfv 6331  ωcom 7558  reccrdg 8023
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2792  ax-sep 5179  ax-nul 5186  ax-pow 5242  ax-pr 5306  ax-un 7439
This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1540  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2653  df-clab 2799  df-cleq 2813  df-clel 2891  df-nfc 2959  df-ne 3007  df-ral 3130  df-rex 3131  df-reu 3132  df-rab 3134  df-v 3475  df-sbc 3753  df-csb 3861  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-pss 3932  df-nul 4270  df-if 4444  df-pw 4517  df-sn 4544  df-pr 4546  df-tp 4548  df-op 4550  df-uni 4815  df-iun 4897  df-br 5043  df-opab 5105  df-mpt 5123  df-tr 5149  df-id 5436  df-eprel 5441  df-po 5450  df-so 5451  df-fr 5490  df-we 5492  df-xp 5537  df-rel 5538  df-cnv 5539  df-co 5540  df-dm 5541  df-rn 5542  df-res 5543  df-ima 5544  df-pred 6124  df-ord 6170  df-on 6171  df-lim 6172  df-suc 6173  df-iota 6290  df-fun 6333  df-fn 6334  df-f 6335  df-f1 6336  df-fo 6337  df-f1o 6338  df-fv 6339  df-om 7559  df-wrecs 7925  df-recs 7986  df-rdg 8024
This theorem is referenced by:  tz9.1  9149  tz9.1c  9150
  Copyright terms: Public domain W3C validator