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. The supremum of all recursive ordinals is called the Church-Kleene ordinal and denoted by . Indeed, an ordinal is recursive if and only if it is smaller than . Since there are only countably many recursive relations, there are also only countably many recursive ordinals. Thus, is countable.
- 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
|This set theory-related article is a stub. You can help Wikipedia by expanding it.|