Computable ordinal

Template:Short description 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 Template:Tmath is computable if there exists a computable well-ordering Template:Tmath of a computable subset Template:Tmath of the natural numbers having the order type Template:Tmath. This means that given any Template:Tmath it is decidable whether Template:Tmath, and given any Template:Tmath it is decidable whether Template:Tmath. Alternatively, this condition can be characterized with a single Turing machine that decides whether Template:Tmath for any Template:Tmath.Template:Sfn

Another equivalent definition states that Template:Tmath is computable if it either is finite or is the order type of a computable well-ordering of all natural numbers.Template:Sfnp This equivalence holds because, if Template:Tmath is infinite and computable, then one can compute a bijection Template:Tmath by letting Template:Tmath be the Template:Tmathth element of Template:Tmath in the usual ordering of the natural numbers; the search always halts because Template:Tmath is infinite. If Template:Tmath is a computable well-ordering with order type Template:Tmath, then defining Template:Tmath iff Template:Tmath gives a computable well-ordering Template:Tmath 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 Template:Tmath of all natural numbers has order type [[Omega (ordinal)|Template:Tmath]]. Since there exists a Turing machine that decides Template:Tmath, this means that Template:Tmath is a computable ordinal.

As another example, the following is the "canonical" construction of a well-ordering Template:Tmath of all natural numbers with order type Template:Tmath: $$\begin{array}{cccccccccccc}0& 2& 4& 6& 8& \dots & 1& 3& 5& 7& 9& \dots \end{array}$$ An algorithm that decides Template:Tmath can be as follows: Return true if Template:Tmath is even and Template:Tmath is odd, false if Template:Tmath is odd and Template:Tmath is even, and otherwise return Template:Tmath. Therefore Template:Tmath 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 Template:Tmath is computable and Template:Tmath, then Template:Tmath is computable too.Template:Sfnp This is because any well-ordering Template:Tmath with order type Template:Tmath has an initial segment Template:Tmath with order type Template:Tmath, where Template:Tmath (for some fixed Template:Tmath) is a computable subset of Template:Tmath if Template:Tmath 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^{𝖢𝖪}$.Template:Sfnp The Church–Kleene ordinal is a limit ordinal. An ordinal is computable if and only if it is smaller than ${\omega }_1^{𝖢𝖪}$. Since there are only countably many computable binary relations, there are also only countably many computable ordinals. Thus, ${\omega }_1^{𝖢𝖪}$ is countable.

The computable ordinals are exactly the ordinals that have an ordinal notation in Kleene's $𝒪$.Template:Sfnp

See also

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

References

• Template:Citation
• Template:Citation
• Template:Cite journal