Transfinite recursion

A method of defining functions on ordinal numbers or, more generally, on sets endowed with an ordinal structure. The defining equation of transfinite recursion has the form $$ F(x) = G(x,F \uparrow x), \qquad (\star) $$ where $ F \uparrow x $ is the ‘piece’ of the function $ F $ to be defined restricted to the set of predecessors of $ x $, and $ G $ is some given function. Many functions and classes important in set theory (e.g., the class of Gödel-constructible sets) are defined by means of transfinite recursion. The analogy between this set-theoretic construction and the recursive definitions of numerical functions has been an object of study in the theory of algorithms from the very beginning of its creation. In particular, this analogy lies at the basis of the various classifications of general recursive functions (see [1]).

Of great significance in a number of branches of mathematical logic (e.g., proof theory, recursive hierarchy theory) are the recursive ordinal numbers and the modification of transfinite recursion related to them. (Recursive ordinal numbers are the algorithmic analogues of countable ordinal numbers; subsequently, analogues of ordinal numbers of larger cardinality were proposed.) In this situation, transfinite recursion is called the Rogers Lemma. Here, Equation $ (\star) $ is subjected to the following modification: The function $ G $ is replaced by an arbitrary recursive function, and instead of the function $ F \uparrow x $, its Gödel number is used (i.e., the code of its algorithmic description; see also Arithmetization).

References

[1]	R. Peter, “Recursive functions”, Acad. Press (1967). (Translated from German)
[2]	H. Rogers, Jr., “Theory of recursive functions and effective computability”, McGraw-Hill (1967), pp. 164–165.
[3]	J. Barwise, “Admissible sets and structures”, Springer (1975).

Comments

J. von Neumann was the first to prove that the method of transfinite recursion is legitimate.

References

[a1]	A. Levy, “Basic set theory”, Springer (1979).