Transfinite recursion

From Encyclopedia of Mathematics
Revision as of 17:17, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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).


[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)


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


[a1] A. Levy, "Basic set theory" , Springer (1979)
How to Cite This Entry:
Transfinite recursion. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by N.V. Belyakin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article