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