From 07a832fa8443e2d82e044a05190e8373f0d512e8 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 7 Feb 2013 16:09:58 +0100
Subject: Existence of ω₁ versus existence of 𝒫(ω).
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 ordinal-zoo.tex | 71 ++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 55 insertions(+), 16 deletions(-)

diff --git a/ordinal-zoo.tex b/ordinal-zoo.tex
index 996acc5..161781d 100644
--- a/ordinal-zoo.tex
+++ b/ordinal-zoo.tex
@@ -363,22 +363,24 @@ gap ordinal (\cite[theorem 4.17 on p. 377]{MarekSrebrny1973}).
 length $\beta$ in the constructible universe.
 
 \ordinal\label{OmegaOneSmallestModelKPWithOmegaOne} The ordinal $\beta
-= \omega_1^{L_\alpha}$ where $\alpha$ is the smallest ordinal such
-that $L_\alpha \models \mathsf{KP}+$“$\omega_1$ exists” (\CHECKTHIS:
-$\alpha$ is the same as the first admissible $\alpha$ which is not
-locally countable, because the existence of an uncountable set implies
-the existence of an uncountable ordinal since Choice holds in
-$L_\alpha$).  Then by construction $\beta$ starts a gap of length
-$\alpha = \beta^+$ (the next admissible ordinal).
-
-\ordinal The ordinal $\alpha$ mentioned
-in •\ref{OmegaOneSmallestModelKPWithOmegaOne}.
-
-[\FINDTHIS: is this the start of the first third-order gap in the
-  constructible universe (\cite[§3]{MarekSrebrny1973})? that is, does
-  the existence of $\omega_1$ give the existence of
-  $\mathscr{P}(\omega)$ as $\{x \in L_{\omega_1} : x \subseteq
-  \omega\}$?]
+= \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.
 
 %
 %
@@ -463,6 +465,39 @@ 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}
+
 %
 %
 %
@@ -495,6 +530,10 @@ z(\theta(L_\beta,z))$.  So $L_\beta \models \exists U(\varphi(U))$.
   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
-- 
cgit v1.2.3