Difference between revisions of "Stable"
BartekChom (Talk | contribs) (<cite>RichterAczel1974:InductiveDefinitions</cite>) |
|||
(8 intermediate revisions by 2 users not shown) | |||
Line 8: | Line 8: | ||
=== Variants === | === Variants === | ||
+ | |||
+ | An ordinal $\alpha$ is called '''$\beta$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ (for $\alpha<\beta$) (Definition 1.17).<cite>RichterAczel1974:InductiveDefinitions</cite> | ||
There are quite a few (weakened) variants of stability:<cite>Madore2017:OrdinalZoo</cite> | There are quite a few (weakened) variants of stability:<cite>Madore2017:OrdinalZoo</cite> | ||
− | *A countable ordinal $\alpha$ is called '''$(+\beta)$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\alpha+\beta}$. | + | *A countable ordinal $\alpha$ is called '''$(+\beta)$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\alpha+\beta}$ ($\alpha$ is $\alpha+\beta$-stable<cite>RichterAczel1974:InductiveDefinitions</cite>). |
− | *A countable ordinal $\alpha$ is called '''$({}^+)$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible]] ordinal larger than $\alpha$. | + | *A countable ordinal $\alpha$ is called '''$({}^+)$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible]] ordinal larger than $\alpha$ ($\alpha$ is $\alpha^+$-stable<cite>RichterAczel1974:InductiveDefinitions</cite>). |
*A countable ordinal $\alpha$ is called '''$({}^{++})$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least admissible ordinal larger than an admissible ordinal larger than $\alpha$. | *A countable ordinal $\alpha$ is called '''$({}^{++})$-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least admissible ordinal larger than an admissible ordinal larger than $\alpha$. | ||
*A countable ordinal $\alpha$ is called '''inaccessibly-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible#Computably_inaccessible_ordinal|computably inaccessible]] ordinal larger than $\alpha$. | *A countable ordinal $\alpha$ is called '''inaccessibly-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible#Computably_inaccessible_ordinal|computably inaccessible]] ordinal larger than $\alpha$. | ||
Line 17: | Line 19: | ||
*A countable ordinal $\alpha$ is called '''doubly $(+1)$-stable''' iff there is a $(+1)$-stable ordinal $\beta>\alpha$ such that $L_\alpha\prec_{\Sigma_1}L_\beta$. | *A countable ordinal $\alpha$ is called '''doubly $(+1)$-stable''' iff there is a $(+1)$-stable ordinal $\beta>\alpha$ such that $L_\alpha\prec_{\Sigma_1}L_\beta$. | ||
*A countable ordinal $\alpha$ is called '''nonprojectible''' iff the set of all $\beta<\alpha$ such that $L_\beta\prec_{\Sigma_1}L_\alpha$ is unbounded in $\alpha$. | *A countable ordinal $\alpha$ is called '''nonprojectible''' iff the set of all $\beta<\alpha$ such that $L_\beta\prec_{\Sigma_1}L_\alpha$ is unbounded in $\alpha$. | ||
− | Further variants have appeared in proof theory, for example [https://arxiv.org/pdf/1104.1842.pdf#page=15 | + | Further variants have appeared in proof theory, for example in Arai's paper analyzing subsystems of the second-order arithmetic $Z_2$ "[https://arxiv.org/pdf/1104.1842.pdf#page=15 Introducing the hardline in proof theory]". |
== Properties == | == Properties == | ||
===Variants=== | ===Variants=== | ||
A related property is nonprojectibility, which has many equivalent characterizations. An ordinal $\alpha$ is nonprojectible iff: | A related property is nonprojectibility, which has many equivalent characterizations. An ordinal $\alpha$ is nonprojectible iff: | ||
− | *$L_\alpha\vDash\Sigma_1\textrm{-separation}$ (Arai, "A sneak preview of proof theory of ordinals, 1997) | + | *$L_\alpha\vDash\Sigma_1\textrm{-separation}$ (Arai, "[https://arxiv.org/abs/1102.0596 A sneak preview of proof theory of ordinals]", 1997) |
− | *There is no [https://en.wikipedia.org/wiki/Alpha_recursion_theory $\alpha$-recursive] injection $f:\alpha\rightarrow\alpha'$ for some $\alpha'\in\alpha$ (Arai, "A sneak preview of proof theory of ordinals, 1997) | + | *There is no [https://en.wikipedia.org/wiki/Alpha_recursion_theory $\alpha$-recursive] injection $f:\alpha\rightarrow\alpha'$ for some $\alpha'\in\alpha$ (Arai, "[https://arxiv.org/abs/1102.0596 A sneak preview of proof theory of ordinals]", 1997) |
*Alternatively, there is no $\alpha$-recursive injection<!--Devlin says its domain is γ∈L_α?--> $f:A\rightarrow\alpha$ mapping a bounded subset of $\alpha$ to $\alpha$. (Devlin, "An introduction to the fine structure of the constructible hierarchy", 1974) | *Alternatively, there is no $\alpha$-recursive injection<!--Devlin says its domain is γ∈L_α?--> $f:A\rightarrow\alpha$ mapping a bounded subset of $\alpha$ to $\alpha$. (Devlin, "An introduction to the fine structure of the constructible hierarchy", 1974) | ||
<!--alpha nonprojectible iff Sigma_1(L_alpha) n P(alpha) subseteq L_alpha? http://saulkripkecenter.org/wp-content/uploads/2019/03/Transfinite-Recursion-Constructible-Sets-and-Analogues-of-Cardinals-PUBLIC.pdf#page=13--> | <!--alpha nonprojectible iff Sigma_1(L_alpha) n P(alpha) subseteq L_alpha? http://saulkripkecenter.org/wp-content/uploads/2019/03/Transfinite-Recursion-Constructible-Sets-and-Analogues-of-Cardinals-PUBLIC.pdf#page=13--> | ||
The sizes of the least $(+1)$-stable ordinal and the least nonprojectible ordinal lie between the least recursively weakly compact and the least [[Admissible#Higher_admissibility|$Σ_2$-admissible]] (the same for other weakened variants of stability defined above). <cite>Madore2017:OrdinalZoo</cite> | The sizes of the least $(+1)$-stable ordinal and the least nonprojectible ordinal lie between the least recursively weakly compact and the least [[Admissible#Higher_admissibility|$Σ_2$-admissible]] (the same for other weakened variants of stability defined above). <cite>Madore2017:OrdinalZoo</cite> | ||
+ | |||
+ | $(+1)$-stable ordinals are exactly the $Π^1_0$-reflecting (i.e., $Π_n$-reflecting for every $n ∈ ω$<cite>Madore2017:OrdinalZoo</cite>) ordinals (Theorem 1.18). $({}^+)$-stable ordinals are exactly the $Π^1_1$-reflecting ordinals (Theorem 1.19).<cite>RichterAczel1974:InductiveDefinitions</cite><!--Page 18 in the PDF, with label 16--> | ||
+ | |||
+ | Properties of nonprojectible ordinals: | ||
+ | *If $\alpha$ is nonprojectible, not only is $\alpha$ $\Pi_1$-reflecting on $\{\beta\in\alpha:L_\beta\prec_{\Sigma_1}L_\alpha\}$, but also $\alpha$ is $\Pi_2$-reflecting on $\{\beta\in\alpha:L_\beta\prec_{\Sigma_1}L_\alpha\}$. (E. Kranakis, [https://www.sciencedirect.com/science/article/pii/0003484382900225 Reflection and partition properties of admissible ordinals], theorem 2.2) <!--Proof of the necessary claim appears not to need the Sigma_n-cofinality or powerset assumptions--> | ||
===Stable=== | ===Stable=== | ||
− | On the other hand, if there is an ordinal $\eta$ such that $L_\eta\models\text{ZFC}$ (i.e. the minimal [[heights of models|height]] of a [[Transitive ZFC model|transitive model of $\text{ZFC}$]]) then it is smaller than the least stable ordinal. In fact, the least stable ordinal is greater than the minimal heights of models of arbitrarily sufficiently satisfiable theories [http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm#A6.2]<!--See Taranovsky's "Ordinal Notation" page, section 6.2, find quote "arbitrary sufficiently satisfiable axioms"--> (a more detailed characterization is given [http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.zamlynska-1afccedc-bd3e-45b8-a2f9-3cbb4c6000bb/c/rm21101.pdf | + | On the other hand, if there is an ordinal $\eta$ such that $L_\eta\models\text{ZFC}$ (i.e. the minimal [[heights of models|height]] of a [[Transitive ZFC model|transitive model of $\text{ZFC}$]]) then it is smaller than the least stable ordinal. In fact, the least stable ordinal is greater than the minimal heights of models of arbitrarily sufficiently satisfiable theories [http://web.mit.edu/dmytro/www/other/OrdinalNotation.htm#A6.2]<!--See Taranovsky's "Ordinal Notation" page, section 6.2, find quote "arbitrary sufficiently satisfiable axioms"--> (a more detailed characterization is given in proposition 0.7 of (W. Marek, K. Rasmussen, [http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.zamlynska-1afccedc-bd3e-45b8-a2f9-3cbb4c6000bb/c/rm21101.pdf Spectrum of L])). |
The smallest stable ordinal is also the smallest ordinal $\alpha$ that is $\Sigma_2^1$-[[reflecting]] <cite>Madore2017:OrdinalZoo</cite> (where $\Sigma$ here denotes an extension of the Levy hierarchy<!--RichterAczel73?? Different source-->) or that $L_\alpha\models\text{KP}+\Sigma_2^1\text{-reflection}$, which in turn is the smallest ordinal which is not the order-type of any $\Delta_2^1$-ordering of the natural numbers. The smallest stable ordinal $\sigma$ has the property that any $\Sigma_1(L_\sigma)$ subset of $\omega$ is $\omega$-finite. <cite>Madore2017:OrdinalZoo</cite> | The smallest stable ordinal is also the smallest ordinal $\alpha$ that is $\Sigma_2^1$-[[reflecting]] <cite>Madore2017:OrdinalZoo</cite> (where $\Sigma$ here denotes an extension of the Levy hierarchy<!--RichterAczel73?? Different source-->) or that $L_\alpha\models\text{KP}+\Sigma_2^1\text{-reflection}$, which in turn is the smallest ordinal which is not the order-type of any $\Delta_2^1$-ordering of the natural numbers. The smallest stable ordinal $\sigma$ has the property that any $\Sigma_1(L_\sigma)$ subset of $\omega$ is $\omega$-finite. <cite>Madore2017:OrdinalZoo</cite> |
Latest revision as of 09:32, 13 May 2022
Stability was developed as a large countable ordinal property in order to try to generalize the different strengthened variants of admissibility. More specifically, they capture the various assertions that $L$$_\alpha\models\text{KP}+A$ for different axioms $A$ by saying that $L_\alpha\models\text{KP}+A$ for many axioms $A$. One could also argue that stability is a weakening of $\Sigma_1$-correctness (which is trivial) to a nontrivial form.
Definition and Variants
Stability is defined using a reflection principle. Let $\Sigma$ denote the "existential side" of the Levy hierarchy, and let $\prec_\Gamma$ denote the elementary substructure relation with respect to a set of formulae $\Gamma$. A countable ordinal $\alpha$ is called stable iff $L_\alpha\prec_{\Sigma_1}L$. [1]
Variants
An ordinal $\alpha$ is called $\beta$-stable iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ (for $\alpha<\beta$) (Definition 1.17).[2]
There are quite a few (weakened) variants of stability:[1]
- A countable ordinal $\alpha$ is called $(+\beta)$-stable iff $L_\alpha\prec_{\Sigma_1}L_{\alpha+\beta}$ ($\alpha$ is $\alpha+\beta$-stable[2]).
- A countable ordinal $\alpha$ is called $({}^+)$-stable iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least admissible ordinal larger than $\alpha$ ($\alpha$ is $\alpha^+$-stable[2]).
- A countable ordinal $\alpha$ is called $({}^{++})$-stable iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least admissible ordinal larger than an admissible ordinal larger than $\alpha$.
- A countable ordinal $\alpha$ is called inaccessibly-stable iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least computably inaccessible ordinal larger than $\alpha$.
- A countable ordinal $\alpha$ is called Mahlo-stable iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least computably Mahlo ordinal larger than $\alpha$; that is, the least $\beta$ such that any $\beta$-recursive function $f:\beta\rightarrow\beta$ has an admissible $\gamma<\beta$ which is closed under $f$.
- A countable ordinal $\alpha$ is called doubly $(+1)$-stable iff there is a $(+1)$-stable ordinal $\beta>\alpha$ such that $L_\alpha\prec_{\Sigma_1}L_\beta$.
- A countable ordinal $\alpha$ is called nonprojectible iff the set of all $\beta<\alpha$ such that $L_\beta\prec_{\Sigma_1}L_\alpha$ is unbounded in $\alpha$.
Further variants have appeared in proof theory, for example in Arai's paper analyzing subsystems of the second-order arithmetic $Z_2$ "Introducing the hardline in proof theory".
Properties
Variants
A related property is nonprojectibility, which has many equivalent characterizations. An ordinal $\alpha$ is nonprojectible iff:
- $L_\alpha\vDash\Sigma_1\textrm{-separation}$ (Arai, "A sneak preview of proof theory of ordinals", 1997)
- There is no $\alpha$-recursive injection $f:\alpha\rightarrow\alpha'$ for some $\alpha'\in\alpha$ (Arai, "A sneak preview of proof theory of ordinals", 1997)
- Alternatively, there is no $\alpha$-recursive injection $f:A\rightarrow\alpha$ mapping a bounded subset of $\alpha$ to $\alpha$. (Devlin, "An introduction to the fine structure of the constructible hierarchy", 1974)
The sizes of the least $(+1)$-stable ordinal and the least nonprojectible ordinal lie between the least recursively weakly compact and the least $Σ_2$-admissible (the same for other weakened variants of stability defined above). [1]
$(+1)$-stable ordinals are exactly the $Π^1_0$-reflecting (i.e., $Π_n$-reflecting for every $n ∈ ω$[1]) ordinals (Theorem 1.18). $({}^+)$-stable ordinals are exactly the $Π^1_1$-reflecting ordinals (Theorem 1.19).[2]
Properties of nonprojectible ordinals:
- If $\alpha$ is nonprojectible, not only is $\alpha$ $\Pi_1$-reflecting on $\{\beta\in\alpha:L_\beta\prec_{\Sigma_1}L_\alpha\}$, but also $\alpha$ is $\Pi_2$-reflecting on $\{\beta\in\alpha:L_\beta\prec_{\Sigma_1}L_\alpha\}$. (E. Kranakis, Reflection and partition properties of admissible ordinals, theorem 2.2)
Stable
On the other hand, if there is an ordinal $\eta$ such that $L_\eta\models\text{ZFC}$ (i.e. the minimal height of a transitive model of $\text{ZFC}$) then it is smaller than the least stable ordinal. In fact, the least stable ordinal is greater than the minimal heights of models of arbitrarily sufficiently satisfiable theories [1] (a more detailed characterization is given in proposition 0.7 of (W. Marek, K. Rasmussen, Spectrum of L)).
The smallest stable ordinal is also the smallest ordinal $\alpha$ that is $\Sigma_2^1$-reflecting [1] (where $\Sigma$ here denotes an extension of the Levy hierarchy) or that $L_\alpha\models\text{KP}+\Sigma_2^1\text{-reflection}$, which in turn is the smallest ordinal which is not the order-type of any $\Delta_2^1$-ordering of the natural numbers. The smallest stable ordinal $\sigma$ has the property that any $\Sigma_1(L_\sigma)$ subset of $\omega$ is $\omega$-finite. [1]
Any $L$-stable ordinal is stable. This is because $L_\alpha^L=L_\alpha$ and $L^L=L$. [3] Any $L$-countable stable ordinal is $L$-stable for the same reason. Therefore, an ordinal is $L$-stable iff it is $L$-countable and stable. This property is the same for all variants of stability.
When $\sigma$ is stable, $L_\sigma$ is $\Sigma_1$-pointwise-definable. $L_{\sigma_{\alpha+1}}$ is pointwise definable for all $\alpha \in \omega_1^L$^{Theorem 4.8} where $\sigma_\alpha$ is consecutive enumeration of stable ordinals.^{before Theorem 4.4}[4]. If $\alpha$ is stable and less then the first stable gap, then $L_\alpha$ is pointwise definable.^{Lemma 4.10}
The intersection of the sets of countable stable ordinals and $\{\beta\in\omega_1:(L_{\beta+1}\setminus L_\beta)\cap P(\omega)=\varnothing\}$ is a very "sparse" set. For example, if we let $f$ enumerate the countable stable ordinals, and let $\alpha=\textrm{min}\{\sigma:L_\sigma\prec_{\Sigma_1}L\land(L_{\alpha+1}\setminus L_\alpha)\cap P(\omega)=\varnothing\}$ (i.e. $\alpha$ is stable gap), then $\alpha=f(\alpha)$.[4]
There are stronger properties then stability:[4]
- (The first ordinal that is not $\Delta^1_n$ is called $\delta_n$.)^{in section 0}
- For $n ≥ 2$^{Theorem 4.16}
- $L_{\delta_n^L} \prec_{\Sigma_{n-1}} L_{\omega_1^L}$ and $\delta_n^L$ is the least ordinal with this property.
- $L_{\delta_n^L}$ is $\Sigma_{n-1}$-pointwise definable and it consists exactly of $\Sigma_{n-1}$-definable elements of $\delta_n^L$.
- $\delta_2$ is the least stable ordinal.^{Theorem 3.1}
References
- Madore, David. A zoo of ordinals. , 2017. www bibtex
- Richter, Wayne and Aczel, Peter. Inductive Definitions and Reflecting Properties of Admissible Ordinals. Generalized recursion theory : proceedings of the 1972 Oslo symposium, pp. 301-381, 1974. www bibtex
- Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www bibtex
- Marek, W. Stable sets, a characterization of $\beta_2$-models of full second order arithmetic and some related facts. Fundamenta Mathematicae 82(2):175-189, 1974. www bibtex