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

Definition df-frec 6256
Description: Define a recursive definition generator on ω (the class of finite ordinals) with characteristic function 𝐹 and initial value 𝐼. This rather amazing operation allows us to define, with compact direct definitions, functions that are usually defined in textbooks only with indirect self-referencing recursive definitions. A recursive definition requires advanced metalogic to justify - in particular, eliminating a recursive definition is very difficult and often not even shown in textbooks. On the other hand, the elimination of a direct definition is a matter of simple mechanical substitution. The price paid is the daunting complexity of our frec operation (especially when df-recs 6170 that it is built on is also eliminated). But once we get past this hurdle, definitions that would otherwise be recursive become relatively simple; see frec0g 6262 and frecsuc 6272.

Unlike with transfinite recursion, finite recurson can readily divide definitions and proofs into zero and successor cases, because even without excluded middle we have theorems such as nn0suc 4488. The analogous situation with transfinite recursion - being able to say that an ordinal is zero, successor, or limit - is enabled by excluded middle and thus is not available to us. For the characteristic functions which satisfy the conditions given at frecrdg 6273, this definition and df-irdg 6235 restricted to ω produce the same result.

Note: We introduce frec with the philosophical goal of being able to eliminate all definitions with direct mechanical substitution and to verify easily the soundness of definitions. Metamath itself has no built-in technical limitation that prevents multiple-part recursive definitions in the traditional textbook style. (Contributed by Mario Carneiro and Jim Kingdon, 10-Aug-2019.)

Assertion
Ref Expression
df-frec frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))})) ↾ ω)
Distinct variable groups:   𝑥,𝑔,𝑚,𝐹   𝑥,𝐼,𝑔,𝑚

Detailed syntax breakdown of Definition df-frec
StepHypRef Expression
1 cF . . 3 class 𝐹
2 cI . . 3 class 𝐼
31, 2cfrec 6255 . 2 class frec(𝐹, 𝐼)
4 vg . . . . 5 setvar 𝑔
5 cvv 2660 . . . . 5 class V
64cv 1315 . . . . . . . . . . 11 class 𝑔
76cdm 4509 . . . . . . . . . 10 class dom 𝑔
8 vm . . . . . . . . . . . 12 setvar 𝑚
98cv 1315 . . . . . . . . . . 11 class 𝑚
109csuc 4257 . . . . . . . . . 10 class suc 𝑚
117, 10wceq 1316 . . . . . . . . 9 wff dom 𝑔 = suc 𝑚
12 vx . . . . . . . . . . 11 setvar 𝑥
1312cv 1315 . . . . . . . . . 10 class 𝑥
149, 6cfv 5093 . . . . . . . . . . 11 class (𝑔𝑚)
1514, 1cfv 5093 . . . . . . . . . 10 class (𝐹‘(𝑔𝑚))
1613, 15wcel 1465 . . . . . . . . 9 wff 𝑥 ∈ (𝐹‘(𝑔𝑚))
1711, 16wa 103 . . . . . . . 8 wff (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚)))
18 com 4474 . . . . . . . 8 class ω
1917, 8, 18wrex 2394 . . . . . . 7 wff 𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚)))
20 c0 3333 . . . . . . . . 9 class
217, 20wceq 1316 . . . . . . . 8 wff dom 𝑔 = ∅
2213, 2wcel 1465 . . . . . . . 8 wff 𝑥𝐼
2321, 22wa 103 . . . . . . 7 wff (dom 𝑔 = ∅ ∧ 𝑥𝐼)
2419, 23wo 682 . . . . . 6 wff (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))
2524, 12cab 2103 . . . . 5 class {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))}
264, 5, 25cmpt 3959 . . . 4 class (𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))})
2726crecs 6169 . . 3 class recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))}))
2827, 18cres 4511 . 2 class (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))})) ↾ ω)
293, 28wceq 1316 1 wff frec(𝐹, 𝐼) = (recs((𝑔 ∈ V ↦ {𝑥 ∣ (∃𝑚 ∈ ω (dom 𝑔 = suc 𝑚𝑥 ∈ (𝐹‘(𝑔𝑚))) ∨ (dom 𝑔 = ∅ ∧ 𝑥𝐼))})) ↾ ω)
Colors of variables: wff set class
This definition is referenced by:  freceq1  6257  freceq2  6258  frecex  6259  frecfun  6260  nffrec  6261  frec0g  6262  frecfnom  6266  freccllem  6267  frecfcllem  6269  frecsuclem  6271
  Copyright terms: Public domain W3C validator