Stable theory

From HandWiki
Short description: Concerned with the notion of stability in model theory

In the mathematical field of model theory, a theory is called stable if it satisfies certain combinatorial restrictions on its complexity. Stable theories are rooted in the proof of Morley's categoricity theorem and were extensively studied as part of Saharon Shelah's classification theory, which showed a dichotomy that either the models of a theory admit a nice classification or the models are too numerous to have any hope of a reasonable classification. A first step of this program was showing that if a theory is not stable then its models are too numerous to classify.

Stable theories were the predominant subject of pure model theory from the 1970s through the 1990s, so their study shaped modern model theory[1] and there is a rich framework and set of tools to analyze them. A major direction in model theory is "neostability theory," which tries to generalize the concepts of stability theory to broader contexts, such as simple and NIP theories.

Motivation and history

A common goal in model theory is to study a first-order theory by analyzing the complexity of the Boolean algebras of (parameter) definable sets in its models. One can equivalently analyze the complexity of the Stone duals of these Boolean algebras, which are type spaces. Stability restricts the complexity of these type spaces by restricting their cardinalities. Since types represent the possible behaviors of elements in a theory's models, restricting the number of types restricts the complexity of these models.[2]

Stability theory has its roots in Michael Morley's 1965 proof of Łoś's conjecture on categorical theories. In this proof, the key notion was that of a totally transcendental theory, defined by restricting the topological complexity of the type spaces. However, Morley showed that (for countable theories) this topological restriction is equivalent to a cardinality restriction, a strong form of stability now called [math]\displaystyle{ \omega }[/math]-stability, and he made significant use of this equivalence. In the course of generalizing Morley's categoricity theorem to uncountable theories, Frederick Rowbottom generalized [math]\displaystyle{ \omega }[/math]-stability by introducing [math]\displaystyle{ \kappa }[/math]-stable theories for some cardinal [math]\displaystyle{ \kappa }[/math], and finally Shelah introduced stable theories.[3]

Stability theory was much further developed in the course of Shelah's classification theory program. The main goal of this program was to show a dichotomy that either the models of a first-order theory can be nicely classified up to isomorphism using a tree of cardinal-invariants (generalizing, for example, the classification of vector spaces over a fixed field by their dimension), or are so complicated that no reasonable classification is possible.[4] Among the concrete results from this classification theory were theorems on the possible spectrum functions of a theory, counting the number of models of cardinality [math]\displaystyle{ \kappa }[/math] as a function of [math]\displaystyle{ \kappa }[/math].[lower-alpha 1] Shelah's approach was to identify a series of "dividing lines" for theories. A dividing line is a property of a theory such that both it and its negation have strong structural consequences; one should imply the models of the theory are chaotic, while the other should yield a positive structure theory. Stability was the first such dividing line in the classification theory program, and since its failure was shown to rule out any reasonable classification, all further work could assume the theory to be stable. Thus much of classification theory was concerned with analyzing stable theories and various subsets of stable theories given by further dividing lines, such as superstable theories.[3]

One of the key features of stable theories developed by Shelah is that they admit a general notion of independence called non-forking independence, generalizing linear independence from vector spaces and algebraic independence from field theory. Although non-forking independence makes sense in arbitrary theories, and remains a key tool beyond stable theories, it has particularly good geometric and combinatorial properties in stable theories. As with linear independence, this allows the definition of independent sets and of local dimensions as the cardinalities of maximal instances of these independent sets, which are well-defined under additional hypotheses. These local dimensions then give rise to the cardinal-invariants classifying models up to isomorphism.[4]

Definition and alternate characterizations

Let T be a complete first-order theory.

For a given infinite cardinal [math]\displaystyle{ \kappa }[/math], T is [math]\displaystyle{ \kappa }[/math]-stable if for every set A of cardinality [math]\displaystyle{ \kappa }[/math] in a model of T, the set S(A) of complete types over A also has cardinality [math]\displaystyle{ \kappa }[/math]. This is the smallest the cardinality of S(A) can be, while it can be as large as [math]\displaystyle{ 2^\kappa }[/math]. For the case [math]\displaystyle{ \kappa = \aleph_0 }[/math], it is common to say T is [math]\displaystyle{ \omega }[/math]-stable rather than [math]\displaystyle{ \aleph_0 }[/math]-stable.[5]

T is stable if it is [math]\displaystyle{ \kappa }[/math]-stable for some infinite cardinal [math]\displaystyle{ \kappa }[/math].[6]

Restrictions on the cardinals [math]\displaystyle{ \kappa }[/math] for which a theory can simultaneously by [math]\displaystyle{ \kappa }[/math]-stable are described by the stability spectrum,[7] which singles out the even tamer subset of superstable theories.

A common alternate definition of stable theories is that they do not have the order property. A theory has the order property if there is a formula [math]\displaystyle{ \phi(\bar x, \bar y) }[/math] and two infinite sequences of tuples [math]\displaystyle{ A= (\bar a_i: i \in \mathbb N) }[/math], [math]\displaystyle{ B= (\bar b_j: j \in \mathbb N) }[/math] in some model M such that [math]\displaystyle{ \phi }[/math] defines an infinite half graph on [math]\displaystyle{ A \times B }[/math], i.e. [math]\displaystyle{ \phi(\bar a_i, \bar b_j) }[/math] is true in M [math]\displaystyle{ \iff i \leq j }[/math].[8] This is equivalent to there being a formula [math]\displaystyle{ \psi(\bar x, \bar y) }[/math] and an infinite sequence of tuples [math]\displaystyle{ A= (\bar a_i: i \in \mathbb N) }[/math] in some model M such that [math]\displaystyle{ \psi }[/math] defines an infinite linear order on A, i.e. [math]\displaystyle{ \psi(\bar a_i, \bar a_j) }[/math] is true in M [math]\displaystyle{ \iff i \leq j }[/math].[9][lower-alpha 2][lower-alpha 3]

There are numerous further characterizations of stability. As with Morley's totally transcendental theories, the cardinality restrictions of stability are equivalent to bounding the topological complexity of type spaces in terms of Cantor-Bendixson rank.[12] Another characterization is via the properties that non-forking independence has in stable theories, such as being symmetric. This characterizes stability in the sense that any theory with an abstract independence relation satisfying certain of these properties must be stable and the independence relation must be non-forking independence.[13]

Any of these definitions, except via an abstract independence relation, can instead be used to define what it means for a single formula to be stable in a given theory T. Then T can be defined to be stable if every formula is stable in T.[14] Localizing results to stable formulas allows these results to be applied to stable formulas in unstable theories, and this localization to single formulas is often useful even in the case of stable theories.[15]

Examples and non-examples

For an unstable theory, consider the theory DLO of dense linear orders without endpoints. Then the atomic order relation has the order property. Alternatively, unrealized 1-types over a set A correspond to cuts (generalized Dedekind cuts, without the requirements that the two sets be non-empty and that the lower set have no greatest element) in the ordering of A,[16] and there exist dense orders of any cardinality [math]\displaystyle{ \kappa }[/math] with [math]\displaystyle{ 2^\kappa }[/math]-many cuts.[17]

Another unstable theory is the theory of the Rado graph, where the atomic edge relation has the order property.[18]

For a stable theory, consider the theory [math]\displaystyle{ ACF_p }[/math] of algebraically closed fields of characteristic p, allowing [math]\displaystyle{ p=0 }[/math]. Then if K is a model of [math]\displaystyle{ ACF_p }[/math], counting types over a set [math]\displaystyle{ A \subset K }[/math] is equivalent to counting types over the field k generated by A in K. There is a (continuous) bijection from the space of n-types over k to the space of prime ideals in the polynomial ring [math]\displaystyle{ k[X_1, \dots, X_n] }[/math]. Since such ideals are finitely generated, there are only [math]\displaystyle{ |k| + \aleph_0 }[/math] many, so [math]\displaystyle{ ACF_p }[/math] is [math]\displaystyle{ \kappa }[/math]-stable for all infinite [math]\displaystyle{ \kappa }[/math].[19]

Some further examples of stable theories are listed below.

  • The theory of differentially closed fields of characteristic p. When [math]\displaystyle{ p=0 }[/math], the theory is [math]\displaystyle{ \omega }[/math]-stable.[22]
  • The theory of any nowhere dense graph class.[23] These include graph classes with bounded expansion, which in turn include planar graphs and any graph class of bounded degree.

Geometric stability theory

Geometric stability theory is concerned with the fine analysis of local geometries in models and how their properties influence global structure. This line of results was later key in various applications of stability theory, for example to Diophantine geometry. It is usually taken to start in the late 1970s with Boris Zilber's analysis of totally categorical theories, eventually showing that they are not finitely axiomatizble. Every model of a totally categorical theory is controlled by (i.e. is prime and minimal over) a strongly minimal set, which carries a matroid structure[lower-alpha 4] determined by (model-theoretic) algebraic closure that gives notions of independence and dimension. In this setting, geometric stability theory then asks the local question of what the possibilities are for the structure of the strongly minimal set, and the local-to-global question of how the strongly minimal set controls the whole model.[24]

The second question is answered by Zilber's Ladder Theorem, showing every model of a totally categorical theory is built up by a finite sequence of something like "definable fiber bundles" over the strongly minimal set.[25] For the first question, Zilber's Trichotomy Conjecture was that the geometry of a strongly minimal set must be either like that of a set with no structure, or the set must essentially carry the structure of a vector space, or the structure of an algebraically closed field, with the first two cases called locally modular.[26] This conjecture illustrates two central themes. First, that (local) modularity serves to divide combinatorial or linear behavior from nonlinear, geometric complexity as in algebraic geometry.[27] Second, that complicated combinatorial geometry necessarily comes from algebraic objects;[28] this is akin to the classical problem of finding a coordinate ring for an abstract projective plane defined by incidences, and further examples are the group configuration theorems showing certain combinatorial dependencies among elements must arise from multiplication in a definable group.[29] By developing analogues of parts of algebraic geometry in strongly minimal sets, such as intersection theory, Zilber proved a weak form of the Trichotomy Conjecture for uncountably categorical theories.[30] Although Ehud Hrushovski developed the Hrushovski construction to disprove the full conjecture, it was later proved with additional hypotheses in the setting of "Zariski geometries".[31]

Notions from Shelah's classification program, such as regular types, forking, and orthogonality, allowed these ideas to be carried to greater generality, especially in superstable theories. Here, sets defined by regular types play the role of strongly minimal sets, with their local geometry determined by forking dependence rather than algebraic dependence. In place of the single strongly minimal set controlling models of a totally categorical theory, there may be many such local geometries defined by regular types, and orthogonality describes when these types have no interaction.[32]

Applications

While stable theories are fundamental in model theory, this section lists applications of stable theories to other areas of mathematics. This list does not aim for completeness, but rather a sense of breadth.

  • Since the theory of differentially closed fields of characteristic 0 is [math]\displaystyle{ \omega }[/math]-stable, there are many applications of stability theory in differential algebra. For example, the existence and uniqueness of the differential closure of such a field (an analogue of the algebraic closure) were proved by Lenore Blum and Shelah respectively, using general results on prime models in [math]\displaystyle{ \omega }[/math]-stable theories.[33]
  • In Diophantine geometry, Ehud Hrushovski used geometric stability theory to prove the Mordell-Lang conjecture for function fields in all characteristics, which generalizes Faltings's theorem about counting rational points on curves and the Manin-Mumford conjecture about counting torsion points on curves.[34] The key point in the proof was using Zilber's Trichotomy in differential fields to show certain arithmetically defined groups are locally modular.[35]
  • In online machine learning, the Littlestone dimension of a concept class is a complexity measure characterizing learnability, analogous to the VC-dimension in PAC learning. Bounding the Littlestone dimension of a concept class is equivalent to a combinatorial characterization of stability involving binary trees.[36] This equivlanece has been used, for example, to prove that online learnability of a concept class is equivalent to differentially private PAC learnability.[37]
  • In functional analysis, Jean-Louis Krivine and Bernard Maurey defined a notion of stability for Banach spaces, equivalent to stating that no quantifier-free formula has the order property (in continuous logic, rather than first-order logic). They then showed that every stable Banach space admits an almost-isometric embedding of ℓp for some [math]\displaystyle{ p \in [1, \infty) }[/math].[38] This is part of a broader interplay between functional analysis and stability in continuous logic; for example, early results of Alexander Grothendieck in functional analysis can be interpreted as equivalent to fundamental results of stability theory.[39]
  • A countable (possibly finite) structure is ultrahomogeneous if every finite partial automorphism extends to an automorphism of the full structure. Gregory Cherlin and Alistair Lachlan provided a general classification theory for stable ultrahomogeneous structures, including all finite ones. In particular, their results show that for any fixed finite relational language, the finite homogeneous structures fall into finitely many infinite families with members parametrized by numerical invariants and finitely many sporadic examples. Furthermore, every sporadic example becomes part of an infinite family in some richer language, and new sporadic examples always appear in suitably richer languages.[40]

Generalizations

For about twenty years after its introduction, stability was the main subject of pure model theory.[43] A central direction of modern pure model theory, sometimes called "neostability" or "classification theory,"[lower-alpha 5]consists of generalizing the concepts and techniques developed for stable theories to broader classes of theories, and this has fed into many of the more recent applications of model theory.[44]

Two notable examples of such broader classes are simple and NIP theories. These are orthogonal generalizations of stable theories, since a theory is both simple and NIP if and only if it is stable.[43] Roughly, NIP theories keep the good combinatorial behavior from stable theories, while simple theories keep the good geometric behavior of non-forking independence.[45] In particular, simple theories can be characterized by non-forking independence being symmetric,[46] while NIP can be characterized by bounding the number of types realized over either finite[47] or infinite[48] sets.

Another direction of generalization is to recapitulate classification theory beyond the setting of complete first-order theories, such as in abstract elementary classes.[49]

See also

Notes

  1. ↑ One such result is Shelah's proof of Morley's conjecture for countable theories, stating that the number of models of cardinality [math]\displaystyle{ \kappa }[/math] is non-decreasing for uncountable [math]\displaystyle{ \kappa }[/math].[4]
  2. ↑ In work on Łoś's conjecture preceding Morley's proof, Andrzej Ehrenfeucht introduced a property slightly stronger than the order property, which Shelah later called property (E). This was another precursor of (uns)stable theories.[10]
  3. ↑ One benefit of the definition of stability via the order property is that it is more clearly set-theoretically absolute.[11]
  4. ↑ The term "pregeometry" is often used instead of "matroid" in this setting.
  5. ↑ The term "classification theory" has two uses. The narrow use described earlier refers to Shelah's program of identifying classifiable theories, and takes place almost entirely within stable theories. The broader use described here refers to the larger program of classifying theories by dividing lines possibly more general than stability.[11]

References

  1. ↑ Baldwin, John (2021). "The dividing line methodology: Model theory motivating set theory". Theoria 87 (2): 1. doi:10.1111/theo.12297. http://homepages.math.uic.edu/~jbaldwin/pub/atheoriabibjan619.pdf. 
  2. ↑ van den Dries, Lou (2005). "Introduction to model-theoretic stability". Introduction. https://faculty.math.illinois.edu/~vddries/stable.pdf. 
  3. ↑ 3.0 3.1 Pillay, Anand (1983). "Preface". An Introduction to Stability Theory. 
  4. ↑ 4.0 4.1 4.2 Baldwin, John (2021). "The dividing line methodology: Model theory motivating set theory". Theoria 87 (2): Section 1.1. doi:10.1111/theo.12297. http://homepages.math.uic.edu/~jbaldwin/pub/atheoriabibjan619.pdf. 
  5. ↑ Marker, David (2006). Model Theory: An Introduction. Definition 4.2.17. 
  6. ↑ Marker, David (2006). Model Theory: An Introduction. Definition 5.3.1. 
  7. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Theorem 8.6.5. 
  8. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Definition 8.2.1. 
  9. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Exercise 8.2.1. 
  10. ↑ Shelah, Saharon (1974). "Categoricity of uncountable theories". https://shelah.logic.at/files/203570/Sh-31.pdf. 
  11. ↑ 11.0 11.1 Hodges, Wilfrid. "First-order Model Theory". Section 5.1. https://plato.stanford.edu/entries/modeltheory-fo/. 
  12. ↑ Casanovas, Enrique. "Stable and simple theories (Lecture Notes)". Proposition 6.6. http://www.ub.edu/modeltheory/documentos/stability.pdf. 
  13. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Theorem 8.5.10. 
  14. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Chapter 8.2. 
  15. ↑ Baldwin, John (2017). Fundamentals of Stability Theory. Chapter 3.1. https://projecteuclid.org/ebooks/perspectives-in-logic/Fundamentals-of-Stability-Theory/toc/pl/1235414194. 
  16. ↑ Marker, David (2006). Model Theory: An Introduction. Example 4.1.12. 
  17. ↑ Marker, David (2006). Model Theory: An Introduction. Lemma 5.2.12. 
  18. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Exercise 8.2.3. 
  19. ↑ Marker, David (2006). Model Theory: An Introduction. Example 4.1.14. 
  20. ↑ Tent, Katrin; Ziegler, Martin (2012). A Course in Model Theory. Example 8.6.6. 
  21. ↑ Sela, Zlil (2013). "Diophantine geometry over groups VIII: Stability". Annals of Mathematics 177 (3): 787–868. doi:10.4007/annals.2013.177.3.1. https://annals.math.princeton.edu/wp-content/uploads/annals-v177-n3-p01-s.pdf. 
  22. ↑ Shelah, Saharon (1973). "Differentially closed fields". Israel Journal of Mathematics 16 (3): 314–328. doi:10.1007/BF02756711. https://shelah.logic.at/files/95979/39.pdf. 
  23. ↑ Adler, Hans; Adler, Isolde (2014). "Interpreting nowhere dense graph classes as a classical notion of model theory". European Journal of Combinatorics 36: 322–330. doi:10.1016/j.ejc.2013.06.048. 
  24. ↑ Pillay, Anand (2001). "Aspects of geometric model theory". https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=04212872c51a082eea4ded5b73cc6567dc8feb5e. 
  25. ↑ Pillay, Anand (1996). Geometric Stability Theory. p. 343. 
  26. ↑ Scanlon, Thomas. "Zilber's Trichotomy Conjecture". https://math.berkeley.edu/~scanlon/papers/LC04/LC04/trichotomy.html. 
  27. ↑ Hrushovski, Ehud (1998). "Geometric model theory". https://eudml.org/doc/224669. 
  28. ↑ Scanlon, Thomas. "Combinatorial geometric stability". https://math.berkeley.edu/~scanlon/papers/LC04/LC04/lec2.html. 
  29. ↑ Ben-Yaacov, Itaï; Tomašić, Ivan; Wagner, Frank (2002). "The Group Configuration in Simple Theories and Its Applications". 8 2. http://math.univ-lyon1.fr/~begnac/articles/bsl.pdf. 
  30. ↑ Scanlon, Thomas. "Zilber's trichotomy theorem". https://math.berkeley.edu/~scanlon/papers/LC04/LC04/trichotomythm.html. 
  31. ↑ Scanlon, Thomas. "Combinatorial geometric stability". https://math.berkeley.edu/~scanlon/papers/LC04/LC04/lec2.html. 
  32. ↑ Pillay, Anand (2001). "Aspects of geometric model theory". https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=04212872c51a082eea4ded5b73cc6567dc8feb5e. 
  33. ↑ Sacks, Gerald (1972). "The differential closure of a differential field". Bulletin of the American Mathematical Society 78 (5): 629–634. doi:10.1090/S0002-9904-1972-12969-0. https://www.ams.org/journals/bull/1972-78-05/S0002-9904-1972-12969-0/S0002-9904-1972-12969-0.pdf. 
  34. ↑ Hrushovski, Ehud (1996). "The Mordell-Lang conjecture for function fields". Journal of the American Mathematical Society 9 (3): 667–690. doi:10.1090/S0894-0347-96-00202-0. https://www.ams.org/journals/jams/1996-9-03/S0894-0347-96-00202-0/S0894-0347-96-00202-0.pdf. 
  35. ↑ Scanlon, Thomas. "Mordell-Lang and variants". https://math.berkeley.edu/~scanlon/papers/LC04/LC04/ml.html. 
  36. ↑ Chase, Hunter; Freitag, James (2019). "Model theory and machine learning". Bulletin of Symbolic Logic 25 (3): 319–332. doi:10.1017/bsl.2018.71. 
  37. ↑ Alon, Noga; Bun, Mark; Livni, Roi; Malliaris, Maryanthe; Moran, Shay (2022). "Private and Online Learnability are Equivalent". Journal of the ACM 69 (4): 1–34. doi:10.1145/3526074. http://www.cs.tau.ac.il/~nogaa/PDFS/JACMjoint1.pdf. 
  38. ↑ Iovino, José (2014). Applications of model theory to functional analysis. Chapters 13,15. https://math.i-learn.unito.it/pluginfile.php/145468/mod_resource/content/2/Iovino.pdf. 
  39. ↑ Ben Yaacov, Itaï (2014). "Model theoretic stability and definability of types, after A. Grothendieck". Bulletin of Symbolic Logic 20 (4). 
  40. ↑ Cherlin, Gregory (2000). "Sporadic homogeneous structures". https://sites.math.rutgers.edu/~cherlin/Paper/2000Sporadic.pdf. 
  41. ↑ Hrushovski, Ehud (2012). "Stable group theory and approximate subgroups". Journal of the American Mathematical Society 25 (1). https://www.ams.org/journals/jams/2012-25-01/S0894-0347-2011-00708-X/S0894-0347-2011-00708-X.pdf. 
  42. ↑ Breuillard, Emmanuel; Green, Ben; Tao, Terence (2012). "The structure of approximate groups". Publications mathématiques de l'IHÉS 116: Acknowledgments. doi:10.1007/s10240-012-0043-9. http://www.numdam.org/item/10.1007/s10240-012-0043-9.pdf. 
  43. ↑ 43.0 43.1 Simon, Pierre (2015). "Introduction". A Guide to NIP Theories. https://www.normalesup.org/~simon/NIP_guide.pdf. 
  44. ↑ Hart, Bradd; Hrushovski, Ehud; Onshuus, Alf; Pillay, Anand; Scanlon, Thomas; Wagner, Frank. "Neostability Theory". https://www.birs.ca/cmo-workshops/2015/15w5145/Report15w5145.pdf. 
  45. ↑ Adler, Hans (2008). "An introduction to theories without the independence property". Archive for Mathematical Logic 5: 21. http://www.logic.univie.ac.at/~adler/docs/nip.pdf. 
  46. ↑ Kim, Byunghan (2001). "Simplicity, and stability in there". The Journal of Symbolic Logic 66 (2): 822–836. doi:10.2307/2695047. 
  47. ↑ Chernikov, Artem; Simon, Pierre (2015). "Externally definable sets and dependent pairs II". Transactions of the American Mathematical Society 367 (7): Fact 3. doi:10.1090/S0002-9947-2015-06210-2. https://www.ams.org/journals/tran/2015-367-07/S0002-9947-2015-06210-2/S0002-9947-2015-06210-2.pdf. 
  48. ↑ Simon, Pierre (2015). A Guide to NIP Theories. Proposition 2.69. https://www.normalesup.org/~simon/NIP_guide.pdf. 
  49. ↑ Shelah, Saharon (2009). Classification Theory for Abstract Elementary Classes Volume 1. https://shelah.logic.at/files/221770/h-v2.pdf. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Stable_theory&oldid=3366050"