{{Short description|Countable ordinal that is the order type of a computable subset of the natural numbers}} In mathematics, specifically computability and set theory, an ordinal <math>\alpha</math> is said to be '''computable''' or '''recursive''' if there is a computable well-ordering {{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 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 {{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 of a computable ordinal and the sum, product, and power of a pair of computable ordinals are all computable.
The set of all computable ordinals is 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 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 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 <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}}