Recursive Ordinal
Get Recursive Ordinal essential facts below. View Videos or join the Recursive Ordinal discussion. Add Recursive Ordinal to your PopFlock.com topic list for future reference or share this resource on social media.
Recursive Ordinal

In mathematics, specifically set theory, an ordinal ${\displaystyle \alpha }$ is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type ${\displaystyle \alpha }$.

It is easy to check that ${\displaystyle \omega }$ 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 ${\displaystyle \omega _{1}^{CK}}$. The Church-Kleene ordinal is a limit ordinal. An ordinal is recursive if and only if it is smaller than ${\displaystyle \omega _{1}^{CK}}$. Since there are only countably many recursive relations, there are also only countably many recursive ordinals. Thus, ${\displaystyle \omega _{1}^{CK}}$ is countable.

The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's ${\displaystyle {\mathcal {O}}}$.

## 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