Metamath Proof Explorer

Theorem dfrecs3

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-ordered recursion. (Contributed by Scott Fenton, 3-Aug-2020) (Proof revised by Scott Fenton, 18-Nov-2024.)

Ref Expression
Assertion dfrecs3 recs ( 𝐹 ) = ∪ { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) }

Proof

Step Hyp Ref Expression
1 df-recs ⊢ recs ( 𝐹 ) = wrecs ( E , On , 𝐹 )
2 df-wrecs ⊢ wrecs ( E , On , 𝐹 ) = frecs ( E , On , ( 𝐹 ∘ 2nd ) )
3 df-frecs ⊢ frecs ( E , On , ( 𝐹 ∘ 2nd ) ) = ∪ { 𝑓 ∣ ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) }
4 3anass ⊢ ( ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ( 𝑓 Fn 𝑥 ∧ ( ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ) )
5 vex ⊢ 𝑥 ∈ V
6 5 elon ⊢ ( 𝑥 ∈ On ↔ Ord 𝑥 )
7 ordsson ⊢ ( Ord 𝑥 → 𝑥 ⊆ On )
8 ordtr ⊢ ( Ord 𝑥 → Tr 𝑥 )
9 7 8 jca ⊢ ( Ord 𝑥 → ( 𝑥 ⊆ On ∧ Tr 𝑥 ) )
10 epweon ⊢ E We On
11 wess ⊢ ( 𝑥 ⊆ On → ( E We On → E We 𝑥 ) )
12 10 11 mpi ⊢ ( 𝑥 ⊆ On → E We 𝑥 )
13 12 anim1ci ⊢ ( ( 𝑥 ⊆ On ∧ Tr 𝑥 ) → ( Tr 𝑥 ∧ E We 𝑥 ) )
14 df-ord ⊢ ( Ord 𝑥 ↔ ( Tr 𝑥 ∧ E We 𝑥 ) )
15 13 14 sylibr ⊢ ( ( 𝑥 ⊆ On ∧ Tr 𝑥 ) → Ord 𝑥 )
16 9 15 impbii ⊢ ( Ord 𝑥 ↔ ( 𝑥 ⊆ On ∧ Tr 𝑥 ) )
17 dftr3 ⊢ ( Tr 𝑥 ↔ ∀ 𝑦 ∈ 𝑥 𝑦 ⊆ 𝑥 )
18 ssel2 ⊢ ( ( 𝑥 ⊆ On ∧ 𝑦 ∈ 𝑥 ) → 𝑦 ∈ On )
19 predon ⊢ ( 𝑦 ∈ On → Pred ( E , On , 𝑦 ) = 𝑦 )
20 19 sseq1d ⊢ ( 𝑦 ∈ On → ( Pred ( E , On , 𝑦 ) ⊆ 𝑥 ↔ 𝑦 ⊆ 𝑥 ) )
21 18 20 syl ⊢ ( ( 𝑥 ⊆ On ∧ 𝑦 ∈ 𝑥 ) → ( Pred ( E , On , 𝑦 ) ⊆ 𝑥 ↔ 𝑦 ⊆ 𝑥 ) )
22 21 ralbidva ⊢ ( 𝑥 ⊆ On → ( ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ↔ ∀ 𝑦 ∈ 𝑥 𝑦 ⊆ 𝑥 ) )
23 17 22 bitr4id ⊢ ( 𝑥 ⊆ On → ( Tr 𝑥 ↔ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) )
24 23 pm5.32i ⊢ ( ( 𝑥 ⊆ On ∧ Tr 𝑥 ) ↔ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) )
25 6 16 24 3bitri ⊢ ( 𝑥 ∈ On ↔ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) )
26 25 anbi1i ⊢ ( ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ( ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) )
27 onelon ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → 𝑦 ∈ On )
28 27 19 syl ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → Pred ( E , On , 𝑦 ) = 𝑦 )
29 28 reseq2d ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) = ( 𝑓 ↾ 𝑦 ) )
30 29 oveq2d ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ 𝑦 ) ) )
31 id ⊢ ( 𝑦 ∈ 𝑥 → 𝑦 ∈ 𝑥 )
32 vex ⊢ 𝑓 ∈ V
33 32 resex ⊢ ( 𝑓 ↾ 𝑦 ) ∈ V
34 33 a1i ⊢ ( 𝑦 ∈ 𝑥 → ( 𝑓 ↾ 𝑦 ) ∈ V )
35 31 34 opco2 ⊢ ( 𝑦 ∈ 𝑥 → ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ 𝑦 ) ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) )
36 35 adantl ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ 𝑦 ) ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) )
37 30 36 eqtrd ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) )
38 37 eqeq2d ⊢ ( ( 𝑥 ∈ On ∧ 𝑦 ∈ 𝑥 ) → ( ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ↔ ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) )
39 38 ralbidva ⊢ ( 𝑥 ∈ On → ( ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ↔ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) )
40 39 pm5.32i ⊢ ( ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) )
41 26 40 bitr3i ⊢ ( ( ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) )
42 41 anbi2i ⊢ ( ( 𝑓 Fn 𝑥 ∧ ( ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ) ↔ ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) )
43 an12 ⊢ ( ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ∈ On ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) ↔ ( 𝑥 ∈ On ∧ ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) )
44 4 42 43 3bitri ⊢ ( ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ( 𝑥 ∈ On ∧ ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) )
45 44 exbii ⊢ ( ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ∃ 𝑥 ( 𝑥 ∈ On ∧ ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) )
46 df-rex ⊢ ( ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ↔ ∃ 𝑥 ( 𝑥 ∈ On ∧ ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) ) )
47 45 46 bitr4i ⊢ ( ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) ↔ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) )
48 47 abbii ⊢ { 𝑓 ∣ ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) } = { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) }
49 48 unieqi ⊢ ∪ { 𝑓 ∣ ∃ 𝑥 ( 𝑓 Fn 𝑥 ∧ ( 𝑥 ⊆ On ∧ ∀ 𝑦 ∈ 𝑥 Pred ( E , On , 𝑦 ) ⊆ 𝑥 ) ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝑦 ( 𝐹 ∘ 2nd ) ( 𝑓 ↾ Pred ( E , On , 𝑦 ) ) ) ) } = ∪ { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) }
50 3 49 eqtri ⊢ frecs ( E , On , ( 𝐹 ∘ 2nd ) ) = ∪ { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) }
51 1 2 50 3eqtri ⊢ recs ( 𝐹 ) = ∪ { 𝑓 ∣ ∃ 𝑥 ∈ On ( 𝑓 Fn 𝑥 ∧ ∀ 𝑦 ∈ 𝑥 ( 𝑓 ‘ 𝑦 ) = ( 𝐹 ‘ ( 𝑓 ↾ 𝑦 ) ) ) }