|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 5861
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 5922 and frecsuc 5930.
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 4270. 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 5931, this definition and
df-irdg 5897 restricted to produce the same result.
Note: We introduce frec with the philosophical goal of
able to eliminate all definitions with direct mechanical
and to verify easily the soundness of definitions. Metamath
has no built-in technical limitation that prevents multiple-part
recursive definitions in the traditional textbook style.
by Mario Carneiro and Jim Kingdon,