Stability and complete types (in Model Theory)

Question

I read the following statement in these slides of Saharon Shelah: "$K$ is stable iff for every $M \in K$ there are only "few" complete types over $M$." About the notation: here $K$ consists of all structures $N$ with the same theory of $M$, that is, the same set of first order sentences which are true in $M$.

I am trying to understand this statement in a context far away from Model Theory.

Suppose $M$ is, e.g., a projective space $\mathbb{P}^n(k)$ with $k$ some field; then what would this statement mean exactly ?

Answer 1

My previous answer addressed the question "How can I make sense of the counting types definition of stability outside of a first-order model theory context?"

After discussion in the comments, I realized that you really wanted to know what stability means in the context of an (abstract) projective plane. So I'll try to address that question in this answer.

First some background in model theory, just to make sure if we're on the same page. Let $M$ be an $L$-structure and $C$ a subset of $M$. We write $L(C)$ for the set of all first-order formulas with parameters from $C$. For example, if $L = \{P,L,I\}$ is the language of incidence structures (where $P$ and $L$ are unary relations picking out the points and lines and $I$ is the binary incidence relation), then $\varphi(x_1,x_2): \forall y\, ((L(y) \land I(x_1,y)\land I(x_2,y))\rightarrow \lnot I(c,y))$ is a formula with a single parameter $c\in C$ expressing that no line through $x_1$ and $x_2$ is incident with $c$.

Let $x = (x_1,\dots,x_n)$ be a tuple of variables. A complete type $p(x)$ over $C$ (in variable context $x$) is a maximal set of $L(C)$-formulas with free variables from $x$ which is consistent with $\mathrm{Th}_{L(C)}(M)$, the set of all $L(C)$-sentences true in $M$. Maximality amounts to saying that for every formula $\varphi(x)\in L(C)$, either $\varphi(x)\in p(x)$ or $\lnot \varphi(x)\in p(x)$. We write $S_x(C)$ for the set of all complete types over $C$ in context $x$.

Let $a = (a_1,\dots,a_n)$ be an element of $M$. Then the type of $a$ over $C$ is the set of all formulas with parameters from $C$ satisfied by $a$ in $M$: $$\mathrm{tp}(a/C) = \{\varphi(x)\in L(C)\mid M\models \varphi(a)\}.$$

We could equivalently define $S_x(C) = \{\mathrm{tp}(b/C)\mid b\in N, M\preceq N\}$. Note here that in general we have to pass to an elementary extension of $M$: it may be that not every complete type over $C$ is the type of an element in $M$, but every complete type is realized in some elementary extension.

Now a theory $T$ is stable if there is some infinite cardinal $\kappa$ such that for all models $M\models T$, all sets $C\subseteq M$ with $|C| = \kappa$, and all variable contexts $x$, we have $|S_x(C)| = \kappa$.

In Shelah's slides, he gives a slightly different definition, depending on the following facts:

1. It suffices to check stability when the context is a single variable $x$ instead of a tuple.
2. It suffices to check stability when $C$ is an (elementary) submodel.
3. If $T$ is stable, then actually we have that for all infinite $\kappa$, $|C| = \kappa$ implies $|S_x(C)| = \kappa^{|L|}$, where $|L|$ is the number of formulas in the language (with no parameters). The fact that there are cardinals $\kappa$ such that $\kappa^{|L|} = \kappa$ gives the converse. Usually we're most interested in the case $|L| = \aleph_0$.

In practice, if you want to prove that a theory is stable by counting types, then you need some way to understand all the possible complete types. This can be hard, because first-order formulas can be very complicated in general. There are essentially two ways of doing this:

1. Quantifier elimination. A theory $T$ has quantifier elimination if for every first-order formula $\varphi(x)$, there is a quantifier-free formula $\psi(x)$ such that $T\models \forall x\, \varphi(x)\leftrightarrow \psi(x)$. Since quantifier-free formulas are usually much easier to understand than general formulas (they are just Boolean combinations of the atomic formulas - basic relations and equalities between terms), quantifier elimination can be very helpful for counting types. Some theories admit weaker forms of quantifier elimination, where you can show that every formula is equivalent to a Boolean combination of formulas in some restricted class that are still easy to understand.

2. Automorphisms. If $a,a'\in M$ and $\sigma\colon M\to M$ is an automorphism with $\sigma(c) = c$ for all $c\in C$ and $\sigma(a) = a'$, then automatically $\mathrm{tp}(a/C) = \mathrm{tp}(a'/C)$. So upper bounds on the number of orbits of automorphism groups of models of $T$ gives upper bounds on the number of complete types.

OK, now let's look at the example of projective planes. The easiest example of a stable theory of projective planes is the complete theory $T$ of $\mathbb{P}^2(k)$, where $k$ is an algebraically closed field. One way to see that $T$ is stable is to show that it is bi-interpretable with the complete theory of $k$. Any theory of algebraically closed fields is stable, and stability is preserved under bi-interpretation.

$T$ does not have quantifier elimination, but if you add a binary function $f$ to the language such that $f(p_1,p_2)$ is the unique line through the points $p_1$ and $p_2$, and $f(l_1,l_2)$ is the unique point at the intersection of $l_1$ and $l_2$, then $T$ has quantifier elimination in the expanded language (this fact rests heavily on the fact that the theory of algebraically closed fields has quantifier elimination).

Let's think about the counting types criterion. Let $M\models T$ (then $M = \mathbb{P}^2(K)$ where $K$ is algebraically closed of the same characteristic as $k$). Suppose $|M| = \kappa$. How big is $S_x(M)$ (where $x$ is a single variable)?

A type over $M$ could be the type of a point or a line. It suffices to count the types of points, by duality. It turns out that if we coordinatize $M = \mathbb{P}^2(K)$, the type of a point over $M$ is completely determined by the algebraic relationships between the coordinates which are definable over $K$. In short, the types are exactly the scheme-theoretic points of $\mathbb{P}^2(K)$.

The points of dimension $0$ are the types of points in $M$ (there are $\kappa$-many of these). The points of dimension $1$ are the generic types of curves in the projective plane defined over $K$ (there are $\kappa$-many of these, since each can be associated with a homogeneous polynomial over $K$). And there is a unique point of dimension $2$, the generic type of the plane. Altogether, there are only $\kappa$-many types, so $T$ is stable (in fact, it is $\omega$-stable, meaning that $|M| = \kappa$ implies $|S_x(M)| = \kappa$ for all infinite cardinals $\kappa$).

When the field is not algebraically closed, we do not get such a nice description of types thanks to the loss of quantifier elimination in the field (though understanding types relative to the theory of $\mathbb{P}^2(k)$ can still be reduced to understanding types relative to the theory of $k$).

The situation is even worse for non-Desarguesian projective planes, which are not coordinatized by fields or even division rings. As I alluded to in the comments, however, Hrushovski constructions can be used to produce non-Desarguesian projective planes with stable theories. These structures are extremely homogeneous, which allows stability to be checked using the automorphism criterion I described above.

Answer 2

Here is one way to make sense of the notion of complete type, outside the context of first-order model theory. It is inspired by the notion of Galois type in abstract elementary classes.

Let's say $M$ is a mathematical object of some kind that you're interested in, and let's assume that it is a set with extra structure of some kind. Let $A\subseteq M$ and $b,c\in M$. Then we can make the following definition: $b$ and $c$ have the same complete type over $A$ if and only if there is an automorphism $\sigma$ of $M$ such that $\sigma(a) = a$ for all $a\in A$ and $\sigma(b) = c$. This captures the idea that $b$ and $c$ relate to $A$ in exactly the same way (inside $M$). According to this definition, the set of complete types over $A$ (in $M$) is the set of orbits of the group of automorphisms of $M$ fixing $A$.

Now in the first-order setting, this definition agrees with the usual definition if $M$ is saturated. If $M$ is just any old model, then 1. it might not contain elements realizing every complete type over $A$, and 2. $M$ might not be homogeneous enough to have automorphisms linking any two elements with the same complete type over $A$.

So in a more general setting, you might also only want to compute "complete types" in analogues of saturated structures, and there's a question of what this means (the usual definition of saturation references complete types, defined as sets of formulas!). A natural choice would be to replace "saturated" by "universal-homogeneous", which is really what you need to make complete types agree with automorphism orbits in the first-order setting.

$M$ is universal universal-homogeneous for a class $K$ if every small structure in $K$ embeds in $M$, and if $f$ and $g$ are two embeddings of the small structure $N$ in $M$, then there is an automorphism $\sigma$ of $M$ such that $\sigma\circ f = g$.

OK, to make sense of that definition, you have to make sense of what "small" means (the usual approach in model theory is to fix some big cardinal $\kappa$, and take small to mean size $<\kappa$). And also you have to decide what counts as an embedding - you might want something stronger than the usual notion of embedding, to preserve properties you care about (e.g. taking elementary embeddings in the first-order context). Thinking about reasonable properties to assume about strong embeddings leads to the definition of abstract elementary classes.

Unfortunately, universal-homogeneous structures only exist if your class $K$ has the amalgamation property for strong embeddings. In the absence of the amalgamation property, here's a fix for the definition of complete type over a structure in $K$:

Let's say $M$ embeds (strongly) in $N_1$ and $N_2$ (and let's identify $M$ with its image in each of these structures), and $a_1\in N_1$ and $a_2\in N_2$. We say that $a_1$ and $a_2$ have the same complete type (Galois type) over $M$ if there are embeddings $f_1\colon N_1\to N_3$ and $f_2\colon N_2\to N_3$ such that $f_1(m) = f_2(m)$ for all $m\in M$, and $f_1(a_1) = f_2(a_2)$.

In other words, a complete type over $M$ is a class of elements in structures extending $M$ which can be made equal in further extensions. In the case when $N_1 = N_2$, this weakens the assumption that $a_1$ and $a_2$ are conjugate by an automorphism.