Misplaced Pages

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 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.

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 ${\displaystyle \omega }$-stability, and he made significant use of this equivalence. In the course of generalizing Morley's categoricity theorem to uncountable theories, Frederick Rowbottom generalized ${\displaystyle \omega }$-stability by introducing ${\displaystyle \kappa }$-stable theories for some cardinal ${\displaystyle \kappa }$, and finally Shelah introduced stable theories.

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. 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 ${\displaystyle \kappa }$ as a function of ${\displaystyle \kappa }$. 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.

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.

Definition and alternate characterizations

Let T be a complete first-order theory.

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

T is stable if it is ${\displaystyle \kappa }$-stable for some infinite cardinal ${\displaystyle \kappa }$.

Restrictions on the cardinals ${\displaystyle \kappa }$ for which a theory can simultaneously by ${\displaystyle \kappa }$-stable are described by the stability spectrum, 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 ${\displaystyle \phi ({\bar {x}},{\bar {y}})}$ and two infinite sequences of tuples ${\displaystyle A=({\bar {a}}_{i}:i\in \mathbb {N} )}$, ${\displaystyle B=({\bar {b}}_{j}:j\in \mathbb {N} )}$ in some model M such that ${\displaystyle \phi }$ defines an infinite half graph on ${\displaystyle A\times B}$, i.e. ${\displaystyle \phi ({\bar {a}}_{i},{\bar {b}}_{j})}$ is true in M ${\displaystyle \iff i\leq j}$. This is equivalent to there being a formula ${\displaystyle \psi ({\bar {x}},{\bar {y}})}$ and an infinite sequence of tuples ${\displaystyle A=({\bar {a}}_{i}:i\in \mathbb {N} )}$ in some model M such that ${\displaystyle \psi }$ defines an infinite linear order on A, i.e. ${\displaystyle \psi ({\bar {a}}_{i},{\bar {a}}_{j})}$ is true in M ${\displaystyle \iff i\leq j}$.

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. 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.

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. 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.

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, and there exist dense orders of any cardinality ${\displaystyle \kappa }$ with ${\displaystyle 2^{\kappa }}$-many cuts.

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

For a stable theory, consider the theory ${\displaystyle ACF_{p}}$ of algebraically closed fields of characteristic p, allowing ${\displaystyle p=0}$. Then if K is a model of ${\displaystyle ACF_{p}}$, counting types over a set ${\displaystyle A\subset K}$ 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 ${\displaystyle k}$. Since such ideals are finitely generated, there are only ${\displaystyle |k|+\aleph _{0}}$ many, so ${\displaystyle ACF_{p}}$ is ${\displaystyle \kappa }$-stable for all infinite ${\displaystyle \kappa }$.

Some further examples of stable theories are listed below.

• The theory of any module over a ring (in particular, any theory of vector spaces or abelian groups).

• The theory of non-abelian free groups.

• The theory of differentially closed fields of characteristic p. When ${\displaystyle p=0}$, the theory is ${\displaystyle \omega }$-stable.

• The theory of any nowhere dense graph class. 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 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.

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. 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. 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. Second, that complicated combinatorial geometry necessarily comes from algebraic objects; 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. 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. 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".

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.

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 ${\displaystyle \omega }$-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 ${\displaystyle \omega }$-stable theories.

• 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. The key point in the proof was using Zilber's Trichotomy in differential fields to show certain arithmetically defined groups are locally modular.

• 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. This equivlanece has been used, for example, to prove that online learnability of a concept class is equivalent to differentially private PAC learnability.

• 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 ℓ for some ${\displaystyle p\in [1,\infty )}$. 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.

• 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.

• In arithmetic combinatorics, Hrushovski proved results on the structure of approximate subgroups, for example implying a strengthened version of Gromov's theorem on groups of polynomial growth. Although this did not directly use stable theories, the key insight was that fundamental results from stable group theory could be generalized and applied in this setting. This directly led to the Breuillard-Green-Tao theorem classifying approximate subgroups.

Generalizations

For about twenty years after its introduction, stability was the main subject of pure model theory. A central direction of modern pure model theory, sometimes called "neostability" or "classification theory,"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.

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. Roughly, NIP theories keep the good combinatorial behavior from stable theories, while simple theories keep the good geometric behavior of non-forking independence. In particular, simple theories can be characterized by non-forking independence being symmetric, while NIP can be characterized by bounding the number of types realized over either finite or infinite sets.

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

See also

• Stability spectrum
• Spectrum of a theory
• Morley's categoricity theorem
• NIP theories

Notes

1. One such result is Shelah's proof of Morley's conjecture for countable theories, stating that the number of models of cardinality ${\displaystyle \kappa }$ is non-decreasing for uncountable ${\displaystyle \kappa }$.
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.
3. One benefit of the definition of stability via the order property is that it is more clearly set-theoretically absolute.
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.

References

1. Baldwin, John (2021). "The dividing line methodology: Model theory motivating set theory" (PDF). Theoria. 87 (2): 1. doi:10.1111/theo.12297. S2CID 211239082.
2. van den Dries, Lou (2005). "Introduction to model-theoretic stability" (PDF). Introduction. Retrieved 9 January 2023.
3. ^ Pillay, Anand (1983). "Preface". An Introduction to Stability Theory.
4. ^ Baldwin, John (2021). "The dividing line methodology: Model theory motivating set theory" (PDF). Theoria. 87 (2). Section 1.1. doi:10.1111/theo.12297. S2CID 211239082.
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" (PDF). Proceedings of the Tarski symposium.
11. ^ Hodges, Wilfrid. "First-order Model Theory". Stanford Encyclopedia of Philosophy. Section 5.1. Retrieved 9 January 2023.
12. Casanovas, Enrique. "Stable and simple theories (Lecture Notes)" (PDF). Proposition 6.6. Retrieved 11 January 2023.
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.
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" (PDF). Annals of Mathematics. 177 (3): 787–868. doi:10.4007/annals.2013.177.3.1. S2CID 119143329.
22. Shelah, Saharon (1973). "Differentially closed fields" (PDF). Israel Journal of Mathematics. 16 (3): 314–328. doi:10.1007/BF02756711. S2CID 119906669.
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". Logic Colloquium ’99.
25. Pillay, Anand (1996). Geometric Stability Theory. p. 343.
26. Scanlon, Thomas. "Zilber's Trichotomy Conjecture". Retrieved 27 January 2023.
27. Hrushovski, Ehud (1998). "Geometric model theory". Proceedings of the International Congress of Mathematicians. Vol. 1.
28. Scanlon, Thomas. "Combinatorial geometric stability". Retrieved 27 January 2023.
29. Ben-Yaacov, Itaï; Tomašić, Ivan; Wagner, Frank (2002). "The Group Configuration in Simple Theories and Its Applications" (PDF). 8. 2.
30. Scanlon, Thomas. "Zilber's trichotomy theorem". Retrieved 27 January 2023.
31. Scanlon, Thomas. "Combinatorial geometric stability". Retrieved 27 January 2023.
32. Pillay, Anand (2001). "Aspects of geometric model theory". Logic Colloquium ’99.
33. Sacks, Gerald (1972). "The differential closure of a differential field" (PDF). Bulletin of the American Mathematical Society. 78 (5): 629–634. doi:10.1090/S0002-9904-1972-12969-0. S2CID 17860378.
34. Hrushovski, Ehud (1996). "The Mordell-Lang conjecture for function fields" (PDF). Journal of the American Mathematical Society. 9 (3): 667–690. doi:10.1090/S0894-0347-96-00202-0.
35. Scanlon, Thomas. "Mordell-Lang and variants". Retrieved 27 January 2023.
36. Chase, Hunter; Freitag, James (2019). "Model theory and machine learning". Bulletin of Symbolic Logic. 25 (3): 319–332. arXiv:1801.06566. doi:10.1017/bsl.2018.71. S2CID 119689419.
37. Alon, Noga; Bun, Mark; Livni, Roi; Malliaris, Maryanthe; Moran, Shay (2022). "Private and Online Learnability are Equivalent" (PDF). Journal of the ACM. 69 (4): 1–34. doi:10.1145/3526074. S2CID 247186721.
38. Iovino, José (2014). Applications of model theory to functional analysis (PDF). Chapters 13,15.
39. Ben Yaacov, Itaï (2014). "Model theoretic stability and definability of types, after A. Grothendieck". Bulletin of Symbolic Logic. 20 (4). arXiv:1306.5852.
40. Cherlin, Gregory (2000). "Sporadic homogeneous structures" (PDF). The Gelfand mathematical seminars, 1996--1999.
41. Hrushovski, Ehud (2012). "Stable group theory and approximate subgroups" (PDF). Journal of the American Mathematical Society. 25 (1).
42. Breuillard, Emmanuel; Green, Ben; Tao, Terence (2012). "The structure of approximate groups" (PDF). Publications mathématiques de l'IHÉS. 116. Acknowledgments. arXiv:1110.5008. doi:10.1007/s10240-012-0043-9. S2CID 254166823.
43. ^ Simon, Pierre (2015). "Introduction". A Guide to NIP Theories (PDF).
44. Hart, Bradd; Hrushovski, Ehud; Onshuus, Alf; Pillay, Anand; Scanlon, Thomas; Wagner, Frank. "Neostability Theory" (PDF).
45. Adler, Hans (2008). "An introduction to theories without the independence property" (PDF). Archive for Mathematical Logic. 5: 21.
46. Kim, Byunghan (2001). "Simplicity, and stability in there". The Journal of Symbolic Logic. 66 (2): 822–836. doi:10.2307/2695047. JSTOR 2695047. S2CID 7033889.
47. Chernikov, Artem; Simon, Pierre (2015). "Externally definable sets and dependent pairs II" (PDF). Transactions of the American Mathematical Society. 367 (7). Fact 3. doi:10.1090/S0002-9947-2015-06210-2. S2CID 53968137.
48. Simon, Pierre (2015). A Guide to NIP Theories (PDF). Proposition 2.69.
49. Shelah, Saharon (2009). Classification Theory for Abstract Elementary Classes Volume 1 (PDF).

External links

• A map of the model-theoretic classification of theories, highlighting stability
• Two book reviews discussing stability and classification theory for non-model theorists: Fundamentals of Stability Theory and Classification Theory
• An overview of (geometric) stability theory for non-model theorists

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Model theory