In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using recursive ordinal notationss.

The Church–Kleene ordinal and variants

The smallest non-recursive ordinal is the Church–Kleene ordinal, named after Alonzo Church and S. C. Kleene; its order type is the set of all recursive ordinals. Since the successor of a recursive ordinal is recursive, the Church–Kleene ordinal is a limit ordinal. It is also the smallest ordinal that is not hyperarithmetical, and the smallest admissible ordinal.

, the first uncountable ordinal to denote the Church–Kleene ordinal.

-computable if it is computable from a Turing machine with an oracle is the supremum.

, first defined by Stephen G. Simpson is a model of \Pi^1_1-comprehension.

Recursively [X] ordinals

.

Recursively [X] ordinals, where [X] typically represents a large cardinal property, are kinds of nonrecursive ordinals. Rathjen has called these ordinals the "recursively large counterparts" of X, however the use of "recursively large" here is not to be confused with the notion of an ordinal being recursive.

is called recursively inaccessibleth admissible ordinal,, an extension of Kripke–Platek set theory ("every set is hereditarily countable is a model of \Delta^1_2-comprehension.

is called recursively hyperinaccessibleth recursively inaccessible. Like "hyper-inaccessible cardinal", different authors conflict on this terminology.

is called recursively Mahlo). Mirroring the Mahloness hierarchy is -Mahlo.

is called recursively weakly compact-reflecting, or equivalently,-Mahlo.

Weakenings of stable ordinals

-elementary-substructure..Proposition 0.7. There are various weakenings of stable ordinals:

-stable iff.

• .

• .

  .

• -reflecting.

• -stable.

• . The smallest Mahlo-stable ordinal is larger than the smallest inaccessibly-stable.

• -stable ordinal is larger than the smallest Mahlo-stable.

Larger nonrecursive ordinals

Even larger nonrecursive ordinals include:

• is the smallest nonprojectible ordinal.

• is a limit of is unbounded in .

• is a model of second-order comprehension without the axiom of power set.

• . This ordinal has been characterized by Toshiyasu Arai.

• .

• The least stable ordinal.

References