, specifically set theory
, an ordinal
is said to be recursive
if there is a recursive binary relation
of the natural numbers
and the order type
of that ordering is
It is trivial to check that is recursive, the successor of a recursive ordinal is recursive, and the set of all recursive ordinals is closed downwards. We call the supremum of all recursive ordinals the Church-Kleene ordinal and denote it by . Since the recursive relations are parameterized by the natural numbers, the recursive ordinals are also parameterized by the natural numbers. Therefore, there are only countably many recursive ordinals. Thus, is countable.
The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's .
- Rogers, H. The Theory of Recursive Functions and Effective Computability, 1967. Reprinted 1987, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
- Sacks, G. Higher Recursion Theory. Perspectives in mathematical logic, Springer-Verlag, 1990. ISBN 0-387-19305-7