Computable ordinal

In mathematics, specifically computability and set theory, an ordinal ${\displaystyle \alpha }$ is said to be computable or recursive if there is a computable well-ordering ⁠${\displaystyle \prec }$⁠ of a computable subset ⁠${\displaystyle S}$⁠ of the natural numbers having the order type ⁠${\displaystyle \alpha }$⁠. This means that given any ⁠${\displaystyle x\in \mathbb {N} }$⁠ it is decidable whether ⁠${\displaystyle x\in S}$⁠, and given any ⁠${\displaystyle x,y\in S}$⁠ it is decidable whether ⁠${\displaystyle x\prec y}$⁠. Equivalently, ⁠${\displaystyle \alpha }$⁠ is computable if it either is finite or is the order type of a computable well-ordering of all natural numbers.¹

It is easy to check that ${\displaystyle \omega }$ is computable. The successor of a computable ordinal is computable, and the set of all computable ordinals is closed downwards.¹ The sum, product, and power of a pair of computable ordinals are also computable.

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

The computable ordinals are exactly the ordinals that have an ordinal notation in Kleene's ${\displaystyle {\mathcal {O}}}$.⁴