# Stability and complete types (in Model Theory)

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 ?

• What makes you think this statement makes sense in a context "far away from Model Theory"? Shelah is only making the definition for elementary classes. In fact, it is possible to make sense of the definition in more general contexts (e.g. metric structures or abstract elementary classes), but my view is that making sense of this definition in some context would actually be evidence that that context is actually not so far away from classical model theory. – Alex Kruckman May 29 '18 at 14:36
• @Alex Kruckman: you should read it as "far away (at first sight)." I know that stability of certain types of graphs has been studied, so I could have asked the question about the point graph or incidence graph of $\mathbb{P}^n(k)$ instead. My question remains the same: what would the statement mean for this type of graph ? For instance, what are the "complete types" over such a graph ? – THC May 29 '18 at 14:49
• Well, the right way to make the definition depends on what properties you are interested in. Also, there are a number of definitions of stability which are equivalent in the first-order setting, but not necessarily in other settings. So for example, when people study stable classes of finite graphs, they usually define stability by a bound on the size of instances of the order property for the edge relation, which has nothing to do (in this context) with counting complete first-order types. In the case of a projective space in the incidence language (points, lines, incidence relation), ... – Alex Kruckman May 29 '18 at 15:01
• ... this is a perfectly good first-order structure, and you use the standard definition of stability from first-order model theory. In fact, $\mathbb{P}^n(k)$ (in the incidence language) is bi-interpretable with $k$ (in the field language), so it will be stable in the first-order model theory sense if and only if $k$ is stable (e.g. if $k$ is finite, algebraically closed, or separably closed). – Alex Kruckman May 29 '18 at 15:02
• Sure, but an abstract projective space in the incidence language is still a first-order structure, and you can take the usual definition of stability. All projective spaces of dimension at least $3$ satisfy Desargues's theorem, so there is at least a division ring around. You can google for "stable division ring" to get a sense for what these can look like. In the case $n = 2$, there are stable non-desarguesian projective planes, constructed using Hrushovski's method. For an exposition, see Section 10.4 of Tent and Ziegler's book A Course in Model Theory. – Alex Kruckman May 29 '18 at 15:27

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.

• @ Alex Kruckman: great answer ! Just to be sure I understand, I have two small questions. (1) Why do you look at scheme-theoretic points ?; as a point-line geometry, the points of $\mathbb{P}^2(K)$ usually are the $K$-rational points; and (2) Where do the automorphisms come in (cf. your paragraph "2. Automorphisms ...") ? And what is $C$ here ? – THC Jun 5 '18 at 14:30
• @THC Good questions. (1) First of all, we're counting with parameters from a model $M = \mathbb{P}^2(K)$ (so $M = C$ from the preceding paragraphs). The $K$-rational points correspond to complete types which are realized in $M$. Such a type includes the formula $(x = p)$, where $p\in M$. But there are lots of other complete types over $M$ of points which are not in $M$ (types which contain the formulas $(x\neq p)$ for all $p\in M$). For a simple example, consider a line $\ell\in M$, and consider a type over $M$ which contains the formula $(x I \ell)$ but also $(x\neq p)$ for all $p\in M$. – Alex Kruckman Jun 5 '18 at 14:58
• Let's say our type is $\mathrm{tp}(a/M)$ for some point $a$ in an elementary extension $N$ of $M$. So $aI\ell$ in $N$, but $a\notin M$. Then $N = \mathbb{P}^2(F)$, where $F$ is an algebraically closed field containing $K$. If we coordinatize $\ell$ in $\mathbb{P}^2(F)$, it becomes a copy of $\mathbb{P}^1(F)$. Its points in $M$ correspond to elements of $K$ (plus $\infty$), while it's points in $N\setminus M$ correspond to elements of $F\setminus K$ (which are transcendental over $K$, since $K$ is algeabraically closed). – Alex Kruckman Jun 5 '18 at 15:02
• Now it turns out that there is a unique type with parameters from $M$ of a transcendental point $\ell$. This can be argued by quantifier elimination, but it's maybe a bit easier to argue using automorphisms (so here I guess I'm answering your second question as well). If $b$ is another transcendental point on the coordinatlized line $\ell$, there is an automorphism over $F$ which fixes $K$ pointwise and moves $a$ to $b$. This automorphism extends to an automorphism $\sigma$ of $N = \mathbb{P}^2(F)$ which fixes $M = \mathbb{P}^2(K)$ pointwise. Thus $\sigma(\ell) = \ell$ but $\sigma(a) = b$. – Alex Kruckman Jun 5 '18 at 15:05
• It follows that $\mathrm{tp}(a/M) = \mathrm{tp}(b/M)$. Ok, so we have a unique type of a point on $\ell$ which is not $K$-rational. It's natural to call this the "generic type" of the line $\ell$ and identify it with the scheme-theoretic generic point of $\ell$. It takes a bit more work to show that scheme-theoretic points which are generic points of plane curves correspond to complete types over $M$, since lines are baked into our language, while curves are not. But thanks to coordinatization and the interpretation of $+$ and $\times$ in the field, we can express polynomial relationships... – Alex Kruckman Jun 5 '18 at 15:08

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.

• @ Alex Kruckman: can you illustrate the definition in your final paragraph ("In other words ...") of complete type over $M$, and Shelah's characterization of stability, on the example of projective planes $\mathbb{P}^2(k)$, with $k$ algebraically closed ? – THC May 30 '18 at 9:54
• @THC: What Alex is describing in his answer is a very general setting to make sense of stability, (Galois) types etc. In order to fit this general setting to your question, you have to decide what notion of strong embedding you want to use. There are many options. Once you have your strong embedding notion, you have to verify that it satisfies the requirements for an Abstract Elementary Class and that is satisfies amalgamation for strong embeddings. Then everything that Alex describes applies. – Ioannis Souldatos May 30 '18 at 11:26
• @THC: To see some examples of AECs and their corresponding strong embeddings see Grossberg's math.cmu.edu/~rami/Rami-NBilgi.pdf and Baldwin's homepages.math.uic.edu/~jbaldwin/pub/AEClec.pdf – Ioannis Souldatos May 30 '18 at 11:28
• @THC Maybe I misinterpreted your question. This answer addresses the question "how can I make sense of the counting types definition of stability outside of a first-order model theory context?" On the other hand, the best notion of stability for a projective space is almost certainly the usual first-order model theory notion of stability. – Alex Kruckman May 30 '18 at 14:39
• @THC Oh, I completely misunderstood where you were coming from, sorry. But now I'm not sure what your background is... e.g. Do you what first-order formulas in the incidence language for projective planes look like? Do you know what a type is? Do you know what quantifier elimination means? – Alex Kruckman May 30 '18 at 15:18