RECURSIVE ORDINAL

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 $omega$ 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 $omega\_1$ and denote it by $omega^\{CK\}\_1$. 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. Since $omega\_1$ is regular, $omega^\{CK\}\_1$ is countable.
The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's $mathcal\{O\}$.

Contents

See also

References

See also

★ Arithmetical hierarchy

★ Large countable ordinals

★ Ordinal notation

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