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]