diff options
| -rw-r--r-- | ordinal-zoo.tex | 149 |
1 files changed, 125 insertions, 24 deletions
diff --git a/ordinal-zoo.tex b/ordinal-zoo.tex index 2fef5e0..410459c 100644 --- a/ordinal-zoo.tex +++ b/ordinal-zoo.tex @@ -21,6 +21,7 @@ % % \mathchardef\emdash="07C\relax +\mathchardef\hyphen="02D\relax \DeclareUnicodeCharacter{00A0}{~} % % @@ -132,12 +133,12 @@ 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-\mathsf{Ref}$. +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-\mathsf{Ref}$. +of $\mathsf{KP} + \Pi_\omega\hyphen\mathsf{Ref}$. See \cite[part I]{Stegert2010}. (Compare •\ref{WeaklyStable}.) \ordinal The proof-theoretic ordinal of $\mathsf{Stability}$: @@ -175,7 +176,7 @@ 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$ +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 @@ -193,8 +194,8 @@ 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 +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 @@ -228,7 +229,7 @@ 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 +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 @@ -243,9 +244,9 @@ 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}). +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?] @@ -254,7 +255,77 @@ $\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}]. +[\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}). % % @@ -268,24 +339,35 @@ the ordinal of •\ref{SigmaOneOne} \cite[theorem 6.4]{Simpson1978} \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 + Fenstad \& Peter G. Hinman (eds.), \textit{Generalized Recursion Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0, - 43–52. + 5–41. \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. + 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, \textit{Generalized Recursion Theory} (Oslo, 1972), - North-Holland (1974), ISBN 0-7204-2276-0, 221–264. + 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 @@ -298,6 +380,14 @@ the ordinal of •\ref{SigmaOneOne} \cite[theorem 6.4]{Simpson1978} 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. @@ -306,18 +396,29 @@ the ordinal of •\ref{SigmaOneOne} \cite[theorem 6.4]{Simpson1978} 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, \textit{Generalized Recursion Theory} (Oslo, 1972), - North-Holland (1974), ISBN 0-7204-2276-0, 301–381. + 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, \textit{Generalized Recursion + 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 |