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, -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.
- Henry Towsner’s notes (which most of Notes 2-4 have been based on; updated to remove references to homogeneity, using only countable saturation);
- Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
- Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
- Anand Pillay’s sketch of a simplified proof of Theorem 1.1.
— 1. Stable theories —
Let be a countable language. Recall that if we have a structure for , and a set of constants in , we can define an (-ary) type of over to be a maximal consistent family of formulae for an -tuple , where the formulae are allowed to use as constants. For instance, in the language of algebraically closed fields over some base field (all elements of which are constants in ), if is an algebraic closed field and is empty, the type associated to a “generic” element of an algebraic variety defined over (i.e. elements that obey the defining equations for , but do not obey any other algebraic relations over ) is a type. If one makes non-empty, then one now also needs to consider algebraic relations over , the field formed by adjoining to . Note that in general, a type will not be realised in the structure (unless that structure is so huge as to be saturated over the cardinality of ), but can always be realised in some extension of , by the completeness theorem.
The set of all -ary types of over is denoted . It has a natural topology, the Stone topology, whose basic open (in fact, clopen) sets are given by for any formula defined over . 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 has cardinality for some infinite , then the total number of formulae in is also , so the number of types could conceivably be as large as . But for a special class of theories – the -stable theories – the number is much smaller:
Definition 1 Let be an infinite cardinal. A complete theory is -stable if, for any structure satisfying , and any set of constants in of cardinality at most , the set of -ary types of over is at most for every .
The classic example of a -stable theory (for any infinite ) 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 -ary types in this theory over are in one-to-one correspondence with minimal ideals in , where , where is the base field of given characteristic, with a type consisting of the “generic” points cut out by the ideal . More succinctly, . By Hilbert’s basis theorem, all ideals in are finitely generated, and so the cardinality of types is easily seen to be at most .
When is uncountable, a more general example of a -stable theory is that of a -categorical theory – a theory such that any two models of cardinality are isomorphic. (Details can be found in Anush’s notes.)
The classic example of a theory which is not -stable is the theory of dense linear orderings, i.e. the theory of the rationals with the order relation . Using Dedekind cuts, one can associate a type in 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 -stable (though it is -categorical).
Now we look at alternate characterisations of stability, particularly -stability. If is a model of a theory in a language , define a binary tree in to be a collection of -ary formulas in , where are indexed by finite strings of s and s, each of which are consistent with , and such that for any string and its two children and , the formulae and cut out disjoint subsets of the set cut out by relative to , or more precisely that are mutually inconsistent in , but both imply .
Theorem 2 For a countable language and a complete theory , the following are equivalent:
- (i) No binary tree of formulae exists for any model of .
- (ii) is -stable for every infinite ;
- (iii) is -stable.
Proof: (ii) trivially implies (iii). Now we show that (i) implies (ii), i.e. we take a theory which is not -stable for some infinite and use it to create a binary tree.
By hypothesis, we can find a model and a set of constants of cardinality at most , and an such that the number of -ary types exceeds . We can use this to create a binary tree as follows. Call a formula defined over large if it is contained in more than types (i.e. if has cardinality more than ), and small types; thus in particular any tautology is large. We set the root of the binary tree to be such a large formula. We then remove all the types associated to small formulae from , and still retain more than types. Picking two such distinct types , one can find a formula separating from (since ), which allows one to find two formulae which are inconsistent with each other and imply (namely and ); 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 -stability.
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, -stable theories is that they are unable to definably order infinite sets:
Proof: Suppose this is not the case. Using the compactness theorem, we can thus find a model of with a countably infinite subset for which endows with the order structure of the rationals. But then by Dedekind cuts one can then create an uncountable number of types over , contradicting -stability.
It is easy to generalise -stability in the above theorem to -stability for any infinite , 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 of elements of a structure were order-indiscernible if all of the -tuples with 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 -tuples with 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 -stable theory, every order-indiscernible sequence is indiscernible.
Proof: Let be order-indiscernible in some model . To show indiscernibility, it suffices to show that permutations of 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 and are indistinguishable; the general case is similar.
Suppose this is not the case, thus there is a formula such that holds in but fails. Then holds precisely when , thus orders , 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.)
By the previous remarks, the argument can also be extended to -stable theories for any infinite .
— 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 . Clearly, one would want finite sets to have dimension , 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 if and only if it contains infinitely many disjoint algebraic sets of dimension at least .
One can do the same for any theory, assigning to each definable set in a structure a Morley rank, which is either , an ordinal, or (which we consider to be larger than all the ordinals (!)) by the following rules:
- The empty set has Morley rank ; all other definable sets have Morley rank at least .
- If is an ordinal, then a definable set has Morley rank at least if and only if it contains infinitely many disjoint definable sets of Morley rank at least .
Note that for a limit ordinal , a set will have Morley rank at least iff it has Morley rank at least for all , and a set will have Morley rank if it has Morley rank at least for every ordinal . Using this, one can show by transfinite induction that every definable set has a Morley rank.
The Morley rank of a formula cutting out a definable set in a structure may depend on the choice of structure . However, if we assume that the structure 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 largely disappears. To see this, we first need a preliminary lemma:
Lemma 5 Let be countably saturated, and let be a definable set depending on a parameter . Then the Morley rank of in depends only on the type of .
Proof: Let have the same type (i.e. they are elementarily indistinguishable). We need to show that , have the same Morley rank. Suppose not. If was empty, then 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 has Morley rank but has Morley rank at least , thus contains a countable family of disjoint definable sets of Morley rank at least defined using some constants . Using countable saturation, one can find inductively constants such that has the same type as for every . This creates a countable family of djsoint definable sets of , which by an induction hypothesis on can be assumed to have Morley rank at least , which forces to have Morley rank at least , a contradiction.
Corollary 6 If is countably saturated, and is a formula defined using some constants in , then the Morley rank of in is equal to the Morley rank of in , for any elementary extension of .
Proof: It is easy to see by transfinite induction that the Morley rank in is at least as large as that of (there are more non-empty definable sets). Suppose for contradiction that the Morley rank in is , but the Morley rank in is at least . (The case when cuts out an empty set in or is trivial from elementary equivalence.) Then the set cut out by in contains a countable family of disjoint definable sets of Morley rank at least , for some in . By elementary equivalence and countable saturation, one can inductively find in such that the type of in equals the type of in . Then form a countable family of disjoint definable sets in , which have Morley rank at least by the previous lemma, giving the desired contradiction.
Corollary 7 If are countably saturated elementary extensions of , and is a formula defined using some constants in , then the Morley rank of in is the same as that in .
Proof: Take a common countably saturated elementary extension of both and ; by the previous corollary, the rank in or in is equal to that in .
We can thus define the (structure-independent) Morley rank of any formula in to be the rank of 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 we work in are small elementary submodels of a universal model (i.e. a model which is saturated with respect to all small models).
We know that any set of a given Morley rank 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 has an ordinal Morley rank , then there exists a finite such that cannot be partitioned into more than definable subsets of Morley rank .
Proof: We form a partial binary tree by taking and splitting it (if possible) into disjoint non-empty subsets of Morley rank , 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 into infinitely many disjoint definable sets of Morley rank , a contradiction. Thus this tree is finite, and decomposes into some finite number of rank definable sets which are “irreducible” in the sense that they cannot be partitioned into two subsets of rank .
We now claim that any other partition of into rank definable sets must have . Note that for each there is at most one for which has rank , otherwise would not be irreducible. On the other hand, each has to have at least one for which had rank , for if all the had rank less than then would also. Thus we can assign disjoint non-empty subsets of to each in , which forces .
We thus define the Morley degree of to be the largest for which one can partition into disjoint definable sets of the same rank. Note that all such components necessarily have degree .