From 07a832fa8443e2d82e044a05190e8373f0d512e8 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 7 Feb 2013 16:09:58 +0100 Subject: =?UTF-8?q?Existence=20of=20=CF=89=E2=82=81=20versus=20existence?= =?UTF-8?q?=20of=20=F0=9D=92=AB(=CF=89).?= 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