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, $\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 $\omega$ (an ordinal $\alpha$ is called admissible if $L_\alpha \models \mathsf{KP}$ .) The $\omega_1^{\mathsf{CK}}$ -recursive subsets of $\omega$ are exactly the $\Delta^1_1$ subsets of $\omega$ .D. Madore, [http://www.madore.org/~david/math/ordinal-zoo.pdf A Zoo of Ordinals] (2017). Accessed September 2021.

The notation $\omega_1^{\mathsf{CK}}$ is in reference to $\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 $\omega_1$ to denote the Church-Kleene ordinal.W. Richter, P. Aczel, [https://www.duo.uio.no/handle/10852/44063 Inductive Definitions and Reflecting Properties of Admissible Ordinals] (1973, p.15). Accessed 2021 October 28.

For a set $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 $\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 $\alpha$ , there exists a set $x$ such that $\alpha=\omega_1^x$ .{{citation

| last1=Sacks | first1=Gerald E.

| title=Countable admissible ordinals and hyperdegrees

| date=1976

| journal=Advances in Mathematics

| volume=19

| issue=2

| pages=213–262

| doi=10.1016/0001-8708(76)90187-0 | doi-access=}}

$\omega_\omega^{\mathsf{CK}}$ , first defined by Stephen G. Simpson{{citation needed|date=May 2023}} 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 $L_\alpha \cap \mathsf{P}(\omega)$ is a model of $\Pi^1_1$ -comprehension.D. Madore, [http://www.madore.org/~david/math/ordinal-zoo.pdf A Zoo of Ordinals] (2017). Accessed September 2021.

Recursively ordinals

The $\alpha$ th admissible ordinal is sometimes denoted by $\tau_\alpha$ .P. G. Hinman, Recursion-Theoretic Hierarchies (1978), pp.419--420. Perspectives in Mathematical Logic, ISBN 3-540-07904-1.J. Barwise, Admissible Sets and Structures (1976), pp.174--176. Perspectives in Logic, Cambridge University Press, ISBN 3-540-07451-1.

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

| last1=Rathjen | first1=Michael

| title=Proof theory of reflection

| journal=Annals of Pure and Applied Logic

| volume=68

| issue=2

| date=1994

| pages=181–224

| doi=10.1016/0168-0072(94)90074-4 | doi-access=free

| url=https://www1.maths.leeds.ac.uk/~rathjen/Ehab.pdf}} Rathjen has called these ordinals the "recursively large counterparts" of x,M. Rathjen, "The Realm of Ordinal Analysis" (2006). [https://web.archive.org/web/20231207051454/https://www1.maths.leeds.ac.uk/~rathjen/realm.pdf Archived] 7 December 2023. however the use of "recursively large" here is not to be confused with the notion of an ordinal being recursive.

An ordinal $\alpha$ is called recursively inaccessible if it is admissible and a limit of admissibles. Alternatively, $\alpha$ is recursively inaccessible iff $\alpha$ is the $\alpha$ th admissible ordinal, or iff $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 $L_\alpha\vDash\textrm{V=HC}$ ("every set is hereditarily countable"), $\alpha$ is recursively inaccessible iff $L_\alpha \cap \mathsf{P}(\omega)$ is a model of $\Delta^1_2$ -comprehension.W. Marek, [http://matwbn.icm.edu.pl/ksiazki/fm/fm101/fm101120.pdf Some comments on the paper by Artigue, Isambert, Perrin, and Zalc] (1976), ICM. Accessed 19 May 2023.

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

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

An ordinal $\alpha$ is called recursively weakly compact if it is $\Pi_3$ -reflecting, or equivalently, 2-admissible. These ordinals have strong recursive Mahloness properties, if α is $\Pi_3$ -reflecting then $\alpha$ is recursively $\alpha$ -Mahlo.

Weakenings of stable ordinals

An ordinal $\alpha$ is stable if $L_\alpha$ is a $\Sigma_1$ -elementary-substructure of $L$ , denoted $L_\alpha\preceq_1 L$ .J. Barwise, Admissible Sets and Structures (1976), Cambridge University Press, Perspectives in Logic. These are some of the largest named nonrecursive ordinals appearing in a model-theoretic context, for instance greater than $\min\{\alpha: L_\alpha \models T\}$ for any computably axiomatizable theory $T$ .W. Marek, K. Rasmussen, {{WorldCat|oclc=1280819208|name=Spectrum of L}} ([https://eudml.org/doc/268487 EuDML] page), Państwowe Wydawn. Accessed 2022-12-01.^{Proposition 0.7}. There are various weakenings of stable ordinals:

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

Larger nonrecursive ordinals

Even larger nonrecursive ordinals include:

The least ordinal $\alpha$ such that $L_\alpha \preceq_1 L_\beta$ where $\beta$ is the smallest nonprojectible ordinal.
An ordinal $\alpha$ is nonprojectible if $\alpha$ is a limit of $\alpha$ -stable ordinals, or; if the set $X = \left\{ \beta < \alpha \mid L_\beta \preceq_1 L_\alpha\right\}$ is unbounded in $\alpha$ .
The ordinal of ramified analysis, often written as $\beta_0$ . This is the smallest $\beta$ such that $L_\beta \cap \mathsf{P}(\omega)$ is a model of second-order comprehension, or $L_\beta \models \mathsf{ZFC^{-}}$ , which is $\mathsf{ZFC}$ without the axiom of power set.
The least ordinal $\alpha$ such that $L_\alpha \models \mathsf{KP} + \text{'}\omega_1\text{ exists'}$ . This ordinal has been characterized by Toshiyasu Arai.T. Arai, [https://arxiv.org/abs/1102.0596 A Sneak Preview of Proof Theory of Ordinals] (1997, p.17). Accessed 2021 October 28.
The least ordinal $\alpha$ such that $L_\alpha \models \mathsf{ZFC^{-}} + \text{'}\omega_1\text{ exists'}$ .
The least stable ordinal.

References

{{Citation|last1=Church|first1=Alonzo|title=Formal definitions in the theory of ordinal numbers.|journal=Fundamenta Mathematicae |volume=28|pages=11–21|year=1937|jfm=63.0029.02|last2=Kleene|first2=S. C.|doi=10.4064/fm-28-1-11-21 |author1-link=Alonzo Church|author2-link=Stephen Cole Kleene|doi-access=free}}
{{citation|last1=Church|url=https://www.ams.org/bull/1938-44-04/S0002-9904-1938-06720-1/ |title=The constructive second number class

|journal= Bull. Amer. Math. Soc.|volume= 44 |year=1938|pages= 224–232|doi=10.1090/S0002-9904-1938-06720-1|first1=Alonzo|issue=4|doi-access=free}}

{{citation|title= On Notation for Ordinal Numbers

|first= S. C.|last= Kleene

|doi= 10.2307/2267778|publisher= Vol. 3, No. 4|jstor=2267778|s2cid= 34314018}}

{{Citation | last1=Rogers | first1=Hartley |authorlink = Hartley Rogers| title=The Theory of Recursive Functions and Effective Computability | orig-year=1967 | publisher=First MIT press paperback edition | isbn=978-0-262-68052-3 | year=1987}}
{{Citation | last1=Simpson | first1=Stephen G. | title=Subsystems of Second-Order Arithmetic | orig-year=1999 | publisher=Cambridge University Press | isbn=978-0-521-88439-6 | year=2009|volume=2|series=Perspectives in Logic|pages=246, 267, 292–293}}
{{Citation|last1=Richter|first1=Wayne|title=Inductive Definitions and Reflecting Properties of Admissible Ordinals|pages=312–313, 333|year=1974|last2=Aczel|first2=Peter|author2-link=Peter Aczel|isbn=0-7204-2276-0}}

Category:Proof theory

Category:Ordinal numbers