\documentclass[12pt,a4paper]{article}  % -*- coding: utf-8 -*-
\usepackage[a4paper]{geometry}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{bm}
\usepackage{stmaryrd}
\usepackage{wasysym}
\usepackage{amsthm}
\usepackage{url}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{tikz}
%\usetikzlibrary{matrix,arrows}
%
%
%
\mathchardef\emdash="07C\relax
\mathchardef\hyphen="02D\relax
\DeclareUnicodeCharacter{00A0}{~}
\newcommand{\trans}{\mathop{\mathrm{trans}}\nolimits}
%
%
\newcommand{\TODO}{\textcolor{red}{TODO}}
\newcommand{\REFTHIS}{\textcolor{brown}{REF THIS}}
\newcommand{\CHECKTHIS}{\textcolor{orange}{CHECK THIS}}
\newcommand{\FIXTHIS}{\textcolor{orange}{FIX THIS}}
\newcommand{\FINDTHIS}{\textcolor{orange}{FIND THIS}}
%
\newtheorem{comcnt}{Anything}[section]
%\newcounter{comcnt}[section]
\newcommand\ordinal{%
\refstepcounter{comcnt}\medbreak\noindent•\textbf{\thecomcnt.} }
\newtheorem{prop}[comcnt]{Proposition}
%
%
%
\begin{document}

\title{A zoo of ordinals}
\author{David A. Madore}
\maketitle

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\textbf{\textcolor{red}{Preliminary version:}} the labels in this
document are subject to change.

None of these results are mine.  The purpose of this document is
simply to collect various pointers to the literature, grouping them by
ordinals they are concerned with, and order these ordinals by size.

\section{Recursive ordinals}

\setcounter{comcnt}{-1}

\ordinal $0$ (zero).  This is the smallest ordinal, and the only one that is
neither successor nor limit.

\ordinal $1$ (one).  This is the smallest successor ordinal.

\ordinal $2$.

\ordinal $42$ (cf. \cite[chapter 27]{Adams1981}).

\ordinal $\omega$.  This is the smallest limit ordinal, and the
smallest infinite ordinal.

\ordinal $\omega+1$.  This is the smallest infinite successor ordinal.

\ordinal $\omega2$.

\ordinal $\omega^2$.

\ordinal $\omega^\omega$.

\ordinal $\omega^{\omega^\omega}$.

\ordinal $\varepsilon_0 = \varphi(1,0)$.  This is the limit of
$\omega, \omega^\omega, \omega^{\omega^\omega}, \ldots$, smallest
fixed point of $\xi \mapsto \omega^\xi$; in general, $\alpha \mapsto
\varepsilon_\alpha = \varphi(1,\alpha)$ is defined as the function
enumerating the fixed points of $\xi \mapsto \omega^\xi$.  This is the
proof-theoretic ordinal of Peano arithmetic.

\ordinal $\varepsilon_1 = \varphi(1,1)$.

\ordinal $\varepsilon_\omega$.

\ordinal $\varepsilon_{\varepsilon_0}$.

\ordinal $\varphi(2,0)$.  This is the limit of $\varepsilon_0,
\varepsilon_{\varepsilon_0}, \ldots$, smallest fixed point of $\xi
\mapsto \varepsilon_\xi$; in general, $\alpha \mapsto
\varphi(\gamma+1,\alpha)$ is defined as the function enumerating the
fixed points of $\xi \mapsto \varphi(\gamma,\xi)$.

\ordinal $\varphi(\omega,0)$.  This is the smallest ordinal $>\omega$
closed under primitive recursive ordinal functions
(\cite[corollary 4.5]{Avigad2002}).

\ordinal The Feferman-Schütte ordinal $\Gamma_0 = \varphi(1,0,0)$
(also $\psi(\Omega^{\Omega})$ for an appropriate collapsing
function $\psi$).  This is the limit of $\varepsilon_0, \penalty0
\varphi(\varepsilon_0,0), \penalty0 \varphi(\varphi(\varepsilon_0)),
\ldots$, smallest fixed point of $\xi \mapsto \varphi(\xi, 0)$.  This
is the proof-theoretic ordinal of $\mathsf{ATR}_0$.

\ordinal The Ackermann ordinal $\varphi(1,0,0,0)$ (also
$\psi(\Omega^{\Omega^2})$ for an appropriate collapsing
function $\psi$).

\ordinal The “small” Veblen ordinal ($\psi(\Omega^{\Omega^\omega})$ for
an appropriate collapsing function $\psi$).  This is the limit of
$\varphi(1,0), \penalty0 \varphi(1,0,0), \penalty0 \varphi(1,0,0,0),
\ldots$, the range of the Veblen functions with finitely many
variables.

\ordinal The “large” Veblen ordinal ($\psi(\Omega^{\Omega^\Omega})$
for an appropriate collapsing function $\psi$).  This is the range of
the Veblen functions with up to that many variables.

\ordinal The Bachmann-Howard ordinal ($\psi(\varepsilon_{\Omega+1})$
for an appropriate collapsing function $\psi$).  This is the
proof-theoretic ordinal of Kripke-Platek set theory ($\mathsf{KP}$).

\ordinal The countable collapse of $\varepsilon_{\Omega_\omega + 1}$
(“Takeuti-Feferman-Buchholz ordinal”), which is the proof-theoretic
ordinal of $\Pi^1_1$-comprehension + transfinite induction.

\ordinal\label{CollapseInaccessible} The countable collapse of
$\varepsilon_{I+1}$ where $I$ is the first inaccessible
(= $\Pi^1_0$-indescribable) cardinal.  This is the proof-theoretic
ordinal of Kripke-Platek set theory augmented by the recursive
inaccessibility of the class of ordinals ($\mathsf{KPi}$), or, on the
arithmetical side, of $\Delta^1_2$-comprehension + transfinite
induction.  See \cite{JaegerPohlers1983}.
(Compare •\ref{RecursivelyInaccessible}.)

\ordinal\label{CollapseMahlo} The countable collapse of
$\varepsilon_{M+1}$ where $M$ is the first Mahlo cardinal.  This is
the proof-theoretic ordinal of $\mathsf{KPM}$.
See \cite{Rathjen1990}.  (Compare •\ref{RecursivelyMahlo}.)

\ordinal\label{CollapseWeaklyCompact} The countable collapse of
$\varepsilon_{K+1}$ where $K$ is the first weakly compact
(= $\Pi^1_1$-indescribable) cardinal.  This is the proof-theoretic
ordinal of $\mathsf{KP} + \Pi_3\hyphen\mathsf{Ref}$.
See \cite{Rathjen1994}.  (Compare •\ref{RecursivelyWeaklyCompact}.)

\ordinal\label{CollapsePiTwoZeroIndescribable} The countable collapse
of $\varepsilon_{\Xi+1}$ where $\Xi$ is the first
$\Pi^2_0$-indescribable cardinal.  This is the proof-theoretic ordinal
of $\mathsf{KP} + \Pi_\omega\hyphen\mathsf{Ref}$.
See \cite[part I]{Stegert2010} (in whose notation this ordinal would
be called $\Psi^{\varepsilon_{\Xi+1}}_{\mathbb{X}}$ where $\mathbb{X}
= (\omega^+; \mathsf{P}_0; \epsilon; \epsilon; 0)$).
(Compare •\ref{WeaklyStable}.)

\ordinal The proof-theoretic ordinal of $\mathsf{Stability}$:
see \cite[part II]{Stegert2010} (in whose notation this ordinal would
be called $\Psi^{\varepsilon_{\Upsilon+1}}_{\mathbb{X}}$ where
$\mathbb{X} = (\omega^+; \mathsf{P}_0; \epsilon; \epsilon; 0)$).

%
\section{Recursively large countable ordinals}

\ordinal\label{ChurchKleene} The Church-Kleene ordinal
$\omega_1^{\mathrm{CK}}$: the smallest admissible ordinal $>\omega$.
This is the smallest ordinal which is not the order type of a
recursive (equivalently: hyperarithmetic) well-ordering on $\omega$.
The $\omega_1^{\mathrm{CK}}$-recursive
(resp. $\omega_1^{\mathrm{CK}}$-semi-recursive) subsets of $\omega$
are exactly the $\Delta^1_1$ (=hyperarithmetic) (resp. $\Pi^1_1$)
subsets of $\omega$, and they are also exactly the subsets recursive
(resp. semi-recursive) in $\mathsf{E}$ (or $\mathsf{E}^\#$, \CHECKTHIS
[this is stated vaguely and without proof in \cite[§2, introductory
    remarks]{HinmanMoschovakis1971}, and also alluded to, but with an
  argument, in \cite[chapter VI, introductory remarks to §6 on
    p. 316]{Hinman1978}; but the essential argument should be Gandy's
  selection theorem, \cite[chapter VI, theorem 4.1 on
    p. 292 or its corollary 4.3 on p. 294]{Hinman1978}]).

\ordinal $\omega_\omega^{\mathrm{CK}}$: the smallest limit of
admissibles.  This ordinal is not admissible.  This is the smallest
$\alpha$ such that $L_\alpha \cap \mathscr{P}(\omega)$ is a model of
$\Pi^1_1$-comprehension (cf. \cite[theorem VII.1.8 on p. 246 and
  theorem VII.5.17 on p. 292 and notes to §VII.5 on
  p. 293]{Simpson2009}).

\ordinal\label{RecursivelyInaccessible} The smallest recursively
inaccessible ordinal: this is the smallest ordinal which is admissible
and limit of admissibles.  This is the smallest ordinal $\alpha$ such
that $L_\alpha \models \mathsf{KPi}$, or, on the arithmetical side,
such that $L_\alpha \cap \mathscr{P}(\omega)$ is a model of
$\Delta^1_2$-comprehension (cf. \cite[theorem VII.3.24 on p. 267 and
  theorem VII.5.17 on p. 292 and
  errata\footnote{\url{http://www.personal.psu.edu/t20/sosoa/typos.pdf}}
  to notes to §VII.5 on p. 293]{Simpson2009}).
(Compare •\ref{CollapseInaccessible}.)

This is the smallest ordinal $\omega_1^{\mathsf{E}_1}$ not the order
type of a well-ordering recursive in the Tugué
functional $\mathsf{E}_1$ (\cite[chapter VIII, theorem 6.6 on
  p. 421]{Hinman1978}), or equivalently, recursive in the hyperjump;
and for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive (resp. semi-recursive) in $\mathsf{E}_1$
(\cite[chapter VIII, corollary 4.16 on p. 412]{Hinman1978}).

This is the smallest $\alpha$ such that $L_\alpha \models
\mathsf{KP}+\mathit{Beta}$, where $\mathit{Beta}$ asserts the
existence of a transitive collapse for any well-founded relation, or
equivalently, the smallest admissible $\alpha$ such that any ordering
which $L_\alpha$ thinks is a well-ordering is, indeed, a
well-ordering: see \cite[theorem 6.1 on p. 291]{Nadel1973}
(compare \cite{Harrison1968} for the negative result concerning the
ordinal $\omega_1^{\mathrm{CK}}$ of •\ref{ChurchKleene}; compare also
\cite{Gostanian1979} and •\ref{SigmaOneOne} for related facts).

\ordinal The smallest recursively hyperinaccessible ordinal: i.e., the
smallest recursively inaccessible which is a limit of recursively
inaccessibles.

\ordinal\label{RecursivelyMahlo} The smallest recursively Mahlo
ordinal: i.e., the smallest admissible ordinal $\alpha$ such that for
any $\alpha$-recursive function $f \colon \alpha \to \alpha$ there is
an admissible $\beta<\alpha$ which is closed under $f$.  This is the
smallest ordinal $\alpha$ such that $L_\alpha \models \mathsf{KPM}$.
(Compare •\ref{CollapseMahlo}.)

This is the smallest ordinal not the order type of a well-ordering
recursive in the superjump (\cite{AczelHinman1974} and
\cite{Harrington1974}); and for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive in the superjump (resp. semirecursive in the partial
normalization of the superjump, \cite[theorem 5 on
  p. 50]{Harrington1974}).

Also note concerning this ordinal: \cite[corollary 9.4(ii) on
  p. 348]{RichterAczel1974}.

\ordinal\label{RecursivelyWeaklyCompact} The smallest
$\Pi_3$-reflecting (``recursively weakly compact'') ordinal.  This can
also be described as the smallest ``$2$-admissible'' ordinal:
see \cite[theorem 1.16 on p. 312]{RichterAczel1974}.
(Compare •\ref{CollapseWeaklyCompact}.)

Also the sup of the closure ordinals for $\Sigma_3$ inductive
operators: \cite[theorem A on p. 303]{RichterAczel1974}.  For this
$\alpha$ the $\alpha$-semi-recursive subsets of $\omega$ are exactly
the $\Sigma_3$-inductively definable subsets of $\omega$
(\cite[theorem A on p. 303 and theorem D on p. 304]{RichterAczel1974};
see also \cite[example 4.12 on p. 370]{Simpson1978}).

\ordinal\label{WeaklyStable} The smallest $(+1)$-stable ordinal, i.e.,
the smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha+1}$.  This is the smallest $\Pi^1_0$-reflecting (i.e.,
$\Pi_n$-reflecting for every $n\in\omega$) ordinal: \cite[theorem 1.18
  on p. 313 and 333]{RichterAczel1974}.

(Compare •\ref{CollapsePiTwoZeroIndescribable}.)

\ordinal\label{PiOneOne} The smallest $(^+)$-stable ordinal, i.e., the
smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha^+}$ where $\alpha^+$ is the smallest admissible
ordinal $>\alpha$.  This is the smallest $\Pi^1_1$-reflecting ordinal:
\cite[theorem 1.19 on p. 313 and 336]{RichterAczel1974}.  Also the sup
of the closure ordinals for $\Pi^1_1$ inductive operators:
\cite[theorem B on p. 303 or 10.7 on p. 355]{RichterAczel1974} and
\cite[theorem A on p. 222]{Cenzer1974}.  For this $\alpha$ the
$\alpha$-semi-recursive subsets of $\omega$ are exactly the
$\Pi^1_1$-inductively definable subsets of $\omega$ (\cite[theorem D
  on p. 304]{RichterAczel1974}; see also \cite[example 4.13 on
  p. 370]{Simpson1978}).

This is the smallest ordinal $\omega_1^{\mathsf{G}_1^\#}$ not the
order type of a well-ordering recursive in the nondeterministic
functional $\mathsf{G}_1^\#$ defined by $\mathsf{G}_1^\#(f) \approx
\{f(0)\}_{(\omega_1^f)^+}(f(1))$; and for this $\alpha$ the
$\alpha$-recursive (resp. $\alpha$-semi-recursive) subsets of $\omega$
are exactly the subsets recursive (resp. semi-recursive) in
$\mathsf{G}_1^\#$ (\cite[theorem 7.4 on p. 238]{Cenzer1974}).

\ordinal\label{SigmaOneOne} The smallest $\Sigma^1_1$-reflecting
ordinal.  Also the sup of the closure ordinals for $\Sigma^1_1$
inductive operators: \cite[theorem B on p. 303 or 10.7 on
  p. 355]{RichterAczel1974}.  For this $\alpha$ the
$\alpha$-semi-recursive subsets of $\omega$ are exactly the
$\Sigma^1_1$-inductively definable subsets of $\omega$
(\cite[theorem D on p. 304]{RichterAczel1974}; see
also \cite[example 4.14 on p. 370]{Simpson1978}).

That this ordinal is greater than that of •\ref{PiOneOne}:
\cite[corollary 1 to theorem 6 on p.213]{Aanderaa1974}; also see:
\cite[theorem 6.5]{Simpson1978} and \cite{GostanianHrbacek1979}.

This is the smallest ordinal $\omega_1^{\mathsf{E}_1^\#}$ not the
order type of a well-ordering recursive in the nondeterministic
version $\mathsf{E}_1^\#$ of the Tugué functional $\mathsf{E}_1$; and
for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive (resp. semi-recursive) in $\mathsf{E}_1^\#$ (combine
\cite[theorem 1 on p. 313, theorem 2 on p. 318]{Aczel1970} and
\cite[theorem D on p. 304]{RichterAczel1974}).

This is the smallest admissible $\alpha$ which is not Gandy, i.e.,
such that every $\alpha$-recursive linear ordering of $\alpha$ of
which $L_{\alpha^+}$ thinks that it is a well-ordering (with
$\alpha^+$ being the next admissible) is, indeed, a well-ordering: see
\cite[theorem 6.6 on p. 377]{Simpson1978} and
\cite[theorem 3.3]{Gostanian1979} (on the terminology ``Gandy
ordinal'', see \cite{AbramsonSacks1976}: in \cite{Gostanian1979} the
same ordinals are called ``good'').

[\FINDTHIS: how stable is this ordinal?]

\ordinal The smallest $(^{++})$-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_{\alpha^{++}}$
where $\alpha^+,\alpha^{++}$ are the two smallest admissible
ordinals $>\alpha$.  This is $\Sigma^1_1$-reflecting and greater than
the ordinal of •\ref{SigmaOneOne} (\cite[theorem 6.4 on
  p. 376]{Simpson1978} and
proposition \ref{PlusPlusStableOrdinalIsSigmaOneOneReflecting} below).

\ordinal The smallest inaccessibly-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta$ where
$\beta$ is the smallest recursively inaccessible
(cf. •\ref{RecursivelyInaccessible}) ordinal $>\alpha$.

\ordinal The smallest Mahlo-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta$ where
$\beta$ is the smallest recursively Mahlo
(cf. •\ref{RecursivelyMahlo}) ordinal $>\alpha$.

\ordinal The smallest doubly $(+1)$-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta
\mathrel{\preceq_1} L_{\beta+1}$ (cf. •\ref{WeaklyStable}).

\ordinal\label{NonprojectibleStable} The smallest stable ordinal under
a nonprojectible ordinal, i.e., the smallest $\alpha$ such that
$L_\alpha \mathrel{\preceq_1} L_\beta$ where $\beta$ is the smallest
nonprojectible (the ordinal of •\ref{Nonprojectible}).

This is the smallest ordinal $\omega_1^{\mathbf{R}}$ not the order
type of a well-ordering recursive in a certain type $3$ functional
$\mathbf{R}$ defined in \cite{Harrington1975}; and for this $\alpha$
the $\alpha$-recursive subsets of $\omega$ are exactly the subsets
recursive in $\mathbf{R}$.  (See also \cite{John1986} and
\cite[example 4.10 on p. 369]{Simpson1978}.)

\ordinal\label{Nonprojectible} The smallest nonprojectible ordinal,
i.e., the smallest $\beta$ such that $\beta$ is a limit of
$\beta$-stable ordinals (ordinals $\alpha$ such that $L_\alpha
\mathrel{\preceq_1} L_\beta$ (cf. •\ref{NonprojectibleStable}); in
other words, the smallest $\beta$ such that $L_\beta \models
\mathsf{KPi}+$“the stable ordinals are unbounded”.  This is the
smallest ordinal $\beta$ such that $L_\beta \models
\mathsf{KP}\omega+\Sigma_1\hyphen\textsf{Sep}$ (cf. \cite[chapter V,
  theorem 6.3 on p. 175]{Barwise1975}), or such that $L_\beta \cap
\mathscr{P}(\omega)$ is a model of $\Pi^1_2$-comprehension
(cf. \cite[theorem VII.3.24 on p. 267 and theorem VII.5.17 on
  p. 292]{Simpson2009}).

In Jensen's terminology (\cite{Jensen1972}), this is the smallest
ordinal $\beta$ such that $\rho_1^\beta > \omega$, and in fact the
smallest $\beta>\omega$ such that $\rho_1^\beta = \beta$: that is, the
smallest ordinal $\beta$ such that every $\Sigma_1(L_\beta)$ subset
of $\omega$ is $\beta$-finite.  Sometimes also called the smallest
“strongly admissible” (or “strongly $\Sigma_1$-admissible”) ordinal.

\ordinal The smallest (weakly) $\Sigma_2$-admissible ordinal.  This is
the smallest ordinal $\beta$ such that $L_\beta \models
\mathsf{KP}\omega+\Delta_2\hyphen\textsf{Sep}$, or such that $L_\beta
\cap \mathscr{P}(\omega)$ is a model of $\Delta^1_3$-comprehension
(cf. \cite[theorem VII.3.24 on p. 267 and theorem VII.5.17 on
  p. 292]{Simpson2009}).

In Jensen's terminology (\cite{Jensen1972}), this is the smallest
ordinal $\beta$ such that $\eta_2^\beta > \omega$, and in fact the
smallest $\beta>\omega$ such that $\eta_2^\beta = \beta$: that is, the
smallest ordinal $\beta$ such that every $\Delta_2(L_\beta)$ subset
of $\omega$ is $\beta$-finite.

In the terminology of \cite[appendix]{MarekSrebrny1973}, this is the
first $\Delta_2$-gap ordinal.

\ordinal The ordinal of ramified analysis (often written $\beta_0$).
This is the smallest $\beta$ such that $L_\beta \models \bigwedge_n
\Sigma_n\hyphen\textsf{Sep}$ (the full separation scheme), or such
that $L_\beta \cap \mathscr{P}(\omega)$ is a model of full
second-order analysis (second-order comprehension), and in fact
$L_\beta \models \mathsf{ZFC}^-$ (that is, $\mathsf{ZFC}$ minus the
powerset axiom).

This starts the first gap in the constructible universe, and this gap
is of length $1$: see \cite{Putnam1963} and \cite[corollary 4.5 on
  p. 374]{MarekSrebrny1973}.

Note that this ordinal is $(+1)$-stable (cf. •\ref{WeaklyStable}) but
not $(+2)$-stable: \cite[corollary to theorem 6.14 on
  p. 384]{MarekSrebrny1973}.

\ordinal The start of the first gap of length $2$ in the constructible
universe.  If $\beta$ is this ordinal then $\beta$ is the $\beta$-th
gap ordinal (\cite[theorem 4.17 on p. 377]{MarekSrebrny1973}).

\ordinal The first ordinal $\beta$ which starts a gap of
length $\beta$ in the constructible universe.

\ordinal\label{OmegaOneSmallestModelKPWithOmegaOne} The ordinal $\beta
= \omega_1^{L_\alpha}$ where $\alpha$ is ordinal
of •\ref{SmallestModelKPWithOmegaOne}.  Then by construction $\beta$
starts a gap of length $\alpha = \beta^+$ (the next admissible
ordinal).

\ordinal\label{SmallestModelKPWithOmegaOne} The smallest ordinal
$\alpha$ such that $L_\alpha \models \mathsf{KP}+$“$\omega_1$ exists”,
i.e., the smallest admissible $\alpha$ which is not locally countable,
or equivalently, the smallest $\alpha$ such that $L_\alpha \models
\mathsf{KP}+$“$\mathscr{P}(\omega)$ exists”
(cf. proposition \ref{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}).

\ordinal The smallest ordinal $\alpha$ such that $L_\alpha \models
\mathsf{ZFC}^-+$“$\omega_1$ exists”, or equivalently such that
$L_\alpha \models \mathsf{ZFC}^-+$“$\mathscr{P}(\omega)$ exists”
(cf. proposition \ref{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}).
This is the start of the first third-order gap (\cite[theorem 3.7 on
  p. 372]{MarekSrebrny1973}) in the constructible universe.

%
%
%

\ordinal\label{OmegaOneSmallestModelZFC} The smallest uncountable
ordinal $\omega_1^{L_\alpha}$ in the smallest model $L_{\alpha}$
of $\mathsf{ZFC}$, assuming it exists (see •\ref{SmallestModelZFC}).
This ordinal is $\alpha$-stable.

\ordinal\label{SmallestModelZFC} The smallest ordinal $\alpha$ such
that $L_\alpha \models \mathsf{ZFC}$ (assuming it exists), i.e., the
height of the minimal model of $\mathsf{ZFC}$.

\ordinal\label{Stable} The smallest stable ordinal $\sigma$, i.e., the
smallest $\sigma$ such that $L_\sigma \mathrel{\preceq_1} L$, or
equivalently $L_\sigma \mathrel{\preceq_1} L_{\omega_1}$.  The set
$L_\sigma$ is the set of all $x$ which are $\Sigma_1$-definable in $L$
without parameters (\cite[chapter V, corollary 7.9(i) on
  p. 182]{Barwise1975}).

This ordinal is projectible to $\omega$ (i.e., in Jensen's
terminology), $\rho_1^\sigma = \omega$ (\cite[chapter V,
  theorem 7.10(i) on p. 183]{Barwise1975}).

This is the smallest ordinal $\delta^1_2$ which not the order type of
a well-ordering $\Delta^1_2$ on $\omega$; and in fact, for this
$\sigma = \delta^1_2$, the $\sigma$-recursive
(resp. $\sigma$-semi-recursive) subsets of $\omega$ are exactly the
$\Delta^1_2$ (resp. $\Sigma^1_2$) subsets of $\omega$
(\cite[chapter V, theorem 8.2 on p. 189 and corollary 8.3 on
  p. 191]{Barwise1975}).

This is also the smallest $\Sigma^1_2$-reflecting ordinal
(\cite{Richter1975}).

\bigbreak

\textbf{\textcolor{orange}{Note:}} This document should probably not
start listing large cardinals, because \textbf{(0)} the fact that one
implies the other nonwithstanding, this is about “ordinals”, not
“cardinals”, \textbf{(1)} they are already well covered elsewhere
(see, e.g., \cite{Kanamori1997}) and \textbf{(2)} we don't want to
start making assumptions, e.g., about whether $\omega_1^L$ is or is
not equal to $\omega_1$, but without making such assumptions it is no
longer possible to correctly order definitions.  Perhaps a median way
would be to assume $V=L$ for ordering, forget about measurable
cardinals and whatnot, and still include inaccessibles, Mahlo, weakly
compact, etc.

%
%
%

\section{Various statements}

Again, none of these statements is due to me, they are well-known
facts for which I couldn't find a suitable published proof.

\begin{prop}\label{PlusPlusStableOrdinalIsSigmaOneOneReflecting}
If $\alpha$ is such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha^{++}}$ (where $\alpha^+,\alpha^{++}$ are the two smallest
admissible ordinals $>\alpha$) then $\alpha$ is
$\Sigma^1_1$-reflecting.  (Stated in \cite[theorem 6.4 on
  p. 376]{Simpson1978}.)
\end{prop}
\begin{proof}
Assume $L_\alpha \models \exists U(\varphi(U))$ where $\varphi$ is a
$\Pi^1_0$ (=first-order) formula with constants in $L_\alpha$ and the
extra relation symbol $U$.  We want to show that there exists
$\beta<\alpha$ such that $L_\beta \models \exists U(\varphi(U))$.

Now by \cite[theorem 6.2 on p. 334]{RichterAczel1974} (applied to the
negation of $\exists U(\varphi(U))$) we can find a $\Pi_1$ formula
$\forall z(\psi(S,z))$ (with the same constants as $\varphi$) such
that for any countable transitive set $A$ containing these constants
and any admissible $B\ni A$ we have $B \models \forall z(\theta(A,z))$
iff $A \models \exists U(\varphi(U))$.

In particular, $L_{\alpha^+} \models \forall z(\theta(L_\alpha,z))$.
So $L_{\alpha^+} \models \exists A(\trans(A) \land \penalty0
(A\models\Theta+V{=}L) \land \penalty0 \forall z(\theta(A,z)))$, were
$\Theta$ is a statement which translates the adequacy of $A$ (see
\cite{Jech1978} (13.9) and lemmas 13.2 and 13.3 p. 110–112, or
\cite{Jech2003}, (13.12) and (13.13) p. 188).  So in turn
$L_{\alpha^{++}} \models \exists C(\trans(C) \land \penalty0
(C\models\mathsf{KP}+V{=}L) \land \penalty0 (C \models \exists
A(\trans(A) \land \penalty100 (A\models\Theta+V{=}L) \land \penalty100
\forall z(\theta(A,z)))))$.  But this is a $\Sigma_1$ formula with
constants in $L_\alpha$, so by the assumption we have $L_\alpha
\models$ the same thing.  So there is $C \in L_\alpha$ transitive and
containing the constants of $\varphi$, and which is necessarily an
$L_\gamma$ (for $\gamma<\alpha$) because $C \models
\mathsf{KP}+V{=}L$, such that $L_\gamma \models \exists A(\trans(A)
\land \penalty0 (A\models\Theta+V{=}L) \land \penalty0 \forall
z(\theta(A,z)))$.  So in turn there exists $A \in L_\gamma$
transitive, which is necessarily an $L_\beta$ (for $\beta<\gamma$)
because $A \models \Theta+V{=}L$, such that $L_\gamma \models \forall
z(\theta(L_\beta,z))$.  So $L_\beta \models \exists U(\varphi(U))$.
\end{proof}

\begin{prop}\label{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}
The following holds in $\mathsf{KP}$: if $A\subseteq \omega$ is
constructible, then $A \in L_\gamma$ for some countable
ordinal $\gamma$.

In particular, in $\mathsf{KP} + V=L$, if there exists an uncountable
ordinal $\delta$, then $\mathscr{P}(\omega)$ exists and can be defined
as $\{A \in L_\delta : A\subseteq\omega\}$.
\end{prop}
\begin{proof}
We have to verify that the usual proof (cf. \cite[chapter II,
  lemma 5.5 on p. 84]{Devlin1984} or \cite[lemma 13.1 on
  p. 110]{Jech1978} or \cite[theorem 13.20 on p. 190]{Jech2003})
works in $\mathsf{KP}$.

Working in $L$, we can assume that $V=L$ holds.  Also, we can assume
that $\omega$ exists because if every set is finite the result is
trivial.

Since $A$ is constructible there is $\delta$ limit such that $A \in
L_\delta$.  We can define $\Delta_1$-Skolem functions for $L_\delta$
inside $\mathsf{KP}$, and because $\omega$ exists we can use induction
(cf. \cite[remarks following definition 9.1 on p. 38]{Barwise1975}) to
construct the Skolem hull $M$ of $L_\omega \cup \{A\}$ inside
$L_\delta$ (or use \cite[chapter II, lemma 5.3 on p. 83]{Devlin1984}).
Since $M$ is extensional, we can now use the Mostowski collapse $\pi
\colon M \buildrel\sim\over\to N$ (cf. \cite[theorem 7.4 on
  p. 32]{Barwise1975}) to collapse $M$ to a transitive set $N$, which
is necessarily an $L_\gamma$.  Now $M$ is countable by construction,
so $N = L_\gamma$ is also, so $\gamma$ is.  And we have $\pi(A) = A$
so $A \in L_\gamma$ with $\gamma$ countable, as asserted.
\end{proof}

%
%
%

\begin{thebibliography}{}

\bibitem[Aanderaa1974]{Aanderaa1974} Stål Aanderaa, “Inductive
  Definitions and their Closure Ordinals”, \textit{in}: Jens Erik
  Fenstad \& Peter G. Hinman (eds.), \textit{Generalized Recursion
    Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0,
  207–220.

\bibitem[AbramsonSacks1976]{AbramsonSacks1976} Fred G. Abramson \&
  Gerald E. Sacks, “Uncountable Gandy Ordinals”, \textit{J. London
    Math. Soc. (2)} \textbf{14} (1976), 387–392.

\bibitem[Aczel1970]{Aczel1970} Peter Aczel, “Representability in Some
  Systems of Second Order Arithmetic”, \textit{Israel J. Math}
  \textbf{8} (1970), 308–328.

\bibitem[AczelHinman1974]{AczelHinman1974} Peter Aczel \& Peter
  G. Hinman, “Recursion in the Superjump”, \textit{in}: Jens Erik
  Fenstad \& Peter G. Hinman (eds.), \textit{Generalized Recursion
    Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0,
  5–41.

\bibitem[Adams1981]{Adams1981} Douglas Adams, \textit{The Hitchiker's
  Guide to the Galaxy}, Pocket Books (1981), ISBN 0-671-46149-4.

\bibitem[Avigad2002]{Avigad2002} Jeremy Avigad, “An ordinal analysis
  of admissible set theory using recursion on ordinal notations”,
  \textit{J. Math. Log.} \textbf{2} (2002), 91–112.

\bibitem[Barwise1975]{Barwise1975} Jon Barwise, \textit{Admissible
  sets and structures, An approach to definability theory},
  Perspectives in Mathematical Logic \textbf{7}, Springer-Verlag
  (1975), ISBN 3-540-07451-1.

\bibitem[Cenzer1974]{Cenzer1974} Douglas Cenzer, “Ordinal Recursion
  and Inductive Definitions”, \textit{in}: Jens Erik Fenstad \& Peter
  G. Hinman (eds.), \textit{Generalized Recursion Theory} (Oslo,
  1972), North-Holland (1974), ISBN 0-7204-2276-0, 221–264.

\bibitem[Devlin1984]{Devlin1984} Keith Devlin,
  \textit{Constructibility}, Perspectives in Mathematical
  Logic \textbf{6}, Springer-Verlag (1984), ISBN 3-540-13258-9.

\bibitem[Gostanian1979]{Gostanian1979} Richard Gostanian “The next
  admissible ordinal”, \textit{Ann. Math. Logic} \textbf{17} (1979),
  171–203.

\bibitem[GostanianHrbáček1979]{GostanianHrbacek1979} Richard Gostanian
  \& Karel Hrbáček, “A new proof that $\pi^1_1 < \sigma^1_1$”,
  \textit{Z. Math. Logik Grundlag. Math.} \textbf{25} (1979), 407–408.

\bibitem[Harrington1974]{Harrington1974} Leo Harrington, “The
  Superjump and the first Recursively Mahlo Ordinal”, \textit{in}:
  Jens Erik Fenstad \& Peter G. Hinman (eds.), \textit{Generalized
    Recursion Theory} (Oslo, 1972), North-Holland (1974),
  ISBN 0-7204-2276-0, 43–52.

\bibitem[Harrington1975]{Harrington1975} Leo Harrington, “Kolmogorov's
  $R$-operator and the first nonprojectible ordinal”, unpublished
  notes (1975).

\bibitem[Harrison1968]{Harrison1968} Joseph Harrison, “Recursive
  pseudo-well-orderings”, \textit{Trans. Amer. Math. Soc.}
  \textbf{131} (1968), 526–543.

\bibitem[Hinman1978]{Hinman1978} Peter G. Hinman,
  \textit{Recursion-Theoretic Hierarchies}, Perspectives in
  Mathematical Logic \textbf{9}, Springer-Verlag (1978),
  ISBN 3-540-07904-1.

\bibitem[HinmanMoschovakis1971]{HinmanMoschovakis1971} Peter G. Hinman
  \& Yiannis N. Moschovakis, “Computability over the Continuum”,
  \textit{in}: R. O. Gandy \& C. M. E. Yates (eds.), \textit{Logic
    Colloquium '69} (Manchester, 1969), North-Holland (1971), 77–105.

\bibitem[JaegerPohlers1983]{JaegerPohlers1983} Gerhard Jäger \&
  Wolfram Pohlers, “Eine beweistheoretische Untersuchung von
  ($\Delta^1_2$-$\mathsf{CA}$)+($\mathsf{BI}$) und verwandter
  Systeme”, \textit{Bayer. Akad. Wiss.,
    Math.-Natur. Kl. Sitzungsber. 1982} (1983), 1–28.

\bibitem[Jech1978]{Jech1978} Thomas Jech, \textit{Set theory}, Pure
  and Applied Mathematics \textbf{79}, Academic Press (1978),
  ISBN 0-12-381950-4.

\bibitem[Jech2003]{Jech2003} Thomas Jech, \textit{Set theory, The
  third millennium edition, revised and expanded}, Springer Monographs
  in Mathematics, Springer-Verlag (2003), ISBN 3-540-44085-2.

\bibitem[Jensen1972]{Jensen1972} Ronald Björn Jensen, “The fine
  structure of the constructible hierarchy”, \textit{Ann. Math. Logic}
  \textbf{4} (1972), 229–308.

\bibitem[John1986]{John1986} Thomas John, “Recursion in Kolmogorov's
  $R$-operator and the ordinal $\sigma_3$”, \textit{J. Symbolic Logic}
  \textbf{51} (1986), 1–11.

\bibitem[Kanamori1997]{Kanamori1997} Akihiro Kanamori, \textit{The
  Higher Infinite} (corrected first edition), Perspectives in
  Mathematical Logic, Springer-Verlag (1997), ISBN 3-540-57071-3.

\bibitem[MarekSrebrny1973]{MarekSrebrny1973} Wiktor Marek \& Marian
  Srebrny, “Gaps in the Constructible Universe”,
  \textit{Ann. Math. Logic} \textbf{6} (1974), 359–394.

\bibitem[Nadel1973]{Nadel1973} Mark Nadel, “Scott Sentences and
  Admissible Sets”, \textit{Ann. Math. Logic} \textbf{7} (1974),
  267–294.

\bibitem[Putnam1963]{Putnam1963} Hilary Putnam, “A Note on
  Constructible Sets of Integers”, \textit{Notre Dame J. Formal Logic}
  \textbf{4} (1963), 270–273.

\bibitem[Rathjen1990]{Rathjen1990} Michael Rathjen, “Ordinal Notations
  Based on a Weakly Mahlo Cardinal”, \textit{Arch. Math. Logic}
  \textbf{29} (1990), 249–263.

\bibitem[Rathjen1994]{Rathjen1994} Michael Rathjen, “Proof theory of
  reflection”, \textit{Ann. Pure Appl. Logic} \textbf{68} (1994),
  181–224.

\bibitem[Richter1975]{Richter1975} Wayne Richter, “The Least
  $\Sigma^1_2$ and $\Pi^1_2$ Reflecting Ordinals”, \textit{in}: Gert
  H. Müller, Arnold Oberschelp \& Klaus Potthoff,
  \textit{$\models$ISILC Logic Conference} (Kiel, 1974),
  Springer-Verlag \textit{Lecture Notes in Math.} \textbf{499} (1975),
  ISBN 3-540-07534-8, 568–578.

\bibitem[RichterAczel1974]{RichterAczel1974} Wayne Richter \& Peter
  Aczel, “Inductive Definitions and Reflecting Properties of
  Admissible Ordinals”, \textit{in}: Jens Erik Fenstad \& Peter
  G. Hinman (eds.), \textit{Generalized Recursion Theory} (Oslo,
  1972), North-Holland (1974), ISBN 0-7204-2276-0, 301–381.

\bibitem[Simpson1978]{Simpson1978} Stephen G. Simpson, “Short Course
  on Admissible Recursion Theory”, \textit{in}: Jens Erik Fenstad,
  R. O. Gandy \& Gerald E. Sacks (eds.), \textit{Generalized Recursion
    Theory II} (Oslo, 1977), North-Holland (1978), ISBN 0-444-85163-1,
  355–390.

\bibitem[Simpson2009]{Simpson2009} Stephen G. Simpson,
  \textit{Subsystems of Second-Order Arithmetic} (second edition),
  Perspectives in Logic, ASL (2009), ISBN 978-0-521-88439-6.

\bibitem[Stegert2010]{Stegert2010} Jan-Carl Stegert, \textit{Ordinal
  Proof Theory of Kripke-Platek Set Theory Augmented by Strong
  Reflection Principles}, PhD dissertation (Westfälischen
  Wilhelms-Universität Münster), 2010.

\end{thebibliography}

\end{document}
