From ba531178391b854e05b03cb6c38a88fb19dc733b Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 31 Jan 2013 19:08:04 +0100 Subject: Gaps in the constructible universe. --- ordinal-zoo.tex | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 87 insertions(+), 11 deletions(-) diff --git a/ordinal-zoo.tex b/ordinal-zoo.tex index 410459c..3334068 100644 --- a/ordinal-zoo.tex +++ b/ordinal-zoo.tex @@ -273,7 +273,7 @@ $\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta \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 first +$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 @@ -290,8 +290,8 @@ $\beta$-stable ordinals (ordinals $\alpha$ such that $L_\alpha 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}+\Sigma_1\hyphen\textsf{Sep}$ (cf. \cite[chapter V, - theorem 6.3 on p. 175]{Barwise1975}), or such that $L_\alpha \cap +\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}). @@ -299,13 +299,80 @@ smallest ordinal $\beta$ such that $L_\beta \models 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$ subset of $\omega$ -is $\beta$-finite. +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 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\}$?] % % % +\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 @@ -319,10 +386,11 @@ terminology), $\rho_1^\sigma = \omega$ (\cite[chapter V, 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$ 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}). +$\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}). @@ -388,6 +456,14 @@ This is also the smallest $\Sigma^1_2$-reflecting ordinal $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. @@ -416,8 +492,8 @@ This is also the smallest $\Sigma^1_2$-reflecting ordinal 355–390. \bibitem[Simpson2009]{Simpson2009} Stephen G. Simpson, - \textit{Subsystems of Second-Order Arithmetic}, Perspectives in - Logic, ASL (2009), ISBN 978-0-521-88439-6. + \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 -- cgit v1.2.3