Nonrecursive ordinal

In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using recursive ordinal notations.

The Church–Kleene ordinal and variants

The smallest non-recursive ordinal is the Church Kleene ordinal, [math]\displaystyle{ \omega_1^{\mathsf{CK}} }[/math], named after Alonzo Church and S. C. Kleene; its order type is the set of all recursive ordinals. Since the successor of a recursive ordinal is recursive, the Church–Kleene ordinal is a limit ordinal. It is also the smallest ordinal that is not hyperarithmetical, and the smallest admissible ordinal after [math]\displaystyle{ \omega }[/math] (an ordinal [math]\displaystyle{ \alpha }[/math] is called admissible if [math]\displaystyle{ L_\alpha \models \mathsf{KP} }[/math].) The [math]\displaystyle{ \omega_1^{\mathsf{CK}} }[/math]-recursive subsets of [math]\displaystyle{ \omega }[/math] are exactly the [math]\displaystyle{ \Delta^1_1 }[/math] subsets of [math]\displaystyle{ \omega }[/math].

The notation [math]\displaystyle{ \omega_1^{\mathsf{CK}} }[/math] is in reference to [math]\displaystyle{ \omega_1 }[/math], the first uncountable ordinal, which is the set of all countable ordinals, analogously to how the Church-Kleene ordinal is the set of all recursive ordinals. Some old sources use [math]\displaystyle{ \omega_1 }[/math] to denote the Church-Kleene ordinal.

For a set [math]\displaystyle{ x\subseteq\mathbb N }[/math], A set is x-computable if it is computable from a Turing machine with an oracle state that queries x. The relativized Church–Kleene ordinal [math]\displaystyle{ \omega_1^x }[/math] is the supremum of the order types of x-computable relations. The Friedman-Jensen-Sacks theorem states that for every countable admissible ordinal [math]\displaystyle{ \alpha }[/math], there exists a set x such that [math]\displaystyle{ \alpha=\omega_1^x }[/math].

[math]\displaystyle{ \omega_\omega^{\mathsf{CK}} }[/math], first defined by Stephen G. Simpson is an extension of the Church–Kleene ordinal. This is the smallest limit of admissible ordinals, yet this ordinal is not admissible. Alternatively, this is the smallest α such that [math]\displaystyle{ L_\alpha \cap \mathsf{P}(\omega) }[/math] is a model of [math]\displaystyle{ \Pi^1 1 }[/math]-comprehension.

Recursively ordinals

The [math]\displaystyle{ \alpha }[/math]th admissible ordinal is sometimes denoted by [math]\displaystyle{ \tau_\alpha }[/math].

Recursively "x" ordinals, where "x" typically represents a large cardinal property, are kinds of nonrecursive ordinals.

An ordinal [math]\displaystyle{ \alpha }[/math] is called recursively inaccessible if it is admissible and a limit of admissibles. Alternatively, [math]\displaystyle{ \alpha }[/math] is recursively inaccessible iff [math]\displaystyle{ \alpha }[/math] is the [math]\displaystyle{ \alpha }[/math]th admissible ordinal, or iff [math]\displaystyle{ L_\alpha \models \mathsf{KPi} }[/math], an extension of Kripke–Platek set theory stating that each set is contained in a model of Kripke–Platek set theory. Under the condition that [math]\displaystyle{ L_\alpha\vDash\textrm{V=HC} }[/math] ("every set is hereditarily countable"), [math]\displaystyle{ \alpha }[/math] is recursively inaccessible iff [math]\displaystyle{ L_\alpha \cap \mathsf{P}(\omega) }[/math] is a model of [math]\displaystyle{ \Delta^1 2 }[/math]-comprehension.

An ordinal [math]\displaystyle{ \alpha }[/math] is called recursively hyperinaccessible if it is recursively inaccessible and a limit of recursively inaccessibles, or where [math]\displaystyle{ \alpha }[/math] is the [math]\displaystyle{ \alpha }[/math]th recursively inaccessible. Like "hyper-inaccessible cardinal", different authors conflict on this terminology.

An ordinal [math]\displaystyle{ \alpha }[/math] is called recursively Mahlo if it is admissible and for any [math]\displaystyle{ \alpha }[/math]-recursive function [math]\displaystyle{ f : \alpha \rightarrow \alpha }[/math] there is an admissible [math]\displaystyle{ \beta \lt \alpha }[/math] such that [math]\displaystyle{ \left\{f(\gamma)\mid\gamma\in\beta\right\}\subseteq\beta }[/math] (that is, [math]\displaystyle{ \beta }[/math] is closed under [math]\displaystyle{ f }[/math]). Mirroring the Mahloness hierarchy, [math]\displaystyle{ \alpha }[/math] is recursively [math]\displaystyle{ \gamma }[/math]-Mahlo for an ordinal [math]\displaystyle{ \gamma }[/math] if it is admissible and for any [math]\displaystyle{ \alpha }[/math]-recursive function [math]\displaystyle{ f : \alpha \rightarrow \alpha }[/math] there is an admissible ordinal [math]\displaystyle{ \beta \lt \alpha }[/math] such that [math]\displaystyle{ \beta }[/math] is closed under [math]\displaystyle{ f }[/math], and [math]\displaystyle{ \beta }[/math] is recursively [math]\displaystyle{ \delta }[/math]-Mahlo for all [math]\displaystyle{ \delta\lt \gamma }[/math].

An ordinal [math]\displaystyle{ \alpha }[/math] is called recursively weakly compact if it is [math]\displaystyle{ \Pi_3 }[/math]-reflecting, or equivalently, 2-admissible. These ordinals have strong recursive Mahloness properties, if α is [math]\displaystyle{ \Pi_3 }[/math]-reflecting then [math]\displaystyle{ \alpha }[/math] is recursively [math]\displaystyle{ \alpha }[/math]-Mahlo.

Weakenings of stable ordinals

An ordinal [math]\displaystyle{ \alpha }[/math] is stable if [math]\displaystyle{ L_\alpha }[/math] is a [math]\displaystyle{ \Sigma_1 }[/math]-elementary-substructure of [math]\displaystyle{ L }[/math], denoted [math]\displaystyle{ L_\alpha\preceq_1 L }[/math]. These are some of the largest named nonrecursive ordinals appearing in a model-theoretic context, for instance greater than [math]\displaystyle{ \min\{\alpha: L_\alpha \models T\} }[/math] for any computably axiomatizable theory [math]\displaystyle{ T }[/math].^{Proposition 0.7}. There are various weakenings of stable ordinals:

• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called [math]\displaystyle{ (+1) }[/math]-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\alpha+1} }[/math].
  • The smallest [math]\displaystyle{ (+1) }[/math]-stable ordinal is much larger than the smallest recursively weakly compact ordinal: it has been shown that the smallest [math]\displaystyle{ (+1) }[/math]-stable ordinal is [math]\displaystyle{ \Pi_n }[/math]-reflecting for all finite [math]\displaystyle{ n }[/math].
  • In general, a countable ordinal [math]\displaystyle{ \alpha }[/math] is called [math]\displaystyle{ (+\beta) }[/math]-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\alpha+\beta} }[/math].
• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called [math]\displaystyle{ (^+) }[/math]-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\alpha^+} }[/math], where [math]\displaystyle{ \beta^+ }[/math] is the smallest admissible ordinal [math]\displaystyle{ \gt \beta }[/math]. The smallest [math]\displaystyle{ (^+) }[/math]-stable ordinal is again much larger than the smallest [math]\displaystyle{ (+1) }[/math]-stable or the smallest [math]\displaystyle{ (+\beta) }[/math]-stable for any constant [math]\displaystyle{ \beta }[/math].
• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called [math]\displaystyle{ (^{++}) }[/math]-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\alpha^{++}} }[/math], where [math]\displaystyle{ \beta^{++} }[/math] are the two smallest admissible ordinals [math]\displaystyle{ \gt \beta }[/math]. The smallest [math]\displaystyle{ (^{++}) }[/math]-stable ordinal is larger than the smallest [math]\displaystyle{ \Sigma^1_1 }[/math]-reflecting.
• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called inaccessibly-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\beta} }[/math], where [math]\displaystyle{ \beta }[/math] is the smallest recursively inaccessible ordinal [math]\displaystyle{ \gt \alpha }[/math]. The smallest inaccessibly-stable ordinal is larger than the smallest [math]\displaystyle{ (^{++}) }[/math]-stable.
• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called Mahlo-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\beta} }[/math], where [math]\displaystyle{ \beta }[/math] is the smallest recursively Mahlo ordinal [math]\displaystyle{ \gt \alpha }[/math]. The smallest Mahlo-stable ordinal is larger than the smallest inaccessibly-stable.
• A countable ordinal [math]\displaystyle{ \alpha }[/math] is called doubly [math]\displaystyle{ (+1) }[/math]-stable iff [math]\displaystyle{ L_\alpha \preceq_1 L_{\beta} \preceq_1 L_{\beta+1} }[/math]. The smallest doubly [math]\displaystyle{ (+1) }[/math]-stable ordinal is larger than the smallest Mahlo-stable.

Larger nonrecursive ordinals

• The least ordinal [math]\displaystyle{ \alpha }[/math] such that [math]\displaystyle{ L_\alpha \preceq_1 L_\beta }[/math] where [math]\displaystyle{ \beta }[/math] is the smallest nonprojectible ordinal.
• An ordinal [math]\displaystyle{ \alpha }[/math] is nonprojectible if [math]\displaystyle{ \alpha }[/math] is a limit of [math]\displaystyle{ \alpha }[/math]-stable ordinals, or; if the set [math]\displaystyle{ X = \left\{ \beta \lt \alpha \mid L_\beta \preceq_1 L_\alpha\right\} }[/math] is unbounded in [math]\displaystyle{ \alpha }[/math].
• The ordinal of ramified analysis, often written as [math]\displaystyle{ \beta_0 }[/math]. This is the smallest [math]\displaystyle{ \beta }[/math] such that [math]\displaystyle{ L_\beta \cap \mathsf{P}(\omega) }[/math] is a model of second-order comprehension, or [math]\displaystyle{ L_\beta \models \mathsf{ZFC^{-}} }[/math], [math]\displaystyle{ \mathsf{ZFC} }[/math] without the powerset axiom.
• The least ordinal [math]\displaystyle{ \alpha }[/math] such that [math]\displaystyle{ L_\alpha \models \mathsf{KP} + '\omega_1\textrm{ exists}' }[/math]. This ordinal has been characterized by Toshiyasu Arai.
• The least ordinal [math]\displaystyle{ \alpha }[/math] such that [math]\displaystyle{ L_\alpha \models \mathsf{ZFC^{-}} + '\omega_1\textrm{ exists}' }[/math].
• The least stable ordinal.

References

• Church, Alonzo; Kleene, S. C. (1937), "Formal definitions in the theory of ordinal numbers.", Fundamenta Mathematicae 28: 11–21, doi:10.4064/fm-28-1-11-21 
• Church, Alonzo (1938), "The constructive second number class", Bull. Amer. Math. Soc. 44 (4): 224–232, doi:10.1090/S0002-9904-1938-06720-1, https://www.ams.org/bull/1938-44-04/S0002-9904-1938-06720-1/ 
• Kleene, S. C. (1938), "On Notation for Ordinal Numbers", Journal of Symbolic Logic (Vol. 3, No. 4) 3 (4): 150–155, doi:10.2307/2267778 
• Rogers, Hartley (1987), The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3 
• Simpson, Stephen G. (2009), Subsystems of Second-Order Arithmetic, Perspectives in Logic, 2, Cambridge University Press, pp. 246, 267, 292-293, ISBN 978-0-521-88439-6 
• Richter, Wayne; Aczel, Peter (1974), Inductive Definitions and Reflecting Properties of Admissible Ordinals, pp. 312–313, 333, ISBN 0-7204-2276-0