ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  frecrdg GIF version

Theorem frecrdg 6211
Description: Transfinite recursion restricted to omega.

Given a suitable characteristic function, df-frec 6194 produces the same results as df-irdg 6173 restricted to ω.

Presumably the theorem would also hold if 𝐹 Fn V were changed to 𝑧(𝐹𝑧) ∈ V. (Contributed by Jim Kingdon, 29-Aug-2019.)

Hypotheses
Ref Expression
frecrdg.1 (𝜑𝐹 Fn V)
frecrdg.2 (𝜑𝐴𝑉)
frecrdg.inc (𝜑 → ∀𝑥 𝑥 ⊆ (𝐹𝑥))
Assertion
Ref Expression
frecrdg (𝜑 → frec(𝐹, 𝐴) = (rec(𝐹, 𝐴) ↾ ω))
Distinct variable groups:   𝑥,𝐴   𝑥,𝐹   𝑥,𝑉   𝜑,𝑥

Proof of Theorem frecrdg
Dummy variables 𝑦 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 frecrdg.1 . . . 4 (𝜑𝐹 Fn V)
2 vex 2636 . . . . . 6 𝑧 ∈ V
3 funfvex 5357 . . . . . . 7 ((Fun 𝐹𝑧 ∈ dom 𝐹) → (𝐹𝑧) ∈ V)
43funfni 5148 . . . . . 6 ((𝐹 Fn V ∧ 𝑧 ∈ V) → (𝐹𝑧) ∈ V)
52, 4mpan2 417 . . . . 5 (𝐹 Fn V → (𝐹𝑧) ∈ V)
65alrimiv 1809 . . . 4 (𝐹 Fn V → ∀𝑧(𝐹𝑧) ∈ V)
71, 6syl 14 . . 3 (𝜑 → ∀𝑧(𝐹𝑧) ∈ V)
8 frecrdg.2 . . 3 (𝜑𝐴𝑉)
9 frecfnom 6204 . . 3 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉) → frec(𝐹, 𝐴) Fn ω)
107, 8, 9syl2anc 404 . 2 (𝜑 → frec(𝐹, 𝐴) Fn ω)
11 rdgifnon2 6183 . . . 4 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉) → rec(𝐹, 𝐴) Fn On)
127, 8, 11syl2anc 404 . . 3 (𝜑 → rec(𝐹, 𝐴) Fn On)
13 omsson 4455 . . 3 ω ⊆ On
14 fnssres 5161 . . 3 ((rec(𝐹, 𝐴) Fn On ∧ ω ⊆ On) → (rec(𝐹, 𝐴) ↾ ω) Fn ω)
1512, 13, 14sylancl 405 . 2 (𝜑 → (rec(𝐹, 𝐴) ↾ ω) Fn ω)
16 fveq2 5340 . . . . 5 (𝑥 = ∅ → (frec(𝐹, 𝐴)‘𝑥) = (frec(𝐹, 𝐴)‘∅))
17 fveq2 5340 . . . . 5 (𝑥 = ∅ → ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘∅))
1816, 17eqeq12d 2109 . . . 4 (𝑥 = ∅ → ((frec(𝐹, 𝐴)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) ↔ (frec(𝐹, 𝐴)‘∅) = ((rec(𝐹, 𝐴) ↾ ω)‘∅)))
19 fveq2 5340 . . . . 5 (𝑥 = 𝑦 → (frec(𝐹, 𝐴)‘𝑥) = (frec(𝐹, 𝐴)‘𝑦))
20 fveq2 5340 . . . . 5 (𝑥 = 𝑦 → ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦))
2119, 20eqeq12d 2109 . . . 4 (𝑥 = 𝑦 → ((frec(𝐹, 𝐴)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) ↔ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)))
22 fveq2 5340 . . . . 5 (𝑥 = suc 𝑦 → (frec(𝐹, 𝐴)‘𝑥) = (frec(𝐹, 𝐴)‘suc 𝑦))
23 fveq2 5340 . . . . 5 (𝑥 = suc 𝑦 → ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦))
2422, 23eqeq12d 2109 . . . 4 (𝑥 = suc 𝑦 → ((frec(𝐹, 𝐴)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑥) ↔ (frec(𝐹, 𝐴)‘suc 𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦)))
25 frec0g 6200 . . . . . 6 (𝐴𝑉 → (frec(𝐹, 𝐴)‘∅) = 𝐴)
268, 25syl 14 . . . . 5 (𝜑 → (frec(𝐹, 𝐴)‘∅) = 𝐴)
27 peano1 4437 . . . . . . 7 ∅ ∈ ω
28 fvres 5364 . . . . . . 7 (∅ ∈ ω → ((rec(𝐹, 𝐴) ↾ ω)‘∅) = (rec(𝐹, 𝐴)‘∅))
2927, 28ax-mp 7 . . . . . 6 ((rec(𝐹, 𝐴) ↾ ω)‘∅) = (rec(𝐹, 𝐴)‘∅)
30 rdg0g 6191 . . . . . . 7 (𝐴𝑉 → (rec(𝐹, 𝐴)‘∅) = 𝐴)
318, 30syl 14 . . . . . 6 (𝜑 → (rec(𝐹, 𝐴)‘∅) = 𝐴)
3229, 31syl5eq 2139 . . . . 5 (𝜑 → ((rec(𝐹, 𝐴) ↾ ω)‘∅) = 𝐴)
3326, 32eqtr4d 2130 . . . 4 (𝜑 → (frec(𝐹, 𝐴)‘∅) = ((rec(𝐹, 𝐴) ↾ ω)‘∅))
34 simpr 109 . . . . . . . . . 10 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦))
35 fvres 5364 . . . . . . . . . . 11 (𝑦 ∈ ω → ((rec(𝐹, 𝐴) ↾ ω)‘𝑦) = (rec(𝐹, 𝐴)‘𝑦))
3635ad2antlr 474 . . . . . . . . . 10 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → ((rec(𝐹, 𝐴) ↾ ω)‘𝑦) = (rec(𝐹, 𝐴)‘𝑦))
3734, 36eqtrd 2127 . . . . . . . . 9 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (frec(𝐹, 𝐴)‘𝑦) = (rec(𝐹, 𝐴)‘𝑦))
3837fveq2d 5344 . . . . . . . 8 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (𝐹‘(frec(𝐹, 𝐴)‘𝑦)) = (𝐹‘(rec(𝐹, 𝐴)‘𝑦)))
397, 8jca 301 . . . . . . . . . 10 (𝜑 → (∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉))
40 simp1 946 . . . . . . . . . . . . 13 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → ∀𝑧(𝐹𝑧) ∈ V)
41 ralv 2650 . . . . . . . . . . . . 13 (∀𝑧 ∈ V (𝐹𝑧) ∈ V ↔ ∀𝑧(𝐹𝑧) ∈ V)
4240, 41sylibr 133 . . . . . . . . . . . 12 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → ∀𝑧 ∈ V (𝐹𝑧) ∈ V)
43 simp2 947 . . . . . . . . . . . . 13 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → 𝐴𝑉)
4443elexd 2646 . . . . . . . . . . . 12 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → 𝐴 ∈ V)
45 simp3 948 . . . . . . . . . . . 12 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → 𝑦 ∈ ω)
46 frecsuc 6210 . . . . . . . . . . . 12 ((∀𝑧 ∈ V (𝐹𝑧) ∈ V ∧ 𝐴 ∈ V ∧ 𝑦 ∈ ω) → (frec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(frec(𝐹, 𝐴)‘𝑦)))
4742, 44, 45, 46syl3anc 1181 . . . . . . . . . . 11 ((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉𝑦 ∈ ω) → (frec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(frec(𝐹, 𝐴)‘𝑦)))
48473expa 1146 . . . . . . . . . 10 (((∀𝑧(𝐹𝑧) ∈ V ∧ 𝐴𝑉) ∧ 𝑦 ∈ ω) → (frec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(frec(𝐹, 𝐴)‘𝑦)))
4939, 48sylan 278 . . . . . . . . 9 ((𝜑𝑦 ∈ ω) → (frec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(frec(𝐹, 𝐴)‘𝑦)))
5049adantr 271 . . . . . . . 8 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (frec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(frec(𝐹, 𝐴)‘𝑦)))
511adantr 271 . . . . . . . . . 10 ((𝜑𝑦 ∈ ω) → 𝐹 Fn V)
528adantr 271 . . . . . . . . . 10 ((𝜑𝑦 ∈ ω) → 𝐴𝑉)
53 simpr 109 . . . . . . . . . . 11 ((𝜑𝑦 ∈ ω) → 𝑦 ∈ ω)
54 nnon 4452 . . . . . . . . . . 11 (𝑦 ∈ ω → 𝑦 ∈ On)
5553, 54syl 14 . . . . . . . . . 10 ((𝜑𝑦 ∈ ω) → 𝑦 ∈ On)
56 frecrdg.inc . . . . . . . . . . 11 (𝜑 → ∀𝑥 𝑥 ⊆ (𝐹𝑥))
5756adantr 271 . . . . . . . . . 10 ((𝜑𝑦 ∈ ω) → ∀𝑥 𝑥 ⊆ (𝐹𝑥))
5851, 52, 55, 57rdgisucinc 6188 . . . . . . . . 9 ((𝜑𝑦 ∈ ω) → (rec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(rec(𝐹, 𝐴)‘𝑦)))
5958adantr 271 . . . . . . . 8 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (rec(𝐹, 𝐴)‘suc 𝑦) = (𝐹‘(rec(𝐹, 𝐴)‘𝑦)))
6038, 50, 593eqtr4d 2137 . . . . . . 7 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (frec(𝐹, 𝐴)‘suc 𝑦) = (rec(𝐹, 𝐴)‘suc 𝑦))
61 peano2 4438 . . . . . . . . 9 (𝑦 ∈ ω → suc 𝑦 ∈ ω)
62 fvres 5364 . . . . . . . . 9 (suc 𝑦 ∈ ω → ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦) = (rec(𝐹, 𝐴)‘suc 𝑦))
6361, 62syl 14 . . . . . . . 8 (𝑦 ∈ ω → ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦) = (rec(𝐹, 𝐴)‘suc 𝑦))
6463ad2antlr 474 . . . . . . 7 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦) = (rec(𝐹, 𝐴)‘suc 𝑦))
6560, 64eqtr4d 2130 . . . . . 6 (((𝜑𝑦 ∈ ω) ∧ (frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦)) → (frec(𝐹, 𝐴)‘suc 𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦))
6665ex 114 . . . . 5 ((𝜑𝑦 ∈ ω) → ((frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦) → (frec(𝐹, 𝐴)‘suc 𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦)))
6766expcom 115 . . . 4 (𝑦 ∈ ω → (𝜑 → ((frec(𝐹, 𝐴)‘𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑦) → (frec(𝐹, 𝐴)‘suc 𝑦) = ((rec(𝐹, 𝐴) ↾ ω)‘suc 𝑦))))
6818, 21, 24, 33, 67finds2 4444 . . 3 (𝑥 ∈ ω → (𝜑 → (frec(𝐹, 𝐴)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑥)))
6968impcom 124 . 2 ((𝜑𝑥 ∈ ω) → (frec(𝐹, 𝐴)‘𝑥) = ((rec(𝐹, 𝐴) ↾ ω)‘𝑥))
7010, 15, 69eqfnfvd 5439 1 (𝜑 → frec(𝐹, 𝐴) = (rec(𝐹, 𝐴) ↾ ω))
Colors of variables: wff set class
Syntax hints:  wi 4  wa 103  w3a 927  wal 1294   = wceq 1296  wcel 1445  wral 2370  Vcvv 2633  wss 3013  c0 3302  Oncon0 4214  suc csuc 4216  ωcom 4433  cres 4469   Fn wfn 5044  cfv 5049  reccrdg 6172  freccfrec 6193
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 582  ax-in2 583  ax-io 668  ax-5 1388  ax-7 1389  ax-gen 1390  ax-ie1 1434  ax-ie2 1435  ax-8 1447  ax-10 1448  ax-11 1449  ax-i12 1450  ax-bndl 1451  ax-4 1452  ax-13 1456  ax-14 1457  ax-17 1471  ax-i9 1475  ax-ial 1479  ax-i5r 1480  ax-ext 2077  ax-coll 3975  ax-sep 3978  ax-nul 3986  ax-pow 4030  ax-pr 4060  ax-un 4284  ax-setind 4381  ax-iinf 4431
This theorem depends on definitions:  df-bi 116  df-3an 929  df-tru 1299  df-fal 1302  df-nf 1402  df-sb 1700  df-eu 1958  df-mo 1959  df-clab 2082  df-cleq 2088  df-clel 2091  df-nfc 2224  df-ne 2263  df-ral 2375  df-rex 2376  df-reu 2377  df-rab 2379  df-v 2635  df-sbc 2855  df-csb 2948  df-dif 3015  df-un 3017  df-in 3019  df-ss 3026  df-nul 3303  df-pw 3451  df-sn 3472  df-pr 3473  df-op 3475  df-uni 3676  df-int 3711  df-iun 3754  df-br 3868  df-opab 3922  df-mpt 3923  df-tr 3959  df-id 4144  df-iord 4217  df-on 4219  df-ilim 4220  df-suc 4222  df-iom 4434  df-xp 4473  df-rel 4474  df-cnv 4475  df-co 4476  df-dm 4477  df-rn 4478  df-res 4479  df-ima 4480  df-iota 5014  df-fun 5051  df-fn 5052  df-f 5053  df-f1 5054  df-fo 5055  df-f1o 5056  df-fv 5057  df-recs 6108  df-irdg 6173  df-frec 6194
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator