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 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 after \omega (an ordinal \alpha is called admissible if .) The -recursive subsets of \omega are exactly the \Delta^1_1 subsets of \omega. The notation is in reference to \omega_1, 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. Some old sources use \omega_1 to denote the Church-Kleene ordinal. For a set, a set is x-computable if it is computable from a Turing machine with an oracle state that queries x. The relativized Church–Kleene ordinal \omega_1^x is the supremum of the order types of x-computable relations. The Friedman-Jensen-Sacks theorem states that for every countable admissible ordinal \alpha, there exists a set x such that. , first defined by Stephen G. Simpson 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 is a model of \Pi^1 1-comprehension.

Recursively ordinals

The \alphath admissible ordinal is sometimes denoted by \tau_\alpha. 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. An ordinal \alpha is called recursively inaccessible if it is admissible and a limit of admissibles. Alternatively, \alpha is recursively inaccessible iff \alpha is the \alphath admissible ordinal, or iff, an extension of Kripke–Platek set theory stating that each set is contained in a model of Kripke–Platek set theory. Under the condition that ("every set is hereditarily countable"), \alpha is recursively inaccessible iff is a model of \Delta^1 2-comprehension. An ordinal \alpha is called recursively hyperinaccessible if it is recursively inaccessible and a limit of recursively inaccessibles, or where \alpha is the \alphath recursively inaccessible. Like "hyper-inaccessible cardinal", different authors conflict on this terminology. An ordinal \alpha is called recursively Mahlo if it is admissible and for any \alpha-recursive function there is an admissible such that (that is, \beta is closed under f). Mirroring the Mahloness hierarchy, \alpha is recursively \gamma-Mahlo for an ordinal \gamma if it is admissible and for any \alpha-recursive function there is an admissible ordinal such that \beta is closed under f, and \beta is recursively \delta-Mahlo for all. An ordinal \alpha is called recursively weakly compact if it is \Pi_3-reflecting, or equivalently, 2-admissible. These ordinals have strong recursive Mahloness properties, if α is \Pi_3-reflecting then \alpha is recursively \alpha-Mahlo.

Weakenings of stable ordinals

An ordinal \alpha is stable if L_\alpha is a \Sigma_1-elementary-substructure of L, denoted. These are some of the largest named nonrecursive ordinals appearing in a model-theoretic context, for instance greater than for any computably axiomatizable theory T. Proposition 0.7. There are various weakenings of stable ordinals:

Larger nonrecursive ordinals

Even larger nonrecursive ordinals include: