Nonrecursive ordinal

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 notations.

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.

It is also the smallest ordinal that is not hyperarithmetical, and the smallest admissible ordinal after

, the first uncountable ordinal, which is the set of all countable ordinals, analogously to how the Church-Kleene ordinal is the set of all recursive ordinals.

to denote the Church-Kleene ordinal.

-computable if it is computable from a Turing machine with an oracle state that queries

is the supremum of the order types of

The Friedman-Jensen-Sacks theorem states that for every countable admissible ordinal

, first defined by Stephen G. Simpson[citation needed] is an extension of the Church–Kleene ordinal.

This is the smallest limit of admissible ordinals, yet this ordinal is not admissible.

Alternatively, this is the smallest α such that

th admissible ordinal is sometimes denoted by

[4][5] Recursively "x" ordinals, where "x" typically represents a large cardinal property, are kinds of nonrecursive ordinals.

[6] Rathjen has called these ordinals the "recursively large counterparts" of x,[7] however the use of "recursively large" here is not to be confused with the notion of an ordinal being recursive.

is called recursively inaccessible if it is admissible and a limit of admissibles.

is recursively inaccessible iff

th admissible ordinal,[5] or iff

, an extension of Kripke–Platek set theory stating that each set is contained in a model of Kripke–Platek set theory.

("every set is hereditarily countable"),

is recursively inaccessible iff

is called recursively hyperinaccessible if it is recursively inaccessible and a limit of recursively inaccessibles, or where

Like "hyper-inaccessible cardinal", different authors conflict on this terminology.

is called recursively Mahlo if it is admissible and for any

[2] Mirroring the Mahloness hierarchy,

is called recursively weakly compact if it is

These ordinals have strong recursive Mahloness properties, if α is

[9] These are some of the largest named nonrecursive ordinals appearing in a model-theoretic context, for instance greater than

for any computably axiomatizable theory

There are various weakenings of stable ordinals:[1] Even larger nonrecursive ordinals include:[1]