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, ${\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 x-computable if it is computable from a Turing machine with an oracle state that queries x. The relativized Church–Kleene ordinal ${\displaystyle \omega _{1}^{x}}$ is the supremum of the order types of x-computable relations. The Friedman-Jensen-Sacks theorem states that for every countable admissible ordinal ${\displaystyle \alpha }$, there exists a set 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