diff options
| -rw-r--r-- | ordinal-zoo.tex | 324 |
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} |