# Nonrecursive ordinal

(Redirected from Church–Kleene 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, ${\displaystyle \omega _{1}^{\mathsf {CK}}}$, 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 ${\displaystyle \omega }$ (an ordinal ${\displaystyle \alpha }$ is called admissible if ${\displaystyle L_{\alpha }\models {\mathsf {KP}}}$.) The ${\displaystyle \omega _{1}^{\mathsf {CK}}}$-recursive subsets of ${\displaystyle \omega }$ are exactly the ${\displaystyle \Delta _{1}^{1}}$ subsets of ${\displaystyle \omega }$.[1]

The notation ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ is in reference to ${\displaystyle \omega _{1}}$, 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 ${\displaystyle \omega _{1}}$ to denote the Church-Kleene ordinal.[2]

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

${\displaystyle \omega _{\omega }^{\mathsf {CK}}}$, first defined by Stephen G. Simpson[citation needed] 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 ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ is a model of ${\displaystyle \Pi _{1}^{1}}$-comprehension.[1]

## Recursively ordinals

The ${\displaystyle \alpha }$th admissible ordinal is sometimes denoted by ${\displaystyle \tau _{\alpha }}$.[4][5]

Recursively "x" ordinals, where "x" typically represents a large cardinal property, are kinds of nonrecursive ordinals.[6] Rathjen has called these ordinals the "recursively large counterparts" of x,[7] however the use of "recursively large" here is not to be confused with the notion of an ordinal being recursive.

An ordinal ${\displaystyle \alpha }$ is called recursively inaccessible if it is admissible and a limit of admissibles. Alternatively, ${\displaystyle \alpha }$ is recursively inaccessible iff ${\displaystyle \alpha }$ is the ${\displaystyle \alpha }$th admissible ordinal,[5] or iff ${\displaystyle L_{\alpha }\models {\mathsf {KPi}}}$, 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 ${\displaystyle L_{\alpha }\vDash {\textrm {V=HC}}}$ ("every set is hereditarily countable"), ${\displaystyle \alpha }$ is recursively inaccessible iff ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ is a model of ${\displaystyle \Delta _{2}^{1}}$-comprehension.[8]

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

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

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

## Weakenings of stable ordinals

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

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

## Larger nonrecursive ordinals

Even larger nonrecursive ordinals include:[1]

• The least ordinal ${\displaystyle \alpha }$ such that ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ where ${\displaystyle \beta }$ is the smallest nonprojectible ordinal.
• An ordinal ${\displaystyle \alpha }$ is nonprojectible if ${\displaystyle \alpha }$ is a limit of ${\displaystyle \alpha }$-stable ordinals, or; if the set ${\displaystyle X=\left\{\beta <\alpha \mid L_{\beta }\preceq _{1}L_{\alpha }\right\}}$ is unbounded in ${\displaystyle \alpha }$.
• The ordinal of ramified analysis, often written as ${\displaystyle \beta _{0}}$. This is the smallest ${\displaystyle \beta }$ such that ${\displaystyle L_{\beta }\cap {\mathsf {P}}(\omega )}$ is a model of second-order comprehension, or ${\displaystyle L_{\beta }\models {\mathsf {ZFC^{-}}}}$, which is ${\displaystyle {\mathsf {ZFC}}}$ without the axiom of power set.
• The least ordinal ${\displaystyle \alpha }$ such that ${\displaystyle L_{\alpha }\models {\mathsf {KP}}+{\text{'}}\omega _{1}{\text{ exists'}}}$. This ordinal has been characterized by Toshiyasu Arai.[11]
• The least ordinal ${\displaystyle \alpha }$ such that ${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+{\text{'}}\omega _{1}{\text{ exists'}}}$.
• The least stable ordinal.

## References

1. ^ a b c d D. Madore, A Zoo of Ordinals (2017). Accessed September 2021.
2. ^ a b c d W. Richter, P. Aczel, Inductive Definitions and Reflecting Properties of Admissible Ordinals (1973, p.15). Accessed 2021 October 28.
3. ^ Sacks, Gerald E. (1976), "Countable admissible ordinals and hyperdegrees", Advances in Mathematics, 19 (2): 213–262, doi:10.1016/0001-8708(76)90187-0
4. ^ P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.
5. ^ a b J. Barwise, Admissible Sets and Structures (1976), pp.174--176. Perspectives in Logic, Cambridge University Press, ISBN 3-540-07451-1.
6. ^ a b c Rathjen, Michael (1994), "Proof theory of reflection" (PDF), Annals of Pure and Applied Logic, 68 (2): 181–224, doi:10.1016/0168-0072(94)90074-4
7. ^ M. Rathjen, "The Realm of Ordinal Analysis" (2006). Archived 7 December 2023.
8. ^ W. Marek, Some comments on the paper by Artigue, Isambert, Perrin, and Zalc (1976), ICM. Accessed 19 May 2023.
9. ^ J. Barwise, Admissible Sets and Structures (1976), Cambridge University Press, Perspectives in Logic.
10. ^ W. Marek, K. Rasmussen, Spectrum of L in libraries (WorldCat catalog) (EuDML page), Państwowe Wydawn. Accessed 2022-12-01.
11. ^ T. Arai, A Sneak Preview of Proof Theory of Ordinals (1997, p.17). Accessed 2021 October 28.