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