Googology Wiki
Advertisement
Googology Wiki

Stable ordinals are large ordinals defined using the notion of \(\Sigma_1\)-elementary substructure on levels of constructible universe.[1] (invalid link)[2][footnote 1]

For a natural number \(n\), let \(M \prec_{\Sigma_n} N\) denote the relation "\(M\) is a \(\Sigma_n\)-elementary substructure of \(N\).

There are special definitions for \(\Sigma_1\)-elementary substructures:

  • An ordinal \(\alpha\) is \((+\beta)\)-stable if \(L_\alpha\prec_{\Sigma_1}L_{\alpha+\beta}\).[citation needed]
  • An ordinal \(\alpha\) is \((^+)\)-stable if \(L_\alpha\prec_{\Sigma_1}L_\beta\) where \(\beta\) is next admissible ordinal after \(\alpha\).[2]
  • An ordinal \(\alpha\) is \((^{++})\)-stable if \(L_\alpha\prec_{\Sigma_1}L_\beta\) where \(\beta\) is next admissible ordinal after the next admissible ordinal after \(\alpha\).[2]
  • An ordinal \(\alpha\) is inaccessibly-stable if \(L_\alpha\prec_{\Sigma_1}L_\beta\) where \(\beta\) is next recursively inaccessible ordinal after \(\alpha\).[2]
  • An ordinal \(\alpha\) is Mahlo-stable if \(L_\alpha\prec_{\Sigma_1}L_\beta\) where \(\beta\) is next recursively Mahlo ordinal after \(\alpha\).[2]
  • An ordinal \(\alpha\) is doubly \((+\beta)\)-stable if there exists ordinal \(\gamma\) such that \(L_\alpha\prec_{\Sigma_1}L_\gamma\prec_{\Sigma_1}L_{\gamma+\beta}\).[citation needed]
  • An ordinal \(\alpha\) is nonprojectible if \(\sup\{\beta<\alpha|L_\beta\prec_{\Sigma_1}L_\alpha\}=\alpha\).[2]
  • An ordinal \(\alpha\) is stable if \(L_\alpha\prec_{\Sigma_1}L\).[2]

The general definition by Kripke is that for ordinals \(\alpha\) and \(\beta\) with \(\beta>\alpha\), \(\alpha\) is \(\beta\)-stable iff \(L_\alpha\prec_{\Sigma_1}L_\beta\).[​3]​​ The enumerating function of stable ordinals is continuous.[3][4]

Suppose \(n\ge 1\). An ordinal \(\alpha\) is \(n\)-stable if \(L_\alpha\prec_{\Sigma_n}L\). For \(\rho>\alpha\), an ordinal \(\alpha\) is \(n\)-\(\rho\)-stable (also called "\((\rho,n)\)-stable"[5]) if \(L_\alpha\prec_{\Sigma_n}L_\rho\)[6].

1-\(\rho\)-stability has the following properties:[7] invalid link[citation needed]

  1. If \(\alpha<\beta<\gamma\) and \(L_\alpha\prec_{\Sigma_1}L_\gamma\), then \(L_\alpha\prec_{\Sigma_1}L_\beta\).
  2. If \(L_\alpha\prec_{\Sigma_1}L_\beta\) and \(L_\beta\prec_{\Sigma_1}L_\gamma\), then \(L_\alpha\prec_{\Sigma_1}L_\gamma\).
  3. If \(\alpha<\beta\) and \(\beta\) is stable, then \(\alpha\) is stable iff \(L_\alpha\prec_{\Sigma_1}L_\beta\).
  4. If a set \(A\) is nonempty and \(\forall\alpha\in A(L_\alpha\prec_{\Sigma_1}L_\beta)\), then \(L_{\sup A}\prec_{\Sigma_1}L_\beta\).

For an ordinal \(\alpha\), \(\alpha\) is nonprojectible iff \(L_\alpha\models\text{KP}\omega+\Sigma_1\text{-Sep}\)[8], and "\(\alpha\) is nonprojectible" implies "\(\alpha\) is recursively Mahlo"[9]. For a limit ordinal \(\alpha\), \(L_\alpha\models\Sigma_n\text{-Sep}+\Sigma_n\text{-Coll}\) iff \(\forall x\in L_\alpha\exists M\in L_\alpha(x\subseteq M\land M\prec_{\Sigma_n}L_\alpha)\).[10]

Properties of stability:

  • (+1)-stable ordinals are exactly \(\Pi_0^1\)-reflecting ordinals.[11]
  • \((^+)\)-stable ordinals are exactly \(\Pi_1^1\)-reflecting ordinals.[12]
  • The least \(\Sigma_1^1\)-reflecting ordinal is greater than the least \(\Pi_1^1\)-reflecting ordinal, but every \((^{++})\)-stable ordinal is \(\Sigma_1^1\)-reflecting.
  • Stable ordinals are exactly \(\Sigma_2^1\)-reflecting ordinals, while the least of them is less than the least \(\Pi_2^1\)-reflecting ordinal.[13]
  • \(\zeta\), the supremum of all eventually writable ordinals, is the least ordinal that is 2-\(\rho\)-stable for some \(\rho\); and \(\Sigma\), the supremum of all accidentally writable ordinals, is the least ordinal \(\rho\) such that \(\zeta\) is 2-\(\rho\)-stable.[14]

Footnotes

  1. Here, \(\Sigma_1\) denotes Levy's hierarchy. (reference 4) On the other hand, Madore's zoo refers to \(\Pi\), \(\Sigma\), and \(\Delta\) as the hierarchy for arithmetic in other parts. If it is actually intended, then the statement on the reflection property of a \((+1)\)-stable ordinal conflicts the definition based on \(\Sigma_1\)-elementary substructure. Therefore it might be a mistake, or simply an abuse of notation.

Sources

  1. Cantor's attic
  2. 2.0 2.1 2.2 2.3 2.4 2.5 2.6 David A. Madore, A zoo of ordinals.
  3. W. Marek and M. Srebrny, Gaps in the Constructible Universe (1973) (p.382)
  4. J. Barwise, Admissible Sets and Structures (p.178)
  5. T. Arai, A sneak preview of proof theory of ordinals (1997) (p.13)
  6. M. Rathjen, The Higher Infinite in Proof Theory (p.19)
  7. Jon Barwise, "Admissible Sets and Structures", page 179
  8. M. Rathjen, The Higher Infinite in Proof Theory (p.19)
  9. J. Barwise, Admissible Sets and Structures (p.188)
  10. M. Rathjen, The Higher Infinite in Proof Theory (p.19)
  11. Richter & Aczel (1973) Inductive Definitions and Reflecting Properties of Admissible Ordinals (p.44)
  12. Richter & Aczel (1973) Inductive Definitions and Reflecting Properties of Admissible Ordinals (p.16)
  13. Wayne Richter, "The Least \(\Sigma^1_2\) and \(\Pi^1_2\) Reflecting Ordinals", ISILC Logic Conference, ISBN 3-540-07534-8, 568--578
  14. Ansten Morch Klev, "Extending Kleene’s O Using Infinite Time Turing Machines"

See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Advertisement