path: root/ordinal-zoo.tex

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

\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$.

\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 closed
under primitive recursive ordinal functions.

\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}) =
\psi(\Omega_2)$ for an appropriate collapsing function $\psi$).  This
is the proof-theoretic ordinal of Kripke-Platek set
theory ($\mathsf{KP}$).

\ordinal The collapse of $\Omega_\omega$ (“Takeuti-Feferman-Buchholz
ordinal”), which is the proof-theoretic ordinal of
$\Pi^1_1$-comprehension.  [\CHECKTHIS: there may be a confusion
  between $\Omega_\omega$ and $\Omega_{\omega+1}$ in the collapse.]

\ordinal\label{CollapseInaccessible} The collapse of an 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.
See \cite{JaegerPohlers1983}.
(Compare •\ref{RecursivelyInaccessible}.)

\ordinal\label{CollapseMahlo} The collapse of a Mahlo cardinal.  This
is the proof-theoretic ordinal of $\mathsf{KPM}$.
See \cite{Rathjen1990}.  (Compare •\ref{RecursivelyMahlo}.)

\ordinal\label{CollapseWeaklyCompact} The collapse of a 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 collapse of a
$\Pi^2_0$-indescribable cardinal.  This is the proof-theoretic ordinal
of $\mathsf{KP} + \Pi_\omega\hyphen\mathsf{Ref}$.
See \cite[part I]{Stegert2010}.  (Compare •\ref{WeaklyStable}.)

\ordinal The proof-theoretic ordinal of $\mathsf{Stability}$:
see \cite[part II]{Stegert2010}.

%
\section{Recursively large countable ordinals}

\ordinal 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).

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

\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.  (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}).

\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 gerater than that of •\ref{PiOneOne}:
\cite[corollary 1 to theorem 6 on p.213]{Anderaa1974}; also see:
\cite[theorem 6.5]{Simpson1978}.

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}).

[\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{KP}+$“$\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}).

%
%
%

\section{Various statements}

\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[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[Anderaa1974]{Anderaa1974} Stål Anderaa, “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[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[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[Hinman1978]{Hinman1978} Peter G. Hinman,
  \textit{Recursion-Theoretic Hierarchies}, Perspectives in
  Mathematical Logic \textbf{9}, Springer-Verlag (1978),
  ISBN 3-540-07904-1.

\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[MarekSrebrny1973]{MarekSrebrny1973} Wiktor Marek \& Marian
  Srebrny, “Gaps in the Constructible Universe”,
  \textit{Ann. Math. Logic} \textbf{6} (1974), 359–394.

\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}