After a one-week hiatus, we are resuming our reading seminar of the Hrushovski paper. This week, we are taking a break from the paper proper, and are instead focusing on the subject of stable theories (or more precisely, {\omega}-stable theories), which form an important component of the general model-theoretic machinery that the Hrushovski paper uses. (Actually, Hrushovski’s paper needs to work with more general theories than the stable ones, but apparently many of the tools used to study stable theories will generalise to the theories studied in this paper.)

Roughly speaking, stable theories are those in which there are “few” definable sets; a classic example is the theory of algebraically closed fields (of characteristic zero, say), in which the only definable sets are boolean combinations of algebraic varieties. Because of this paucity of definable sets, it becomes possible to define the notion of the Morley rank of a definable set (analogous to the dimension of an algebraic set), together with the more refined notion of Morley degree of such sets (analogous to the number of top-dimensional irreducible components of an algebraic set). Stable theories can also be characterised by their inability to order infinite collections of elements in a definable fashion.

The material here was presented by Anush Tserunyan; her notes on the subject can be found here. Let me also repeat the previous list of resources on this paper (updated slightly):

— 1. Stable theories —

Let {L} be a countable language. Recall that if we have a structure {M} for {L}, and a set {A} of constants in {M}, we can define an ({n}-ary) type of {M} over {A} to be a maximal consistent family {p} of formulae {\phi(x_1,\ldots,x_n)} for an {n}-tuple {\vec x = (x_1,\ldots,x_n)}, where the formulae are allowed to use {A} as constants. For instance, in the language of algebraically closed fields over some base field {k} (all elements of which are constants in {L}), if {M} is an algebraic closed field and {A} is empty, the type associated to a “generic” element of an algebraic variety {V \subset M^n} defined over {k} (i.e. elements that obey the defining equations for {k}, but do not obey any other algebraic relations over {k}) is a type. If one makes {A} non-empty, then one now also needs to consider algebraic relations over {k(A)}, the field formed by adjoining {A} to {k}. Note that in general, a type will not be realised in the structure {M} (unless that structure is so huge as to be saturated over the cardinality of {A}), but can always be realised in some extension of {M}, by the completeness theorem.

The set of all {n}-ary types of {M} over {A} is denoted {S_n^M(A)}. It has a natural topology, the Stone topology, whose basic open (in fact, clopen) sets are given by {U_\phi := \{ p \in S_n^M(A): \phi \in p \}} for any formula {\phi(x_1,\ldots,x_n)} defined over {A}. This makes the space of types a Stone space (totally disconnected, Hausdorff, compact).

In general, the number of types in the world can be quite large: if {A} has cardinality {\kappa} for some infinite {\kappa}, then the total number of formulae in {L(A)} is also {\kappa}, so the number of types could conceivably be as large as {2^\kappa}. But for a special class of theories – the {\kappa}-stable theories – the number is much smaller:

Definition 1 Let {\kappa} be an infinite cardinal. A complete theory {T} is {\kappa}-stable if, for any structure {M} satisfying {T}, and any set {A} of constants in {M} of cardinality at most {\kappa}, the set of {n}-ary types of {M} over {A} is at most {\kappa} for every {n}.

The classic example of a {\kappa}-stable theory (for any infinite {\kappa}) is the theory of algebraically closed fields with fixed characteristic (it is a classical theorem that this theory is complete, basically thanks to quantifier elimination). By quantifier elimination (or by many applications of the nullstellensatz), one can show that the {n}-ary types in this theory over {A} are in one-to-one correspondence with minimal ideals in {F(x_1,\ldots,x_n)}, where {F = k(A)}, where {k} is the base field of given characteristic, with a type {p} consisting of the “generic” points cut out by the ideal {I := \{ f \in F(x_1,\ldots,x_n): (f(x_1,\ldots,x_n)=0) \in p \}}. More succinctly, {S_n^M(A) \equiv Spec(F(x_1,\ldots,x_n))}. By Hilbert’s basis theorem, all ideals in {F(x_1,\ldots,x_n)} are finitely generated, and so the cardinality of types is easily seen to be at most {\kappa}.

When {\kappa} is uncountable, a more general example of a {\kappa}-stable theory is that of a {\kappa}-categorical theory – a theory such that any two models of cardinality {\kappa} are isomorphic. (Details can be found in Anush’s notes.)

The classic example of a theory which is not {\kappa}-stable is the theory of dense linear orderings, i.e. the theory of the rationals {{\mathbb Q}} with the order relation {<}. Using Dedekind cuts, one can associate a type in {S_1^{\mathbb Q}({\mathbb Q})} to every real number, and so there are uncountably many types here even though the number of constants is countable. Thus this theory is not {\omega}-stable (though it is {\omega}-categorical).

Now we look at alternate characterisations of stability, particularly {\omega}-stability. If {M} is a model of a theory {T} in a language {L}, define a binary tree in {M} to be a collection {\phi_s(x_1,\ldots,x_n)} of {n}-ary formulas in {L(M)}, where {s} are indexed by finite strings of {0}s and {1}s, each of which are consistent with {T}, and such that for any string {s} and its two children {s0} and {s1}, the formulae {\phi_{s0}} and {\phi_{s1}} cut out disjoint subsets of the set cut out by {\phi_s} relative to {T}, or more precisely that {\phi_{s0},\phi_{s1}} are mutually inconsistent in {T}, but both imply {\phi_s}.

Theorem 2 For a countable language {L} and a complete theory {T}, the following are equivalent:

  • (i) No binary tree of formulae exists for any model {M} of {T}.
  • (ii) {T} is {\kappa}-stable for every infinite {\kappa};
  • (iii) {T} is {\omega}-stable.

Proof: (ii) trivially implies (iii). Now we show that (i) implies (ii), i.e. we take a theory which is not {\kappa}-stable for some infinite {\kappa} and use it to create a binary tree.

By hypothesis, we can find a model {M} and a set {A} of constants of cardinality at most {\kappa}, and an {n} such that the number of {n}-ary types exceeds {\kappa}. We can use this to create a binary tree as follows. Call a formula {\phi(x_1,\ldots,x_n)} defined over {A} large if it is contained in more than {\kappa} types (i.e. if {U_\phi} has cardinality more than {\kappa}), and small types; thus in particular any tautology is large. We set the root {\phi_\emptyset} of the binary tree to be such a large formula. We then remove all the types associated to small formulae from {U_{\phi_\emptyset}}, and still retain more than {\kappa} types. Picking two such distinct types {p,q}, one can find a formula {\psi} separating {p} from {q} (since {p \neq q}), which allows one to find two formulae {\phi_1, \phi_2} which are inconsistent with each other and imply {\phi_\emptyset} (namely {\phi \wedge \neg \psi} and {\phi_\emptyset \wedge \neg \psi}); by construction, these formulae are also large. Iterating this procedure gives the binary tree.

Finally, to show (iii) implies (i), we see from taking Dedekind cuts again that an infinite binary tree can be used to define an uncountable number of types (by including all the formulae to the left of a cut, excluding all the ones to the right, and then completing to a complete type), which violates {\omega}-stability. \Box

The property of not having binary trees is also known as being totally transcendental, though it was unclear where this terminology came from (especially given that the theory of algebraically closed fields is the classic example of a totally transcendental theory).

We have seen that order theories tend to be unstable. Indeed, {\omega}-stable theories is that they are unable to definably order infinite sets:

Theorem 3 Let {T} be an {\omega}-stable theory, let {M} be a model of {T}, and let {X} be an infinite subset of {M}. Then there is no definable relation {<} in {L} that is a total ordering on {X}.

Proof: Suppose this is not the case. Using the compactness theorem, we can thus find a model of {M} with a countably infinite subset {X} for which {<} endows {X} with the order structure of the rationals. But then by Dedekind cuts one can then create an uncountable number of types over {X}, contradicting {\omega}-stability. \Box

It is easy to generalise {\omega}-stability in the above theorem to {\kappa}-stability for any infinite {\kappa}, by developing analogues of the rational order structure for other cardinalities; see Anush’s notes.

There was some debate as to whether the theory of the Rado graph admitted any obvious definable total ordering on a countable set, but the discussion was inconclusive.

— 2. Stability and indiscernability —

Recall from previous notes that a sequence {x_1,x_2,\ldots} of elements of a structure {M} were order-indiscernible if all of the {k}-tuples {(x_{i_1},\ldots,x_{i_k})} with {i_1<\ldots<i_k} were elementarily indistinguishable from each other (i.e. every formula obeyed by one tuple, is obeyed by all the other tuples). One can use Ramsey-theoretic methods to generate a plentiful supply of order-indiscernibles.

One would however like a stronger notion of indiscernability, which we will just call indiscernability, in which all {k}-tuples {(x_{i_1},\ldots,x_{i_k})} with {i_1,\ldots,i_k} distinct (but not necessarily ordered) are indistinguishable. In general, order indiscernability does not imply indiscernability. But because stable theories cannot “see” order, one has equivalence in this case:

Theorem 4 In an {\omega}-stable theory, every order-indiscernible sequence is indiscernible.

Proof: Let {x_1,x_2,\ldots} be order-indiscernible in some model {M}. To show indiscernibility, it suffices to show that permutations of {(x_{i_1},\ldots,x_{i_k})} are indistinguishable from each other. As permutations are generated by adjacent transpositions, it suffices to do this for adjacent transpositions. For notational simplicity we will just show that {(x_1,x_2)} and {(x_2,x_1)} are indistinguishable; the general case is similar.

Suppose this is not the case, thus there is a formula {\phi} such that {\phi(x_1,x_2)} holds in {M} but {\phi(x_2,x_1)} fails. Then {\phi(x_i,x_j)} holds precisely when {i < j}, thus {\phi} orders {x_1,x_2,\ldots}, contradicting the previous theorem.

(In the general case, one cannot quite use Theorem 3 directly, but one can modify the proof to achieve a similar result; see Anush’s notes.) \Box

By the previous remarks, the argument can also be extended to {\kappa}-stable theories for any infinite {\kappa}.

— 3. Morley rank and degree —

Suppose one was working in the theory of algebraically closed fields of characteristic zero, and wanted to define the notion of the dimension of an algebraic set {V}. Clearly, one would want finite sets to have dimension {0}, and to be the only sets with this property. As for infinite sets, one could recursively define dimension by enforcing the following statement: an algebraic set has dimension at least {\alpha+1} if and only if it contains infinitely many disjoint algebraic sets of dimension at least {\alpha}.

One can do the same for any theory, assigning to each definable set in a structure {M} a Morley rank, which is either {-1}, an ordinal, or {\infty} (which we consider to be larger than all the ordinals (!)) by the following rules:

  • The empty set has Morley rank {-1}; all other definable sets have Morley rank at least {0}.
  • If {\alpha} is an ordinal, then a definable set has Morley rank at least {\alpha+1} if and only if it contains infinitely many disjoint definable sets of Morley rank at least {\alpha}.

Note that for a limit ordinal {\alpha}, a set will have Morley rank at least {\alpha} iff it has Morley rank at least {\beta} for all {\beta < \alpha}, and a set will have Morley rank {\infty} if it has Morley rank at least {\alpha} for every ordinal {\alpha}. Using this, one can show by transfinite induction that every definable set has a Morley rank.

The Morley rank of a formula {\phi} cutting out a definable set in a structure {M} may depend on the choice of structure {M}. However, if we assume that the structure {M} is countably saturated, i.e. that any finitely satisfiable collection of formulae involving at most countably many constants is fully satisfiable, then the dependence on {M} largely disappears. To see this, we first need a preliminary lemma:

Lemma 5 Let {M} be countably saturated, and let {A_a} be a definable set depending on a parameter {a}. Then the Morley rank of {A_a} in {M} depends only on the type of {a}.

Proof: Let {a, b} have the same type (i.e. they are elementarily indistinguishable). We need to show that {A_a}, {A_b} have the same Morley rank. Suppose not. If {A_a} was empty, then {A_b} would be also by indistinguishability, and the claim is obvious; so suppose that both sets are non-empty. Then, without loss of generality, we may assume that {A_a} has Morley rank {\alpha} but {A_b} has Morley rank at least {\alpha+1}, thus {A_b} contains a countable family of disjoint definable sets {B_{b,c_1}, B_{b,c_2}, \ldots} of Morley rank at least {\alpha} defined using some constants {c_1, c_2, \ldots}. Using countable saturation, one can find inductively constants {d_1,d_2,\ldots} such that {(a,d_1,\ldots,d_m)} has the same type as {(b,c_1,\ldots,c_m)} for every {m}. This creates a countable family of djsoint definable sets {B_{a,d_1},B_{a,d_2},\ldots} of {A_a}, which by an induction hypothesis on {\alpha} can be assumed to have Morley rank at least {\alpha}, which forces {A_a} to have Morley rank at least {\alpha+1}, a contradiction. \Box

Corollary 6 If {M} is countably saturated, and {\phi_a} is a formula defined using some constants {a} in {M}, then the Morley rank of {\phi_a} in {M} is equal to the Morley rank of {\phi_a} in {N}, for any elementary extension {N} of {M}.

Proof: It is easy to see by transfinite induction that the Morley rank in {N} is at least as large as that of {M} (there are more non-empty definable sets). Suppose for contradiction that the Morley rank in {M} is {\alpha}, but the Morley rank in {N} is at least {\alpha+1}. (The case when {\phi_a} cuts out an empty set in {M} or {N} is trivial from elementary equivalence.) Then the set {\phi_a(N)} cut out by {\phi_a} in {N} contains a countable family of disjoint definable sets {\psi_{a,b_1}(N), \psi_{a,b_2}(N), \ldots} of Morley rank at least {\alpha}, for some {b_1, b_2, \ldots} in {N}. By elementary equivalence and countable saturation, one can inductively find {c_1,c_2,\ldots} in {M} such that the type of {(a,c_1,\ldots,c_m)} in {M} equals the type of {(a,b_1,\ldots,b_m)} in {N}. Then {\psi_{a,c_1}(M), \psi_{a,c_2}(M), \ldots} form a countable family of disjoint definable sets in {\phi_a(M)}, which have Morley rank at least {\alpha} by the previous lemma, giving the desired contradiction. \Box

Corollary 7 If {N_0, N_1} are countably saturated elementary extensions of {M}, and {\phi_a} is a formula defined using some constants {a} in {M}, then the Morley rank of {\phi_a} in {N_0} is the same as that in {N_1}.

Proof: Take a common countably saturated elementary extension {N} of both {N_0} and {N_1}; by the previous corollary, the rank in {N_0} or in {N_1} is equal to that in {N}. \Box

We can thus define the (structure-independent) Morley rank of any formula {\phi} in {M} to be the rank of {\phi} in any countably saturated elementary extension.

It is not hard to show that Morley rank obeys the basic properties of a dimension, e.g. the dimension of a union is the larger of the dimensions of the two summands (in particular, Morley rank is monotone with respect to set inclusion), and that the only sets of dimension zero are the finite sets.

To avoid technical issues, let us now assume that all models {M} we work in are small elementary submodels of a universal model {{\Bbb M}} (i.e. a model which is saturated with respect to all small models).

We know that any set of a given Morley rank {\alpha} cannot be partitioned into infinitely many disjoint subsets of the same rank. Using this and König’s lemma, we in fact conclude

Proposition 8 If a definable set {A} has an ordinal Morley rank {\alpha}, then there exists a finite {d} such that {A} cannot be partitioned into more than {d} definable subsets of Morley rank {\alpha}.

Proof: We form a partial binary tree by taking {A} and splitting it (if possible) into disjoint non-empty subsets of Morley rank {\alpha}, then taking these subsets and splitting them further, continuing until no further splitting is possible. If this tree is infinite, then König’s lemma ensures an infinite path, which easily gives a decomposition of {A} into infinitely many disjoint definable sets of Morley rank {\alpha}, a contradiction. Thus this tree is finite, and decomposes {A} into some finite number {B_1,\ldots,B_d} of rank {\alpha} definable sets which are “irreducible” in the sense that they cannot be partitioned into two subsets of rank {\alpha}.

We now claim that any other partition {A = C_1 \cup \ldots \cup C_m} of {A} into rank {\alpha} definable sets must have {m \leq d}. Note that for each {B_i} there is at most one {C_j} for which {B_i \cap C_j} has rank {\alpha}, otherwise {B_i} would not be irreducible. On the other hand, each {C_j} has to have at least one {B_i} for which {B_i \cap C_j} had rank {\alpha}, for if all the {B_i \cap C_j} had rank less than {\alpha} then {C_j} would also. Thus we can assign disjoint non-empty subsets of {\{1,\ldots,d\}} to each {j} in {\{1,\ldots,m\}}, which forces {m \leq d}. \Box

We thus define the Morley degree of {A} to be the largest {d} for which one can partition {A} into disjoint definable sets of the same rank. Note that all such components necessarily have degree {1}.