Definitions

# Recursive ordinal

In mathematics, specifically set theory, an ordinal $alpha$ 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 $alpha$.

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 ordinal and denote it by $omega^\left\{CK\right\}_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^\left\{CK\right\}_1$ is countable.

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