Intuition behind stability and instability in model theory

I am going to explain some motivation by relating this definition to stability to other definitions, and discussing some examples. For simplicity I am going to assume we are working in a countable language.

An alternate definition of stability, for a complete theory $T$ is as follows.

Definition. $T$ is stable if there is some infinite cardinal $\lambda$ such that $T$ is $\lambda$-stable, i.e., for any $M\models T$, and any $A\subseteq M$, if $|A|\leq\lambda$ then for any $n$, $|S_n^T(A)|\leq\lambda$.

(In the previous definition, $S_n^T(A)$ is the space of complete $n$-types with parameters from $A$. One usually drops $T$ from this notation when $T$ is fixed. Also, in checking stability of $T$, it is enough to restrict to $1$-types by an easy exercise.)

So the slogan is that stable theories have "few types", since in general $|S^T_n(A)|$ is only bounded by $2^{|A|+\aleph_0}$. Since types describe the behavior of elements of models (or rather the "potential" behavior in elementary extensions), then we have the idea that stable theories are nice because the number of possible behaviors is constrained.

Counting types this way is an important part of stability theory and Shelah's work in classifying first-order theories according to the spectrum function $I(T,\kappa)$, which counts the number of non-isomorphic models of $T$ of cardinality $\kappa$. Part of the idea is that in order for this function to be well-behaved, and for their to be hope of classifying the models of a theory, one needs a stability (in a strong way). It is also worth mentioning here that there are strong restrictions on the set of $\lambda$ for which a theory $T$ can be $\lambda$-stable. For example if $T$ is stable in some $\lambda$ then it is stable in unboundedly many $\lambda$. Moreover, if $T$ is $\aleph_0$-stable then it is stable in all infinite $\lambda$. But this is getting off track a little so I won't say more.

To give some intuition for the connection between the two definitions of stability, consider the following example.

Example 1. Let $T$ be the theory a dense linear order without endpoints (this determines a complete theory). We can see in $T$ that there a lot of types. For example just consider $1$-types over $\mathbb{Q}$. For any irrational $\alpha\in\mathbb{Q}$, we have a type $p_{\alpha}$ which says $x<r$ for any rational $r>\alpha$, and $x>r$ for any rational $r<\alpha$. This type is finitely-satisfiable in $\mathbb{Q}$ (hence is a bona fide type, and complete by QE for this theory). It is clear that different irrationals give distinct types, and so we obtain $2^{\aleph_0}$ types over a countable parameter set. Conclusion: DLO is not $\aleph_0$-stable (by the second definition). This argument can be generalized to any $\lambda$ (this is Exercise 4.5.21 in Dave Marker's book Model Theory: An Introduction).

In the previous example, we kill stability and obtain a lot of types by using cuts in orderings. So the amazing result is that, in some sense, this is precisely the way to kill stability, but with respect to a more "local" notion of ordering as described by the definition you've given. Indeed, the following is part of Shelah's Unstable Formula Theorem, which is Theorem 2.2 in Chapter 2 of Classification Theory.

Unstable Formula Theorem (abridged). Let $\phi(\bar{x},\bar{y})$ be a formula. The following are equivalent.

1. $\phi(\bar{x},\bar{y})$ is unstable in every $\lambda\geq\aleph_0$, i.e., for every $\lambda\geq\aleph_0$, there is a subset $A$ (of some model of $T$) such that $|A|\leq\lambda<|S_\phi(A)|$ (where $S_\phi(A)$ denotes the space of $\phi$-types with parameters from $A$).
2. $\phi(\bar{x},\bar{y})$ is unstable in some $\lambda\geq\aleph_0$.
3. $\phi(\bar{x},\bar{y})$ has the order property (i.e., satisfies the condition in your definition).

The proof of this theorem is quite beautiful, and draws from both model theory and combinatorics, going back to a combinatorial result of Erdos and Makkai from this paper. In order to fully establish the equivalence between the two notions of stability for a theory (rather than a formula), one needs to show that if $T$ is not $\lambda$-stable for any $\lambda$ (which means there are a lot of complete types) then this can be detected by a single formula (i.e. there are a lot of $\phi$-types for a fixed $\phi(\bar{x},\bar{y})$). This is Theorem 2.13 in the same chapter of Shelah's book.

Remark (on the word "stable"). Stable theories were first defined by Shelah in the 1969 paper Stable Theories. Much of the motivation in this paper comes from work of Morley on totally transcendental theories, which are a subclass of stable theories (in a countable language, totally transcendental is the same as $\aleph_0$-stable). In this paper, Shelah proves the first "spectrum theorem" for type-counting. In particular he proves that if $T$ is a complete theory (we are still in a countable language) then one of the following holds:

1. For any model $M$ and $A\subseteq M$, $|S_1(A)|\leq |A|+2^{\aleph_0}$.
2. For any model $M$ and $A\subseteq M$, $|S_1(A)|\leq |A|^{\aleph_0}$; and (1) fails.
3. For any infinite $\lambda$, there is a model $M$ and $A\subseteq M$ such that $|A|=\lambda<|S_1(A)|$.

Shelah calls the first two cases "stable", presumably because the the cardinalities of the type spaces are "stable" as functions of the cardinalities of the parameter sets (modulo some cardinal arithmetic). For example, in the first case, we can see that $T$ is $\lambda$-stable according to the above definition whenever $\lambda\geq 2^{\aleph_0}$. In the second case $T$ is $\lambda$-stable whenever $\lambda^{\aleph_0}=\lambda$. This result narrows the "stability spectrum" for a particular theory, and Shelah further refines this in his book.

Example 2 (an $\aleph_0$-stable theory). Let $T$ be the theory of algebraically closed fields of characteristic $0$ (this determines a complete theory in the language of rings). This theory has quantifier elimination in the language of rings (this is known to algebraic geometers as the result of Chevalley saying that the projection of a constructible set is constructible). We can use this to deduce that $T$ is $\lambda$-stable for any infinite $\lambda$. Indeed, suppose $A$ is a subset of some model of $T$. We can assume for simplicity that $A$ is a model (note that $|acl(A)|=|A|+\aleph_0$). By quantifier elimination, a $1$-type over $A$ is determined by polynomial equations and inequations with variables in $A$. So one of two things can happen. Either the $1$-type contains a polynomial equation (and thus specifies an element in $A$) or the $1$-type says that no polynomial equation is satisfied (and thus describes a "transcendental" over $A$). So there are $|A|+1=|A|$ many $1$-types, i.e., $|S_1(A)|=|A|$.

Example 3 (a superstable theory). Let $T$ be the theory of the additive group of integers. This theory does not have quantifier elimination in the language of groups. In order to obtain QE, one needs binary relation symbols $\equiv_n$ specifying congruence modulo $n$ for all $n\geq 2$ (note that each $\equiv_n$ is definable in the language of groups using existential quantifiers). We can use these congruence relations to see that $T$ is not $\aleph_0$-stable. In particular, for any (possibly infinite) set $P$ of primes, there is a $1$-type over $\emptyset$ which contains $x\equiv_n 0$ for all $n\in P$ and $x\not\equiv_n 0$ for all primes $n\not\in P$. So we get $2^{\aleph_0}$ types over $\emptyset$.

On the other hand, $T$ is $\lambda$-stable for any $\lambda\geq 2^{\aleph_0}$. This takes a little more work to write out, but one essentially uses QE to show that a $1$-type over a model $A$ either specifies an element of $A$, or specifies a new element plus divisibility conditions for primes. So we get $|A|+2^{\aleph_0}$ types. In general, a theory that is $\lambda$-stable for sufficiently large $\lambda$ (i.e. case (1) in the Remark above) is called superstable.

In both of the previous examples, a good thought experiment is whether it would be easy to check stability using the order property definition (i.e., show that no formula admits an order). Indeed, in my experience the order property definition is a good way to show that a theory is unstable, but in order to show a theory is stable one usually uses type-counting or more sophisticated methods (e.g., forking). On the other hand, going back to Example 1, while type-counting in dense linear orders wasn't all that hard, it is completely trivial to find a formula with the order property.

What I've said only scratches the surface of stability, and there is much more to say. Probably others will add. Indeed, if this website were called Model Theory MathOverflow, then your question could easily be a community wiki.

If you are interested in homogeneous structures, then you might also be interested in the following (equivalent) formulation, using the notion of a half-graph:

Let $V=\{v_1,v_2,\ldots, v_n\}$ be the vertex set of a graph $G=(V,E)$. We say that $G$ is a half-graph if $v_i\mathrel{E}v_j$ iff $i\leq j$.

(Intuitively, this means just that the graph of $E$ as a binary relation consists of exactly the points above the diagonal, including the diagonal --- although for the following definitions it does not really matter what happens on the diagonal.)

Given a model $M$ and a formula $\varphi(\bar x,\bar y)$, where $\bar x$ has length $n$ and $\bar y$ has length $m$, you can consider the infinite graph $G_{\varphi,M}=(M^{n+m},E_\varphi)$, where for $(\bar a_1,\bar b_1), (\bar a_2,\bar b_2)\in M^{n+m}$ we have a $E_\varphi$-edge between them when $\varphi(\bar a_1,\bar b_2)$ holds.

Using this, we can define stability in the following way.

Fix a theory $T$.

• A formula $\varphi(\bar x,\bar y)$ in $T$ is $k$-stable if for every (if $T$ is complete, then equivalently, some) model $M$ of $T$, the graph $G_{\varphi,M}$ does not contain a half-graph of size $k$.
• A formula is stable if it is $k$-stable for some $k$.
• $T$ is stable if every formula $\varphi(\bar x,\bar y)$ is stable.

For example, if $T$ is the theory of $M$, which is the Fraisse limit of a Fraisse class $\mathcal C$ in a finite language, which happens to be uniformly locally finite (e.g. it is relational), then you have quantifier elimination, which gives the following corollary.

• A quantifier-free formula $\varphi(\bar x,\bar y)$ is $k$-stable if no $G_{\varphi,C}$ (with $C\in \mathcal C$) contains a half-graph of size $k$.
• $T$ is stable iff every quantifier-free formula is $k$-stable.

In other words, stability just means that for each $\varphi$, there is some $k$ such that no graph in the class $(G_{\varphi,C})_{C\in \mathcal C}$ of finite graphs contains a half-graph of size $k$. So stability amounts to having some forbidden graphs. Many other model-theoretic tameness notions can be worded similarly.

Here's a topological way to understand stability of a formula. Depending on your background, you might find it intuitive.

Given a formula $\varphi(\bar x,\bar y)$, a model $M$ and a tuple $\bar b$ in $M$ of the same length as $\bar y$, you can define a formula $f_{\varphi,\bar b}\colon M\to \{0,1\}$ by putting $f_{\varphi,\bar b}(\bar a)=1$ if and only if $\varphi(\bar a,\bar b)$ holds.

Now, let us endow $M^{\lvert x\rvert}$ with the weakest topology which makes all these functions continuous. We may attempt to define stability in the following way (which is not yet complete).

"Definition" (I think this is not equivalent, although I don't have any counterexamples offhand): the formula $\varphi$ is stable if the set $\{f_{\varphi,\bar b}\mid \bar b\in M^{\lvert y\rvert}\}\subseteq C(M^{\lvert x\rvert})$ is relatively weakly compact.

Unfortunately, the topology on $M^{\lvert \bar x\rvert}$ itself may not be so nice (for starters, it will often not be Hausdorff). Instead, we consider the space $S_{\varphi}(M)$ --- in model theory, this is the space of $\varphi$-types over $M$. Topologically, it is the compactification of $M^{\lvert \bar x\rvert}$ induced by the family $(f_{\varphi,\bar b})_{\bar b\in M}$ (i.e. the closure of the image of $M^{\lvert \bar x\rvert}$ under the map $M\to \{0,1\}^{M^{\lvert y\rvert}}$, where $\bar a\mapsto (f_{\varphi,\bar b}(a))_{\bar b\in M^{\lvert y\rvert}}$). Note that the functions $f_{\varphi,\bar b}$ uniquely extend to continuous functions on $S_{\varphi}(M)$ (namely, the extensions are the projections).

Having this, we may define stability in the following way:

The formula $\varphi$ is stable when for every $M\models T$, the set $A_{\varphi,M}:=\{f_{\varphi,\bar b}\mid \bar b\in M^{\lvert y\rvert}\}\subseteq C(S_\varphi(M))$ is relatively weakly compact.