Difference between revisions of "Stable"

From Cantor's Attic
Jump to: navigation, search
(Variants)
(Properties: Hard to read)
(5 intermediate revisions by the same user not shown)
Line 13: Line 13:
 
*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$.
 
*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 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 '''Mahlo-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible|computably Mahlo]] ordinal larger than $\alpha$; that is, the least $\beta$ such that any [https://en.wikipedia.org/wiki/Alpha_recursion_theory $\beta$-recursive] function $f:\beta\rightarrow\beta$ has an admissible $\gamma<\beta$ which is closed under $f$.
+
*A countable ordinal $\alpha$ is called '''Mahlo-stable''' iff $L_\alpha\prec_{\Sigma_1}L_{\beta}$ where $\beta$ is the least [[admissible#Recursively_Mahlo_and_further|computably Mahlo]] ordinal larger than $\alpha$; that is, the least $\beta$ such that any [https://en.wikipedia.org/wiki/Alpha_recursion_theory $\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 '''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$.
Line 22: Line 22:
  
 
Nonprojectibility has many equivalent properties. An ordinal $\alpha$ is nonprojectible iff:
 
Nonprojectibility has many equivalent properties. An ordinal $\alpha$ is nonprojectible iff:
*There is no [https://en.wikipedia.org/wiki/Alpha_recursion_theory $\alpha$-recursive] function mapping a bounded subset of $\alpha$ to $\alpha$. <!--Devlin, "An introduction to the fine structure of the constructible hierarchy", 1974?-->
 
 
*$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, "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)
+
*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)
 +
*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?-->
  
 
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>

Revision as of 15:11, 2 August 2021

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

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}$.
  • 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 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 this paper by Arai analyzing subsystems of the second-order arithmetic $Z_2$.

Properties

Nonprojectibility has many equivalent properties. 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$.

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]

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.

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$. [2] 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.

References

  1. Madore, David. A zoo of ordinals. , 2017. www   bibtex
  2. Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www   bibtex
Main library