summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2013-01-30 19:17:51 +0100
committerDavid A. Madore <david+git@madore.org>2013-01-30 19:17:51 +0100
commit27404099a1b7fbf4316b32c84f2725eefba371e5 (patch)
treee05f327b54e6bf28925098e0b8e3d06a82bfa56a
downloadordinal-zoo-27404099a1b7fbf4316b32c84f2725eefba371e5.tar.gz
ordinal-zoo-27404099a1b7fbf4316b32c84f2725eefba371e5.tar.bz2
ordinal-zoo-27404099a1b7fbf4316b32c84f2725eefba371e5.zip
Start writing down a zoo of ordinals.
-rw-r--r--ordinal-zoo.tex324
1 files changed, 324 insertions, 0 deletions
diff --git a/ordinal-zoo.tex b/ordinal-zoo.tex
new file mode 100644
index 0000000..9a25dc3
--- /dev/null
+++ b/ordinal-zoo.tex
@@ -0,0 +1,324 @@
+\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}