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 \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. Thus, \omega^{CK}_1 is countable.

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

[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