{{Short description|Countable ordinal that is the order type of a computable subset of the natural numbers}} In [[mathematics]], specifically [[Computability theory|computability]] and [[set theory]], an [[ordinal number|ordinal]] <math>\alpha</math> is said to be '''computable''' or '''recursive''' if there is a [[Computable set|computable]] [[well-order]]ing {{tmath|\prec}} of a computable [[subset]] {{tmath|S}} of the [[natural numbers]] having the [[order type]] {{tmath|\alpha}}. This means that given any {{tmath|x \in \mathbb{N} }} it is [[Recursive language|decidable]] whether {{tmath|x \in S}}, and given any {{tmath|x, y \in S}} it is decidable whether {{tmath|x \prec y}}. Equivalently, {{tmath|\alpha}} is computable if it either is finite or is the order type of a computable well-ordering of all natural numbers.{{sfnp|Sacks|1990|p=9}}
== Examples == All computable ordinals are by definition [[countable]]. Conversely, for many countable ordinals, the "natural" witnesses for countability are also witnesses for computability. For example, the natural ordering {{tmath|<}} of all natural numbers has order type [[Omega (ordinal)|{{tmath|\omega}}]]. Since there exists a [[Turing machine]] that decides {{tmath|x < y}}, this means that {{tmath|\omega}} is a computable ordinal.
As another example, the following is the "canonical" construction of a well-ordering {{tmath|\prec}} of all natural numbers with order type {{tmath|\omega + \omega}}: <math display="block">\begin{matrix} 0 & 2 & 4 & 6 & 8 & \dots & 1 & 3 & 5 & 7 & 9 & \dots \end{matrix}</math> An algorithm that decides {{tmath|x \prec y}} can be as follows: Return true if {{tmath|x}} is even and {{tmath|y}} is odd, false if {{tmath|x}} is odd and {{tmath|y}} is even, and otherwise return {{tmath|x < y}}. Therefore {{tmath|\omega + \omega}} is also computable. In fact, with similar constructions, it can be shown that the [[successor ordinal|successor]] of a computable ordinal and the [[Ordinal arithmetic|sum, product, and power]] of a pair of computable ordinals are all computable.
The [[Set (mathematics)|set]] of all computable ordinals is [[closure (mathematics)|closed]] downwards, i.e., if {{tmath|\alpha}} is computable and {{tmath|\beta < \alpha}}, then {{tmath|\beta}} is computable too.{{sfnp|Sacks|1990|p=9}} This is because any well-ordering {{tmath|\langle \prec, S \rangle}} with order type {{tmath|\alpha}} has an initial segment {{tmath|\langle \prec, S' \rangle}} with order type {{tmath|\beta}}, where {{tmath|1=S' = \{ x \in S \mid x \prec x_\beta\} }} (for some fixed {{tmath|x_\beta \in S}}) is a computable subset of {{tmath|S}}.
== Church–Kleene ordinal == The [[supremum]] of all computable ordinals is called the [[Nonrecursive ordinals|Church–Kleene ordinal]], the first nonrecursive ordinal, and denoted by <math>\omega_1^{\mathsf{CK}}</math>.{{sfnp|Sacks|1990|p=10}} The Church–Kleene ordinal is a [[limit ordinal]]. An ordinal is computable if and only if it is smaller than <math>\omega_1^{\mathsf{CK}}</math>.<ref>This follows immediately from downward closure and the definition of <math>\omega_1^{\mathsf{CK}}</math>.</ref> Since there are only countably many computable binary relations, there are also only [[countable set|countably]] many computable ordinals. Thus, <math>\omega_1^{\mathsf{CK}}</math> is countable.
The computable ordinals are exactly the ordinals that have an [[ordinal notation]] in [[Kleene's O|Kleene's <math>\mathcal{O}</math>]].{{sfnp|Sacks|1990|loc=Theorem 4.4}}
==See also== *[[Arithmetical hierarchy]] *[[Large countable ordinal]] *[[Ordinal analysis]] *[[Ordinal notation]]
== Notes == {{reflist}}
== References == {{refbegin}} *{{citation | last = Rogers | first = Hartley Jr. | author-link = Hartley Rogers Jr. | isbn = 0-07-053522-1 | publisher = MIT Press | title = The Theory of Recursive Functions and Effective Computability | year = 1967}} *{{citation | last = Sacks | first = Gerald | author-link = Gerald Sacks | isbn = 0-387-19305-7 | publisher = Springer-Verlag | series = Perspectives in mathematical logic | title = Higher Recursion Theory | year = 1990}} {{refend}}
[[Category:Set theory]] [[Category:Computability theory]] [[Category:Ordinal numbers]]
{{settheory-stub}}