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.

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):

- 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 1Let be an infinite cardinal. A complete theory is-stableif, 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 2For 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:

Theorem 3Let be an -stable theory, let be a model of , and let be an infinite subset of . Then there is no definable relation in that is a total ordering on .

*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 4In 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 5Let 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 6If 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 7If 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 8If 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 .

## 10 comments

Comments feed for this article

21 November, 2009 at 12:23 pm

Anush TserunyanHi Prof. Tao,

In the end of the proof of Proposition 8, you say that we have an injection from to , but the correspondence may not be a function since for one there may be two different -s having rank intersections with . That’s why in the notes I wrote it as a partial function going the other way.

Thanks,

Anush

[Corrected, thanks. -T.]24 November, 2009 at 4:39 pm

Alex UsvyatsovDear Terry,

What did you mean by a definable ordering on a countable set (for the random graph)? There is no definable ordering on a definable subset of for any . The order property is exemplified by singletons: there are indiscernible sequences a_i, b_j such that R(a_i,b_j) iff i<j. So there is a definable order on an indiscernible sequence of

pairs: iff . If, on the other hand, you take a set of singletons , then by quantifier elimination the type of a pair is determined by whether or not they are R-related (note that any two singletons have the same type), so there is no ordering… One might ask what happens when one works with parameters, but I don't think that this is any different: given an ordering with parameters on an infinite set of singletons , one may assume that all the elements have the same type over the parameters, so the type of a pair from is still symmetric.Possibly a small suggestion: stability theory can also be done locally (that is, looking at a single formula). Since one basic idea in Udi's paper is that a lot can be done once you have just one stable relation, it might be interesting to develop some of the local theory as well as the global one (global stability theory can be also deduced from the local one, but not e.g. -stability, Morley rank, etc).

26 November, 2009 at 12:54 pm

Terence TaoAh, I see now. The relation you define gives rise to orderings on arbitrarily large sets in the random graph itself, and thus to orderings on infinite sets in other models of the random graph (e.g. a nonstandard random graph), but does not order any definable sets. Thanks!

I personally don’t understand stability well enough yet to comment intelligently on your suggestion, but hopefully it will become clearer what the minimal amount of stability theory tools are needed to get Hrushovski’s results.

27 November, 2009 at 3:41 am

Alex UsvyatsovOh, I understand you question now (I think). You are asking whether the random graph is an unstable

structure, that is, whether there is an infinite subset of the random graph itself which is definably ordered. The short answer is yes, but let me elaborate a bit.First, although in model theory we normally don’t distinguish between a model and its elementary extensions when it comes to properties like stability (just like we often don’t distinguish between a definable order on a subset of the model and a subset of the model to some finite power), these distinctions are sometimes important. There are stable structures with unstable theories (structures in which one can order arbitrarily large finite sets, but no infinite set), and they have certain interesting properties (related to things I have been working on recently, actually). One example is Krivine-Maurey theorem saying that a quantifier-free stable separable Banach space (here stability is of the structure, not the theory; one has to define stability in the right way for this context, but let’s ignore this for a moment) embeds an space almost isometrically.

As for the random graph , you can actually find the ordering on pairs I was talking about in the structure itself. There are several related ways of seeing that this has to be the case. First, since is -saturated, so if you have an instance of the order property in an elementary extension, you can construct an ordering on an infinite subset of itself by saturation. Second, is -categorical; so if you have the order property in an elementary extension, there is such a countable elementary extension, but it is isomorphic to . Since -categoricity implies -saturation, this is in some sense a stronger argument.

But in this case, the straightforward construction that I mentioned simply works: choose in by induction such that

are R-related to (that is, to all for j<i

is

notR-related tois not R-related to , same for the b_i's.

The last clause is somewhat arbitrary, but it ensures that both sequences are indiscernible, so not only do you get a definable ordering on the sequence of pairs, but we have constructed an instance of the order property in itself, no compactness arguments needed.

Still. it is true that there is no order on definable sets or on infinite sets of singletons.

The answer to your question about how much stability is actually needed for Hrushovski’s paper is “virtually none”. But local stability can be an illuminating background discussion, just like -stability that you have been looking at. If you are currently mostly interested in stable group theory (e.g. existence of stabilizers), then -stability is a simpler framework (due to the existence of Morley rank), and possibly a better choice. But if you would also like to see some general model theoretic properties of stable theories (such as definability of types), I personally would recommend the local approach. The very beginning of Pillay’s book “Geometric stability theory” is a good source.

26 November, 2009 at 12:11 am

LeonardHi Prof. Tao,

It’s interesting to note that all the tools which your reading group has discussed so far are sufficient to develop a proof of Morley’s Categoricity Theorem, which states that a complete theory in a countable language is k-categorical for all uncountable cardinals k if and only if it is l-categorical for just one uncountable cardinal l. However, I suppose that this result, though an important one, won’t be of any relevance to your discussion?

26 November, 2009 at 12:55 pm

Terence TaoMorley’s theorem is mentioned in passing in Anush’s notes (to explain why categorical theories are stable), but yes, it does seem to not play a direct role in Hrushovski’s paper, though it is of course in the same general subject area.

2 December, 2009 at 11:18 am

imiroI am a former model-theorist: my advisor was Jerry Keisler, my “grandfather” was Alfred Tarski, whom I knew well while in Berkeley teaching set theory and model theory. I find your investigations between model theory and other parts of mathematics fascinating and to help I would like to bring to your attention my paper on Modeloids (Transactions of AMS, vol. 250, June 1979, pp. 47 – 90); the concepts discussed there are naturally tied to the fields (group theory, combinatorics, topological dynamics, etc.) where you apply model theory.

What follows is a brief synopsis of modeloids balancing brevity and accuracy (brief rather than pedantic):

The group of automorphisms of a structure M = (A R, … ) in a language L provides useful information about M but the set of partial automorphisms (finite functions on A preserving the relations of L) captures the essence of the structure M, the salient model-theoretic properties like homogeneity, being saturated, etc. discussed in your postings. The set F of partial automorphisms of a model M satisfies the following properties:

0. elements of F are one-to-one finite functions on A (from subsets of A to A)

1. all finite identities (including the empty one) are in F

2. F is closed under inverses

3. F is closed under compositions (compositions may be empty)

A modeloid on A is a set F of functions on A satisfying the above properties.

Note that the somewhat arbitrary language L is gone. However, given a modeloid F on A there is a language L and a structure M = (A, R, …) in that language such that F is the set of partial automorphisms of M.

The key operation on modeloids is the derivative defined as the set F’ of functions in F which can be “extended”: ’ iff

and

Clearly, F’ is a modeloid included in F and we can iterate the operation by )’ and taking the intersection at limit ordinals. Eventually we end with (b for basic) such ’ = , the basic modeloid for b.

The paper characterizes basic modeloids in terms of topological dynamics (section 5 of the paper). For countable A, Fb consists exactly of the “partial automorphisms” which can be extended to an automorphism – a back-and-forth argument).

When I wrote the paper it looked like the process of taking successive derivatives was akin to obtaining a Poisson stable point in the qualitative theory of differential equations (see p. 71 of the paper).

The paper is actually written in terms of a “dual” notion, in terms of equivalence relations. Notation seems easier and it is more general since it allows languages without equality.

Modeloid F is represented as an equivalence relation on A* (the set of finite sequences from A) as follows: (a, b in A* are sequences of the same length):

iff for some f in F f(a) = b (the natural extension of f to words in A*)

In this terminology (and a model M = (A, R, …) of L in the back of our mind), the equivalence classes correspond to the minimal subsets definable in the structure using no quantifiers.

The derivative of a modeloid E is then a more precise equivalence relation E’ (also on A*) defined by: aE’b iff

and

(ax is the concatenation of a from A* with the element x of A) This is essentially an Ehrenfeucht game: I choose x (or y) and, to win, you have to find y (or x) to make axEby true. The equivalence classes of E’ are the minimal subsets of M definable in the structure using one quantifier.

As before, the operation can be iterated to obtain the basic modeloid whose derivative is itself. The key model-theoretical properties are contained in the manner of how the basic modeloid for E “fits” into E (see Proposition 4.9 and Proposition 7.1).

To give an example, the type of a k-tuple a from A* is {a/ | n > 0 } (the equivalence classes containing a). A type in general is a descending sequence of equivalence classes where a’s are from (fixed k). Note that because .

Countable saturation means that all types are realized, that is

For each sequence such that we can find satisfying for large enough n’s.

(If you think of as |a – b| < 1/n (i.e. a and b are 1/n close) then this is very much like the completeness of reals).

Other model-theory concepts like homogeneity, stability, ultraproducts, etc. are discussed in section 7 of the paper. Take a look.

2 December, 2009 at 6:34 pm

Miro BendaOne more thing that I would like to add to my (iMiro) comment about modeloids (Trans of AMS, vol. 250, June 1979, pp. 47 – 90): As a specific example of modeloid techniques I used modeloids associated with subgroups of symmetric groups to show that for n > 4 the alternating group is the only non-trivial normal subgroup (see Application 6.13 on p. 75). The proof relies just on equivalences; I label it there as “an exercise in pretending”. Though it is not a “proof without words” it does not invoke Sylow’s Theorem, Galois Theory, or other high power machinery.

4 December, 2009 at 9:56 pm

Reading seminar 6: “Stable group theory and approximate subgroups”, by Ehud Hrushovski « What’s new[...] that any countable set of constants can only generate at most a countable number of types. Last time, we showed that -stability also implied that for any other infinite cardinal , a set of constants [...]

12 September, 2012 at 7:09 pm

Definable subsets over (nonstandard) finite fields, and almost quantifier elimination « What’s new[...] geometry; for instance, the concept of Morley rank and Morley degree in model theory (discussed in this previous blog post) directly generalises the concepts of dimension and degree in algebraic geometry.) Over , the [...]