\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 \DeclareUnicodeCharacter{00A0}{~} % % \newcommand{\TODO}{\textcolor{red}{TODO}} \newcommand{\REFTHIS}{\textcolor{brown}{REF THIS}} \newcommand{\CHECKTHIS}{\textcolor{orange}{CHECK THIS}} \newcommand{\FIXTHIS}{\textcolor{orange}{FIX THIS}} % \newtheorem{ordinalcnt}{Anything}[section] %\newcounter{ordinalcnt}[section] \newcommand\ordinal{% \refstepcounter{ordinalcnt}\medbreak\noindent•\textbf{\theordinalcnt.} } % % % \begin{document} \section{Recursive ordinals} \setcounter{ordinalcnt}{-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}. \ordinal\label{CollapseMahlo} The collapse of a Mahlo cardinal. This is the proof-theoretic ordinal of $\mathsf{KPM}$. See \cite{Rathjen1990}. \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-\mathsf{Ref}$. See \cite{Rathjen1994}. \ordinal\label{CollapsePiTwoZeroIndescribable} The collapse of a $\Pi^2_0$-indescribable cardinal. This is the proof-theoretic ordinal of $\mathsf{KP} + \Pi_\omega-\mathsf{Ref}$. See \cite[part I]{Stegert2010}. \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 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 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 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 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 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}.) \ordinal 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}. 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 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}. That this ordinal is smaller 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 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}). \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]{Simpson1978} [\CHECKTHIS, probably buried in \cite[§6]{RichterAczel1974}]. % % % \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, \textit{Generalized Recursion Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0, 5–41. \bibitem[Harrington1974]{Harrington1974} Leo Harrington, “The Superjump and the first Recursively Mahlo Ordinal”, \textit{in}: Jens Erik Fenstad \& Peter G. Hinman, \textit{Generalized Recursion Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0, 43–52. \bibitem[Anderaa1974]{Anderaa1974} Stål Anderaa, “Inductive Definitions and their Closure Ordinals”, \textit{in}: Jens Erik Fenstad \& Peter G. Hinman, \textit{Generalized Recursion Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0, 207–220. \bibitem[Cenzer1974]{Cenzer1974} Douglas Cenzer, “Ordinal Recursion and Inductive Definitions”, \textit{in}: Jens Erik Fenstad \& Peter G. Hinman, \textit{Generalized Recursion Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0, 221–264. \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[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[RichterAczel1974]{RichterAczel1974} Wayne Richter \& Peter Aczel, “Inductive Definitions and Reflecting Properties of Admissible Ordinals”, \textit{in}: Jens Erik Fenstad \& Peter G. Hinman, \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, \textit{Generalized Recursion Theory II} (Oslo, 1977), North-Holland (1978), ISBN 0-444-85163-1, 355–390. \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}