Nonrecursive ordinal

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2021) (Learn how and when to remove this template message)

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 ordinal collapsing functions.

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 ω. The notation ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ is in reference to ω
₁, the first uncountable ordinal, which is set of all countable ordinals. The ${\displaystyle \omega _{1}^{\mathsf {CK}}}$-recursive subsets of ω are exactly the ${\displaystyle \Delta _{1}^{1}}$ subsets of ω.

An ordinal α is called admissible if ${\displaystyle L_{\alpha }\models {\mathsf {KP}}}$.

The relativized Church–Kleene ordinal ${\displaystyle \omega _{1}^{x}}$ is the supremum of the x-computable ordinals.

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

Recursively ordinals[]

Recursively x ordinals, not to be confused with recursive ordinals, are kinds of nonrecursive ordinals.

An ordinal ${\displaystyle \alpha }$ is called recursively inaccessible if it is admissible and limit of admissibles (${\displaystyle \alpha }$ is the ${\displaystyle \alpha }$th admissible). Alternatively, it is recursively inaccessible if ${\displaystyle L_{\alpha }\models {\mathsf {KPi}}}$, an extension of Kripke–Platek set theory based on an inaccessible cardinal; or, lastly, on the arithmetical side, such that ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ is a model of ${\displaystyle \Delta _{2}^{1}}$ - comprehension.

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

An ordinal ${\displaystyle \alpha }$ is called recursively weakly compact if it is ${\displaystyle \Pi _{3}}$-reflecting, or equivalently^[1] 2-admissible.

Weakenings of stable ordinals[]

Stable ordinals are some of the largest nonrecursive ordinals. There are various weakenings of stables:

• 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 larger than the smallest recursively weakly compact ordinal.
  • 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 larger than the smallest ${\displaystyle (+1)}$-stable.
• A countable ordinal ${\displaystyle \alpha }$ is called ${\displaystyle (^{++})}$-stable iff ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{++}}}$, where ${\displaystyle \beta ^{+}}$ and ${\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 recursive ordinals[]

• 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 }\prec _{\Sigma _{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^{-}}}}$, ${\displaystyle {\mathsf {ZFC}}}$ without the powerset axiom.
• The least ordinal ${\displaystyle \alpha }$ such that ${\displaystyle L_{\alpha }\models {\mathsf {KP}}+'\omega _{1}{\textrm {exists}}'}$. This ordinal has been characterized by Toshiyasu Arai.^[2]
• The least ordinal ${\displaystyle \alpha }$ such that ${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+'\omega _{1}{\textrm {exists}}'}$.
• The least stable ordinal. A countable ordinal is called stable iff ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L}$.

References[]