From 4f164fcecde1edc08b0a1ef92166a9b4d99ef98f Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 31 Jan 2013 17:01:11 +0100
Subject: Various stuff around stability.

---
 ordinal-zoo.tex | 149 +++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 125 insertions(+), 24 deletions(-)

(limited to 'ordinal-zoo.tex')

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
-- 
cgit v1.2.3

