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

Theorem dfrecs3 7638
Description: The old definition of transfinite recursion. This version is preferred for development, as it demonstrates the properties of transfinite recursion without relying on well-founded recursion. (Contributed by Scott Fenton, 3-Aug-2020.)
Assertion
Ref Expression
dfrecs3 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
Distinct variable group:   𝑓,𝐹,𝑥,𝑦

Proof of Theorem dfrecs3
StepHypRef Expression
1 df-recs 7637 . 2 recs(𝐹) = wrecs( E , On, 𝐹)
2 df-wrecs 7576 . 2 wrecs( E , On, 𝐹) = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))}
3 3anass 1081 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑓 Fn 𝑥 ∧ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))))
4 vex 3343 . . . . . . . . . . . 12 𝑥 ∈ V
54elon 5893 . . . . . . . . . . 11 (𝑥 ∈ On ↔ Ord 𝑥)
6 ordsson 7154 . . . . . . . . . . . . 13 (Ord 𝑥𝑥 ⊆ On)
7 ordtr 5898 . . . . . . . . . . . . 13 (Ord 𝑥 → Tr 𝑥)
86, 7jca 555 . . . . . . . . . . . 12 (Ord 𝑥 → (𝑥 ⊆ On ∧ Tr 𝑥))
9 epweon 7148 . . . . . . . . . . . . . . . 16 E We On
10 wess 5253 . . . . . . . . . . . . . . . 16 (𝑥 ⊆ On → ( E We On → E We 𝑥))
119, 10mpi 20 . . . . . . . . . . . . . . 15 (𝑥 ⊆ On → E We 𝑥)
1211anim2i 594 . . . . . . . . . . . . . 14 ((Tr 𝑥𝑥 ⊆ On) → (Tr 𝑥 ∧ E We 𝑥))
1312ancoms 468 . . . . . . . . . . . . 13 ((𝑥 ⊆ On ∧ Tr 𝑥) → (Tr 𝑥 ∧ E We 𝑥))
14 df-ord 5887 . . . . . . . . . . . . 13 (Ord 𝑥 ↔ (Tr 𝑥 ∧ E We 𝑥))
1513, 14sylibr 224 . . . . . . . . . . . 12 ((𝑥 ⊆ On ∧ Tr 𝑥) → Ord 𝑥)
168, 15impbii 199 . . . . . . . . . . 11 (Ord 𝑥 ↔ (𝑥 ⊆ On ∧ Tr 𝑥))
17 ssel2 3739 . . . . . . . . . . . . . . 15 ((𝑥 ⊆ On ∧ 𝑦𝑥) → 𝑦 ∈ On)
18 predon 7156 . . . . . . . . . . . . . . . 16 (𝑦 ∈ On → Pred( E , On, 𝑦) = 𝑦)
1918sseq1d 3773 . . . . . . . . . . . . . . 15 (𝑦 ∈ On → (Pred( E , On, 𝑦) ⊆ 𝑥𝑦𝑥))
2017, 19syl 17 . . . . . . . . . . . . . 14 ((𝑥 ⊆ On ∧ 𝑦𝑥) → (Pred( E , On, 𝑦) ⊆ 𝑥𝑦𝑥))
2120ralbidva 3123 . . . . . . . . . . . . 13 (𝑥 ⊆ On → (∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥 ↔ ∀𝑦𝑥 𝑦𝑥))
22 dftr3 4908 . . . . . . . . . . . . 13 (Tr 𝑥 ↔ ∀𝑦𝑥 𝑦𝑥)
2321, 22syl6rbbr 279 . . . . . . . . . . . 12 (𝑥 ⊆ On → (Tr 𝑥 ↔ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
2423pm5.32i 672 . . . . . . . . . . 11 ((𝑥 ⊆ On ∧ Tr 𝑥) ↔ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
255, 16, 243bitri 286 . . . . . . . . . 10 (𝑥 ∈ On ↔ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
2625anbi1i 733 . . . . . . . . 9 ((𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))))
27 onelon 5909 . . . . . . . . . . . 12 ((𝑥 ∈ On ∧ 𝑦𝑥) → 𝑦 ∈ On)
2818reseq2d 5551 . . . . . . . . . . . . . 14 (𝑦 ∈ On → (𝑓 ↾ Pred( E , On, 𝑦)) = (𝑓𝑦))
2928fveq2d 6356 . . . . . . . . . . . . 13 (𝑦 ∈ On → (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) = (𝐹‘(𝑓𝑦)))
3029eqeq2d 2770 . . . . . . . . . . . 12 (𝑦 ∈ On → ((𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3127, 30syl 17 . . . . . . . . . . 11 ((𝑥 ∈ On ∧ 𝑦𝑥) → ((𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3231ralbidva 3123 . . . . . . . . . 10 (𝑥 ∈ On → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3332pm5.32i 672 . . . . . . . . 9 ((𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3426, 33bitr3i 266 . . . . . . . 8 (((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3534anbi2i 732 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))) ↔ (𝑓 Fn 𝑥 ∧ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
36 an12 873 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) ↔ (𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
373, 35, 363bitri 286 . . . . . 6 ((𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
3837exbii 1923 . . . . 5 (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ∃𝑥(𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
39 df-rex 3056 . . . . 5 (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) ↔ ∃𝑥(𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
4038, 39bitr4i 267 . . . 4 (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
4140abbii 2877 . . 3 {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))} = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
4241unieqi 4597 . 2 {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))} = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
431, 2, 423eqtri 2786 1 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
Colors of variables: wff setvar class
Syntax hints:  wb 196  wa 383  w3a 1072   = wceq 1632  wex 1853  wcel 2139  {cab 2746  wral 3050  wrex 3051  wss 3715   cuni 4588  Tr wtr 4904   E cep 5178   We wwe 5224  cres 5268  Predcpred 5840  Ord word 5883  Oncon0 5884   Fn wfn 6044  cfv 6049  wrecscwrecs 7575  recscrecs 7636
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1871  ax-4 1886  ax-5 1988  ax-6 2054  ax-7 2090  ax-8 2141  ax-9 2148  ax-10 2168  ax-11 2183  ax-12 2196  ax-13 2391  ax-ext 2740  ax-sep 4933  ax-nul 4941  ax-pr 5055  ax-un 7114
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1635  df-ex 1854  df-nf 1859  df-sb 2047  df-eu 2611  df-mo 2612  df-clab 2747  df-cleq 2753  df-clel 2756  df-nfc 2891  df-ne 2933  df-ral 3055  df-rex 3056  df-rab 3059  df-v 3342  df-sbc 3577  df-dif 3718  df-un 3720  df-in 3722  df-ss 3729  df-pss 3731  df-nul 4059  df-if 4231  df-sn 4322  df-pr 4324  df-tp 4326  df-op 4328  df-uni 4589  df-br 4805  df-opab 4865  df-tr 4905  df-eprel 5179  df-po 5187  df-so 5188  df-fr 5225  df-we 5227  df-xp 5272  df-rel 5273  df-cnv 5274  df-dm 5276  df-rn 5277  df-res 5278  df-ima 5279  df-pred 5841  df-ord 5887  df-on 5888  df-iota 6012  df-fv 6057  df-wrecs 7576  df-recs 7637
This theorem is referenced by:  recsfval  7646  tfrlem9  7650  dfrdg2  32006  dfrecs2  32363
  Copyright terms: Public domain W3C validator