In mathematics, specifically set theory, an ordinal
α
is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type
α
.
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. The supremum of all recursive ordinals is called the Church-Kleene ordinal and denoted by
ω
1
C
K
. Indeed, an ordinal is recursive if and only if it is smaller than
ω
1
C
K
. Since there are only countably many recursive relations, there are also only countably many recursive ordinals. Thus,
ω
1
C
K
is countable.
The recursive ordinals are exactly the ordinals that have an ordinal notation in Kleene's
O
.
