summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2013-01-31 16:01:11 (GMT)
committerDavid A. Madore <david+git@madore.org>2013-01-31 16:01:11 (GMT)
commit4f164fcecde1edc08b0a1ef92166a9b4d99ef98f (patch)
treeeee69597abb3f0fcd4f4ff18a7ab2202a378dc1f
parent41d022555a842d4b78bfb130bd10dd52bc00d9b2 (diff)
downloadordinal-zoo-4f164fcecde1edc08b0a1ef92166a9b4d99ef98f.zip
ordinal-zoo-4f164fcecde1edc08b0a1ef92166a9b4d99ef98f.tar.gz
ordinal-zoo-4f164fcecde1edc08b0a1ef92166a9b4d99ef98f.tar.bz2
Various stuff around stability.
-rw-r--r--ordinal-zoo.tex149
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