Computable ordinal explained
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
.
It is easy to check that
is computable. The
successor of a computable ordinal is computable, and the
set of all computable ordinals is
closed downwards.
The supremum of all computable ordinals is called the Church–Kleene ordinal, the first nonrecursive ordinal, and denoted by
. The Church–Kleene ordinal is a
limit ordinal. An ordinal is computable if and only if it is smaller than
. Since there are only countably many computable relations, there are also only
countably many computable ordinals. Thus,
is countable.
The computable ordinals are exactly the ordinals that have an ordinal notation in Kleene's
.
See also
References
- Hartley Rogers Jr. The Theory of Recursive Functions and Effective Computability, 1967. Reprinted 1987, MIT Press, (paperback),
- Gerald Sacks Higher Recursion Theory. Perspectives in mathematical logic, Springer-Verlag, 1990.