Namespaces
Variants
Actions

Difference between revisions of "Transfinite recursion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (Completed rendering of article in TeX.)
 
Line 1: Line 1:
A method of defining functions on ordinal numbers (cf. [[Ordinal number|Ordinal number]]) or, more generally, on sets endowed with an ordinal structure. The defining equation of transfinite recursion has the form
+
A method of defining functions on [[Ordinal number|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 constructive set|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 [[Algorithms, theory of|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 [[#References|[1]]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937001.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
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|Arithmetization]]).
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937002.png" /> is the  "piece"  of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937003.png" /> to be defined restricted to the set of predecessors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937004.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937005.png" /> 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|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|Algorithms, theory of]]). In particular, this analogy lies at the basis of the various classifications of general recursive functions (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937006.png" /> is replaced by an arbitrary recursive function, and instead of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t093/t093700/t0937007.png" />, its Gödel number is used (i.e. the code of its algorithmic description, see also [[Arithmetization|Arithmetization]]).
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,  "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J. Barwise,  "Admissible sets and structures" , Springer  (1975)</TD></TR></table>
 
  
 +
<table>
 +
<TR><TD valign="top">[1]</TD><TD valign="top">
 +
R. Peter, “Recursive functions”, Acad. Press (1967). (Translated from German)</TD></TR>
 +
<TR><TD valign="top">[2]</TD><TD valign="top">
 +
H. Rogers, Jr., “Theory of recursive functions and effective computability”, McGraw-Hill (1967), pp. 164–165.</TD></TR>
 +
<TR><TD valign="top">[3]</TD><TD valign="top">
 +
J. Barwise, “Admissible sets and structures”, Springer (1975).</TD></TR>
 +
</table>
  
 +
====Comments====
  
====Comments====
 
 
J. von Neumann was the first to prove that the method of transfinite recursion is legitimate.
 
J. von Neumann was the first to prove that the method of transfinite recursion is legitimate.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Levy,   "Basic set theory" , Springer (1979)</TD></TR></table>
+
 
 +
<table>
 +
<TR><TD valign="top">[a1]</TD><TD valign="top">
 +
A. Levy, “Basic set theory”, Springer (1979).</TD></TR>
 +
</table>

Latest revision as of 21:15, 29 January 2017

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).
How to Cite This Entry:
Transfinite recursion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Transfinite_recursion&oldid=16461
This article was adapted from an original article by N.V. Belyakin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article