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

Theorem dfrecs3 7333
Description: The old definition of transfinite recursion. This version is preferred for developement, 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 7332 . 2 recs(𝐹) = wrecs( E , On, 𝐹)
2 df-wrecs 7271 . 2 wrecs( E , On, 𝐹) = {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))}
3 3anass 1034 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑓 Fn 𝑥 ∧ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))))
4 vex 3175 . . . . . . . . . . . 12 𝑥 ∈ V
54elon 5635 . . . . . . . . . . 11 (𝑥 ∈ On ↔ Ord 𝑥)
6 ordsson 6858 . . . . . . . . . . . . 13 (Ord 𝑥𝑥 ⊆ On)
7 ordtr 5640 . . . . . . . . . . . . 13 (Ord 𝑥 → Tr 𝑥)
86, 7jca 552 . . . . . . . . . . . 12 (Ord 𝑥 → (𝑥 ⊆ On ∧ Tr 𝑥))
9 epweon 6852 . . . . . . . . . . . . . . . 16 E We On
10 wess 5015 . . . . . . . . . . . . . . . 16 (𝑥 ⊆ On → ( E We On → E We 𝑥))
119, 10mpi 20 . . . . . . . . . . . . . . 15 (𝑥 ⊆ On → E We 𝑥)
1211anim2i 590 . . . . . . . . . . . . . 14 ((Tr 𝑥𝑥 ⊆ On) → (Tr 𝑥 ∧ E We 𝑥))
1312ancoms 467 . . . . . . . . . . . . 13 ((𝑥 ⊆ On ∧ Tr 𝑥) → (Tr 𝑥 ∧ E We 𝑥))
14 df-ord 5629 . . . . . . . . . . . . 13 (Ord 𝑥 ↔ (Tr 𝑥 ∧ E We 𝑥))
1513, 14sylibr 222 . . . . . . . . . . . 12 ((𝑥 ⊆ On ∧ Tr 𝑥) → Ord 𝑥)
168, 15impbii 197 . . . . . . . . . . 11 (Ord 𝑥 ↔ (𝑥 ⊆ On ∧ Tr 𝑥))
17 ssel2 3562 . . . . . . . . . . . . . . 15 ((𝑥 ⊆ On ∧ 𝑦𝑥) → 𝑦 ∈ On)
18 predon 6860 . . . . . . . . . . . . . . . 16 (𝑦 ∈ On → Pred( E , On, 𝑦) = 𝑦)
1918sseq1d 3594 . . . . . . . . . . . . . . 15 (𝑦 ∈ On → (Pred( E , On, 𝑦) ⊆ 𝑥𝑦𝑥))
2017, 19syl 17 . . . . . . . . . . . . . 14 ((𝑥 ⊆ On ∧ 𝑦𝑥) → (Pred( E , On, 𝑦) ⊆ 𝑥𝑦𝑥))
2120ralbidva 2967 . . . . . . . . . . . . 13 (𝑥 ⊆ On → (∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥 ↔ ∀𝑦𝑥 𝑦𝑥))
22 dftr3 4678 . . . . . . . . . . . . 13 (Tr 𝑥 ↔ ∀𝑦𝑥 𝑦𝑥)
2321, 22syl6rbbr 277 . . . . . . . . . . . 12 (𝑥 ⊆ On → (Tr 𝑥 ↔ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
2423pm5.32i 666 . . . . . . . . . . 11 ((𝑥 ⊆ On ∧ Tr 𝑥) ↔ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
255, 16, 243bitri 284 . . . . . . . . . 10 (𝑥 ∈ On ↔ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥))
2625anbi1i 726 . . . . . . . . 9 ((𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))))
27 onelon 5651 . . . . . . . . . . . 12 ((𝑥 ∈ On ∧ 𝑦𝑥) → 𝑦 ∈ On)
2818reseq2d 5304 . . . . . . . . . . . . . 14 (𝑦 ∈ On → (𝑓 ↾ Pred( E , On, 𝑦)) = (𝑓𝑦))
2928fveq2d 6092 . . . . . . . . . . . . 13 (𝑦 ∈ On → (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) = (𝐹‘(𝑓𝑦)))
3029eqeq2d 2619 . . . . . . . . . . . 12 (𝑦 ∈ On → ((𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3127, 30syl 17 . . . . . . . . . . 11 ((𝑥 ∈ On ∧ 𝑦𝑥) → ((𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3231ralbidva 2967 . . . . . . . . . 10 (𝑥 ∈ On → (∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))) ↔ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3332pm5.32i 666 . . . . . . . . 9 ((𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3426, 33bitr3i 264 . . . . . . . 8 (((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
3534anbi2i 725 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ ((𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))) ↔ (𝑓 Fn 𝑥 ∧ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
36 an12 833 . . . . . . 7 ((𝑓 Fn 𝑥 ∧ (𝑥 ∈ On ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))) ↔ (𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
373, 35, 363bitri 284 . . . . . 6 ((𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ (𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
3837exbii 1763 . . . . 5 (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ∃𝑥(𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
39 df-rex 2901 . . . . 5 (∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))) ↔ ∃𝑥(𝑥 ∈ On ∧ (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))))
4038, 39bitr4i 265 . . . 4 (∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦)))) ↔ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦))))
4140abbii 2725 . . 3 {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))} = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
4241unieqi 4375 . 2 {𝑓 ∣ ∃𝑥(𝑓 Fn 𝑥 ∧ (𝑥 ⊆ On ∧ ∀𝑦𝑥 Pred( E , On, 𝑦) ⊆ 𝑥) ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓 ↾ Pred( E , On, 𝑦))))} = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
431, 2, 423eqtri 2635 1 recs(𝐹) = {𝑓 ∣ ∃𝑥 ∈ On (𝑓 Fn 𝑥 ∧ ∀𝑦𝑥 (𝑓𝑦) = (𝐹‘(𝑓𝑦)))}
Colors of variables: wff setvar class
Syntax hints:  wb 194  wa 382  w3a 1030   = wceq 1474  wex 1694  wcel 1976  {cab 2595  wral 2895  wrex 2896  wss 3539   cuni 4366  Tr wtr 4674   E cep 4937   We wwe 4986  cres 5030  Predcpred 5582  Ord word 5625  Oncon0 5626   Fn wfn 5785  cfv 5790  wrecscwrecs 7270  recscrecs 7331
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2032  ax-13 2232  ax-ext 2589  ax-sep 4703  ax-nul 4712  ax-pr 4828  ax-un 6824
This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3or 1031  df-3an 1032  df-tru 1477  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2461  df-mo 2462  df-clab 2596  df-cleq 2602  df-clel 2605  df-nfc 2739  df-ne 2781  df-ral 2900  df-rex 2901  df-rab 2904  df-v 3174  df-sbc 3402  df-dif 3542  df-un 3544  df-in 3546  df-ss 3553  df-pss 3555  df-nul 3874  df-if 4036  df-sn 4125  df-pr 4127  df-tp 4129  df-op 4131  df-uni 4367  df-br 4578  df-opab 4638  df-tr 4675  df-eprel 4939  df-po 4949  df-so 4950  df-fr 4987  df-we 4989  df-xp 5034  df-rel 5035  df-cnv 5036  df-dm 5038  df-rn 5039  df-res 5040  df-ima 5041  df-pred 5583  df-ord 5629  df-on 5630  df-iota 5754  df-fv 5798  df-wrecs 7271  df-recs 7332
This theorem is referenced by:  recsfval  7341  tfrlem9  7345  dfrdg2  30751  dfrecs2  31033
  Copyright terms: Public domain W3C validator