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

Definition df-frec 5978
 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 5920 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 5983 and frecsuc 5991. 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 4327. 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 5992, this definition and df-irdg 5957 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
Distinct variable groups:   ,,,   ,,,

Detailed syntax breakdown of Definition df-frec
StepHypRef Expression
1 cF . . 3
2 cI . . 3
31, 2cfrec 5977 . 2 frec
4 vg . . . . 5
5 cvv 2557 . . . . 5
64cv 1242 . . . . . . . . . . 11
76cdm 4345 . . . . . . . . . 10
8 vm . . . . . . . . . . . 12
98cv 1242 . . . . . . . . . . 11
109csuc 4102 . . . . . . . . . 10
117, 10wceq 1243 . . . . . . . . 9
12 vx . . . . . . . . . . 11
1312cv 1242 . . . . . . . . . 10
149, 6cfv 4902 . . . . . . . . . . 11
1514, 1cfv 4902 . . . . . . . . . 10
1613, 15wcel 1393 . . . . . . . . 9
1711, 16wa 97 . . . . . . . 8
18 com 4313 . . . . . . . 8
1917, 8, 18wrex 2307 . . . . . . 7
20 c0 3224 . . . . . . . . 9
217, 20wceq 1243 . . . . . . . 8
2213, 2wcel 1393 . . . . . . . 8
2321, 22wa 97 . . . . . . 7
2419, 23wo 629 . . . . . 6
2524, 12cab 2026 . . . . 5
264, 5, 25cmpt 3818 . . . 4
2726crecs 5919 . . 3 recs
2827, 18cres 4347 . 2 recs
293, 28wceq 1243 1 frec recs
 Colors of variables: wff set class This definition is referenced by:  freceq1  5979  freceq2  5980  frecex  5981  nffrec  5982  frec0g  5983  frecfnom  5986  frecsuclem1  5987  frecsuclem2  5989
 Copyright terms: Public domain W3C validator