Transfinite recursion

A method of defining functions on ordinal numbers (cf. Ordinal number) or, more generally, on sets endowed with an ordinal structure. The defining equation of transfinite recursion has the form

(*)

where is the "piece" of the function to be defined restricted to the set of predecessors of , and is some given function. Many functions and classes important in set theory (for example, the class of Gödel constructible sets, cf. Gödel constructive set) 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 (cf. Algorithms, theory of). 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 (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 (*) is subjected to the following modification: The function is replaced by an arbitrary recursive function, and instead of the function , 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)