Recursive ordinal
From Wikipedia, the free encyclopedia
In mathematics, specifically set theory, an ordinal α is said to be recursive if there is a recursive binary relation R that well-orders a subset 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 .
[edit] See also
[edit] References
- 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