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

Definition df-irdg 6149
Description: Define a recursive definition generator on On (the class of ordinal numbers) 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 rec operation (especially when df-recs 6084 that it is built on is also eliminated). But once we get past this hurdle, definitions that would otherwise be recursive become relatively simple. In classical logic it would be easier to divide this definition into cases based on whether the domain of 𝑔 is zero, a successor, or a limit ordinal. Cases do not (in general) work that way in intuitionistic logic, so instead we choose a definition which takes the union of all the results of the characteristic function for ordinals in the domain of 𝑔. This means that this definition has the expected properties for increasing and continuous ordinal functions, which include ordinal addition and multiplication.

For finite recursion we also define df-frec 6170 and for suitable characteristic functions df-frec 6170 yields the same result as rec restricted to ω, as seen at frecrdg 6187.

Note: We introduce rec 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 Jim Kingdon, 19-May-2019.)

Assertion
Ref Expression
df-irdg rec(𝐹, 𝐼) = recs((𝑔 ∈ V ↦ (𝐼 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥)))))
Distinct variable groups:   𝑥,𝑔,𝐹   𝑥,𝐼,𝑔

Detailed syntax breakdown of Definition df-irdg
StepHypRef Expression
1 cF . . 3 class 𝐹
2 cI . . 3 class 𝐼
31, 2crdg 6148 . 2 class rec(𝐹, 𝐼)
4 vg . . . 4 setvar 𝑔
5 cvv 2620 . . . 4 class V
6 vx . . . . . 6 setvar 𝑥
74cv 1289 . . . . . . 7 class 𝑔
87cdm 4452 . . . . . 6 class dom 𝑔
96cv 1289 . . . . . . . 8 class 𝑥
109, 7cfv 5028 . . . . . . 7 class (𝑔𝑥)
1110, 1cfv 5028 . . . . . 6 class (𝐹‘(𝑔𝑥))
126, 8, 11ciun 3736 . . . . 5 class 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥))
132, 12cun 2998 . . . 4 class (𝐼 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥)))
144, 5, 13cmpt 3905 . . 3 class (𝑔 ∈ V ↦ (𝐼 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥))))
1514crecs 6083 . 2 class recs((𝑔 ∈ V ↦ (𝐼 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥)))))
163, 15wceq 1290 1 wff rec(𝐹, 𝐼) = recs((𝑔 ∈ V ↦ (𝐼 𝑥 ∈ dom 𝑔(𝐹‘(𝑔𝑥)))))
Colors of variables: wff set class
This definition is referenced by:  rdgeq1  6150  rdgeq2  6151  rdgfun  6152  rdgexggg  6156  rdgifnon  6158  rdgifnon2  6159  rdgivallem  6160  rdgon  6165  rdg0  6166
  Copyright terms: Public domain W3C validator