Recursive ordinal
In mathematics, specifically set theory, an ordinal [math]\displaystyle{ \alpha }[/math] is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type [math]\displaystyle{ \alpha }[/math]. It is easy to check that [math]\displaystyle{ \omega }[/math] 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 [math]\displaystyle{ \omega^{CK}_1 }[/math]. The Church–Kleene ordinal is a limit ordinal. An ordinal is recursive if and only if it is smaller than [math]\displaystyle{ \omega^{CK}_1 }[/math]. Since there are only countably many recursive relations, there are also only countably many recursive ordinals. Thus, [math]\displaystyle{ \omega^{CK}_1 }[/math] is countable.
The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's [math]\displaystyle{ \mathcal{O} }[/math].
See also
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
 |
