Computable ordinal

Short description: Countable ordinal that is the order type of a computable well-ordering of natural numbers

In mathematics, specifically computability and set theory, a computable (or recursive) ordinal is an ordinal number that can be represented as a computable well-ordering of natural numbers.

Definition

An ordinal $\alpha$ is computable if there exists a computable well-ordering $\prec$ of a computable subset $S$ of the natural numbers having the order type $\alpha$. This means that given any $x\in \mathbb{\mathbb{N}}$ it is decidable whether $x\in S$, and given any $x,y\in S$ it is decidable whether $x\prec y$. Alternatively, this condition can be characterized with a single Turing machine that decides whether $x\in S\wedge y\in S\wedge x⪯y$ for any $x,y\in \mathbb{\mathbb{N}}$.

Another equivalent definition states that $\alpha$ is computable if it either is finite or is the order type of a computable well-ordering of all natural numbers. This equivalence holds because, if $S$ is infinite and computable, then one can compute a bijection $f:\mathbb{\mathbb{N}}\to S$ by letting $f(n)$ be the $n$th element of $S$ in the usual ordering of the natural numbers; the search always halts because $S$ is infinite. If $⟨S,\prec ⟩$ is a computable well-ordering with order type $\alpha$, then defining $x{\prec }_{f}y$ iff $f(x)\prec f(y)$ gives a computable well-ordering $⟨\mathbb{\mathbb{N}},{\prec }_f⟩$ with the same order type.

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 $<$ of all natural numbers has order type $\omega$. Since there exists a Turing machine that decides $x<y$, this means that $\omega$ is a computable ordinal.

As another example, the following is the "canonical" construction of a well-ordering $\prec$ of all natural numbers with order type $\omega +\omega$: $$\begin{array}{cccccccccccc}0& 2& 4& 6& 8& \dots & 1& 3& 5& 7& 9& \dots \end{array}$$ An algorithm that decides $x\prec y$ can be as follows: Return true if $x$ is even and $y$ is odd, false if $x$ is odd and $y$ is even, and otherwise return $x<y$. Therefore $\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 $\alpha$ is computable and $\beta <\alpha$, then $\beta$ is computable too. This is because any well-ordering $⟨S,\prec ⟩$ with order type $\alpha$ has an initial segment $⟨S^{\prime },\prec ⟩$ with order type $\beta$, where $S^{\prime }=\{x\in S\mid x\prec x_{\beta }\}$ (for some fixed $x_{\beta }\in S$) is a computable subset of $S$ if $\prec$ is computable.

Church–Kleene ordinal

The supremum of all computable ordinals is called the Church–Kleene ordinal, the first nonrecursive ordinal, and denoted by ${\omega }_1^{\mathsf{C}\mathsf{K}}$. The Church–Kleene ordinal is a limit ordinal. An ordinal is computable if and only if it is smaller than ${\omega }_1^{\mathsf{C}\mathsf{K}}$. Since there are only countably many computable binary relations, there are also only countably many computable ordinals. Thus, ${\omega }_1^{\mathsf{C}\mathsf{K}}$ is countable.

The computable ordinals are exactly the ordinals that have an ordinal notation in Kleene's ${𝒪}$.

See also

• Arithmetical hierarchy
• Large countable ordinal
• Ordinal analysis
• Ordinal notation

References

• The Theory of Recursive Functions and Effective Computability, MIT Press, 1967, ISBN 0-07-053522-1 
• Higher Recursion Theory, Perspectives in mathematical logic, Springer-Verlag, 1990, ISBN 0-387-19305-7 
• Spector, Clifford (1955). "Recursive well-orderings". Journal of Symbolic Logic 20 (2): 151–163. doi:10.2307/2266902.