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 of a computable subset of the natural numbers having the order type α {\displaystyle \alpha }.

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 ω 1 C K {\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 ω 1 C K {\displaystyle \omega _{1}^{\mathsf {CK}}}. Since there are only countably many computable binary relations, there are also only countably many computable ordinals. Thus, ω 1 C K {\displaystyle \omega _{1}^{\mathsf {CK}}} is countable.

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

See also

Notes

  • Rogers, Hartley Jr. (1967), The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-07-053522-1
  • Sacks, Gerald (1990), Higher Recursion Theory, Perspectives in mathematical logic, Springer-Verlag, ISBN 0-387-19305-7