Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Computable ordinal

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

Wikipedia contributorsAdapted for Fathomly · View authors
2 min read
Source updated August 24, 2026

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.

01Definition

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 {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\land y\in S\land x\preceq y⁠ for any ⁠x,y\in \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 {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 ⁠\langle S,\prec \rangle⁠ 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 ⁠\langle \mathbb {N} ,\prec _{f}\rangle⁠ with the same order type.

02Examples

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{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}} 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 ⁠\langle S,\prec \rangle⁠ with order type ⁠\alpha⁠ has an initial segment ⁠\langle S',\prec \rangle⁠ with order type ⁠\beta⁠, where ⁠S'=\{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.

03Church-Kleene ordinal

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

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

Watch videos about Computable ordinalExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Computable ordinal”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.

Large countable ordinal

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms.

Ordinal analysis

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.