path: root/ordinal-zoo.tex

\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{\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{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}.
(Compare •\ref{RecursivelyInaccessible}.)

\ordinal\label{CollapseMahlo} The collapse of a Mahlo cardinal.  This
is the proof-theoretic ordinal of $\mathsf{KPM}$.
See \cite{Rathjen1990}.  (Compare •\ref{RecursivelyMahlo}.)

\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\hyphen\mathsf{Ref}$.
See \cite{Rathjen1994}.  (Compare •\ref{RecursivelyWeaklyCompact}.)

\ordinal\label{CollapsePiTwoZeroIndescribable} The collapse of a
$\Pi^2_0$-indescribable cardinal.  This is the proof-theoretic ordinal
of $\mathsf{KP} + \Pi_\omega\hyphen\mathsf{Ref}$.
See \cite[part I]{Stegert2010}.  (Compare •\ref{WeaklyStable}.)

\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\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.  (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}).

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

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

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}.  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
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}).

[\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]{Simpson1978}
[\CHECKTHIS, probably similar to \cite[§6]{RichterAczel1974}].

\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 first
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}+\Sigma_1\hyphen\textsf{Sep}$ (cf. \cite[chapter V,
  theorem 6.3 on p. 175]{Barwise1975}), or such that $L_\alpha \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$ subset of $\omega$
is $\beta$-finite.

%
%
%

\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$ 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}).

%
%
%

\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 (eds.), \textit{Generalized Recursion
    Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0,
  5–41.

\bibitem[Anderaa1974]{Anderaa1974} Stål Anderaa, “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[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[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[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[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[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}, 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}