Computable ordinal

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, specifically <a href="/facts/Computability_theory/cqDfXwdf">computability</a> and <a href="/facts/Set_theory/1ptfsvUP">set theory</a>, an <a href="/facts/Ordinal_number/GelFLjJt">ordinal</a> 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is said to be computable or recursive if there is a <a href="/facts/Computable_set/rsnT9cLn">computable</a> <a href="/facts/Well-order/GrWEBWlW">well-ordering</a> of a computable <a href="/facts/Subset/SJGERmbA">subset</a> of the <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a> having the <a href="/facts/Order_type/koXjnax6">order type</a> 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
.
It is easy to check that 
 
 
 
 ω
 
 
 {\displaystyle \omega }
 
 is computable. The <a href="/facts/Successor_ordinal/k2acCuUG">successor</a> of a computable ordinal is computable, and the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of all computable ordinals is <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> downwards. 
The <a href="/facts/Supremum/oXCKVopz">supremum</a> of all computable ordinals is called the <a href="/facts/Nonrecursive_ordinals/q9l6rzqA">Church–Kleene ordinal</a>, the first nonrecursive ordinal, and denoted by 
 
 
 
 
 ω
 
 1
 
 
 
 C
 K
 
 
 
 
 
 {\displaystyle \omega _{1}^{\mathsf {CK}}}
 
. The Church–Kleene ordinal is a <a href="/facts/Limit_ordinal/jPCCoPuP">limit ordinal</a>. An ordinal is computable if and only if it is smaller than 
 
 
 
 
 ω
 
 1
 
 
 
 C
 K
 
 
 
 
 
 {\displaystyle \omega _{1}^{\mathsf {CK}}}
 
. Since there are only countably many computable relations, there are also only <a href="/facts/Countable_set/Wj4DmWPv">countably</a> many computable ordinals. Thus, 
 
 
 
 
 ω
 
 1
 
 
 
 C
 K
 
 
 
 
 
 {\displaystyle \omega _{1}^{\mathsf {CK}}}
 
 is countable.
The computable ordinals are exactly the ordinals that have an <a href="/facts/Ordinal_notation/7gjtASPb">ordinal notation</a> in <a href="/facts/Kleene%27s_O/Bu8Tlydf">Kleene's 
 
 
 
 
 
 O
 
 
 
 
 {\displaystyle {\mathcal {O}}}
 
</a>.

Computable ordinal open-in-new

Computable ordinal