From Cantor's Attic
Jump to: navigation, search

    This article is a stub. Please help us to improve Cantor's Attic by adding information.

An ordinal $\gamma$ is admissible if the $L_\gamma$ level of the constructible universe satisfies the Kripke-Platek axioms of set theory. The term was coined by Richard Platek in 1966. (G. Sacks: Higher Recursion Theory, (part C))

The smallest admissible ordinal is often considered to be $\omega$, the least infinite ordinal. However, some authors include Infinity in the KP axioms, in which case $\omega_1^{CK}$,[1] the least non-computable ordinal, is the least admissible. More generally, for any real $x$, the least ordinal not computable from $x$ is denoted $\omega_1^x$, and is also admissible. Indeed, one has $L_{\omega_1^x}[x]\models\text{KP}$.

The smallest limit of admissible ordinals, $\omega_\omega^{CK}$, is not admissible.[1]

Equivalent definitions

The following properties are also equivalent to admissibility:

$Π_2$-reflecting ordinals are precisely the admissible ordinals $>\omega$. (theorem 1.8)[2]

Higher admissibility

Computably inaccessible ordinal

An ordinal $\alpha$ is computably inaccessible, also known as recursively inaccessible, if it is admissible and a limit of admissible ordinals.[1] If \(f\) enumerates admissible ordinals, recursively inaccessible ordinals are exactly the ordinals \(\alpha\) where \(\alpha=f(\alpha)\).

Recursively Mahlo

An ordinal $α$ is recursively Mahlo iff for any $α$-recursive function $f : α → α$ there is an admissible $β < α$ closed under $f$.[1]


We call $\kappa\in\mathrm{Ad}$ 2-admissible iff every $\xi<\kappa$ such that $\{\xi\}_\kappa$ maps $\kappa$-recursive functions to $\kappa$-recursive functions has a witness ($\alpha\in\mathrm{Ad}$ such that $\xi<\alpha<\kappa$ and $\{\xi\}_\kappa$ maps $\alpha$-recursive functions to $\alpha$-recursive functions). ($\mathrm{Ad}$ is the class of admissible ordinals greater than $\omega$.) TODO: complete definition (definition 1.15)[2]

2-admissible ordinals are precisely the $Π_3$-reflecting ordinals. (theorem 1.16)[2]

2-admissibility is a recursive analogue of 2-regularity, which is equivalent to weak compactness. (theorem 1.14)[2] 2-admissible ordinals can be called recursively weakly compact.[1] More generally, $Π_{n+2}$-reflection is analogous to strong $Π_n^1$-indescribability for all $n>0$. (after definition 1.12)[2]


Some implications between admissibility-related conditions.

Admissibility has been extended using stronger collection axioms. One common formulation is that an ordinal $\alpha$ is $\Sigma_n$-admissible if $L_\alpha\vDash\textrm{RST}\cup\Sigma_n\textrm{-collection}$, where $\textrm{RST}$ denotes rudimentary set theory, i.e. Kripke-Platek set theory without the $\Sigma_0$-collection axiom.

$\Sigma_n$-admissible ordinals need not necessarily satisfy the $\Sigma_n$-separation schema. For example, the least $\Sigma_2$-admissible ordinal doesn't satisfy $\Sigma_2$-separation.

Here are some properties of $\Sigma_n$-admissibility:

Cofinality and projectum

Two concepts used in the study of admissible ordinals are $\Sigma_1$-cofinality and $\Sigma_1$-projecta.

  • The $\Sigma_1$-cofinality of $\beta$ is the least $\xi$ such that there exists a $\Sigma_1$-definable function mapping $\xi$ cofinally into $\beta$. (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976)
  • The $\Sigma_n$-projectum of $\beta$ is equal to the least $\delta$ such that some $\Sigma_n(L_\alpha)$-definable function maps a subset of $\delta$ onto $L_\beta$ (K. Devlin, An introduction to the fine structure of the constructible hierarchy, 1972). (However note that when using the Jensen hierarchy instead of the hierarchy $L$, as the original source does, that behavior may change)
    • Alternatively, when $n=1$, the $\Sigma_1$-projectum of $\beta$ has been given as the least $\gamma\le\beta$ such that a $\beta$-recursive one-to-one function $f:\beta\rightarrow\gamma$ exists. (W. Maass, Inadmissibility, tame R.E. sets and the admissible collapse, 1976) (Sacks, Higher Recursion Theory, p.157) This is claimed to extend to $n>1$ in [1]
    • Alternatively, the $\Sigma_n$-projectum of $\alpha$ is the smallest $\rho$ such that there exists a $\Sigma_n(L_\alpha)$ function $f$ with $f^{\prime\prime}L_\rho=L_\alpha$.[3]p.549

$\Delta_n$-projecta are similar to $\Sigma_n$-projecta, except that its behavior lacks the involvement of a bounded subset of $\delta$, employing just the ordinal $\delta$ instead. (Compare Σn: [2], Δn: [3])



Sometimes, some unintuitive patterns arise in projecta of an ordinal, such as $\Sigma_1\textrm{-proj}(\alpha)=\Sigma_2\textrm{-proj}(\alpha)>\Sigma_3\textrm{-proj}(\alpha)$. In fact, for any binary string, there exists some ordinal $\alpha$ whose sequence $(\Sigma_k\textrm{-proj}(\alpha))_{0\le k\le n}$ has pairwise comparisons $>$, $=$ each determined by that string. [4]


  1. Madore, David. A zoo of ordinals. , 2017. www   bibtex
  2. Richter, Wayne and Aczel, Peter. Inductive Definitions and Reflecting Properties of Admissible Ordinals. Generalized recursion theory : proceedings of the 1972 Oslo symposium, pp. 301-381, 1974. www   bibtex
  3. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
  4. Arai, Toshiyasu. A sneak preview of proof theory of ordinals. , 1997. www   bibtex
Main library