This week, Henry Towsner continued some model-theoretic preliminaries for the reading seminar of the Hrushovski paper, particularly regarding the behaviour of wide types, leading up to the main model-theoretic theorem (Theorem 3.4 of Hrushovski) which in turn implies the various combinatorial applications (such as Corollary 1.2 of Hrushovski). Henry’s notes can be found here.

A key theme here is the phenomenon that any pair of large sets contained inside a definable set of finite measure (such as ) must intersect if they are sufficiently “generic”; the notion of a wide type is designed, in part, to capture this notion of genericity.

** — 1. Global types — **

Throughout this post, we begin with a countable structure of a language , and then consider a universal elementary extension of (i.e. one that obeys the saturation and homogeneity properties as discussed in Notes 1. Later on, will contain the language of groups, and then we will rename as to emphasise this.

Recall from Notes 1 that a *partial type* over a set is a set of formulae (with variables for some fixed ) using as constant symbols, which is consistent and contains the theory of ; if the set of formulae is maximal (i.e. complete), then it is a *type*. One can also think of a type as an ultrafilter over the -definable sets; if is a type and is an -definable set given by some formula , then either lies in (in which case we write ) or lies in (in which case we write ) but not both.

When the set is small (i.e. has cardinality less than that of , which in particular would be true of consisted of union with a finite set, which is a very typical situation), then by saturation one can identify types (or partial types) with the subset of that they cut out. In particular, these sets are non-empty. Adding more formulae to a partial type corresponds to shrinking the set that they cut out, and vice versa.

However, if we have a *global* type – a type defined over the entire model – then one can no longer identify types with the set that they cut out, because these sets are usually empty! However, what we can do is *restrict* to some smaller set of constants to create a type over , defined as the set of all formulae in that only involve the constants in . It is easy to see that this is still a type, and if is small, it cuts out a non-empty set in .

A global type is said to be *-invariant*, or *invariant* for short, if the set of formulae in is invariant under any automorphism of that fixes . In particular, given any -definable set and , we see that if and only if , where is a slice of . (Indeed, this gives an equivalent definition of invariance.)

A trivial example of an invariant global type would be the type of an element (or in ). This cuts out a singleton set . This is in fact the only invariant global type that cuts out anything at all:

Lemma 1Let be a global invariant type. Then is realisable in (i.e. is non-empty) if and only if it is realisable in (and is the type of a single element in ).

*Proof:* Suppose is realisable in by some . Since the formula is definable in , we see that , i.e. cuts out precisely the singleton set . As is invariant, must then be invariant under all -fixing automorphisms of . By homogeneity, this means that there is no element distinct from which is elementarily indistinguishable from over ; in other words, is the set cut out by the type of over .

By saturation, the formula together with the formulae in is not satisfiable, hence not finitely satisfiable. Thus there is a finite set of formulae in that cut out , i.e. is definable over . But as is an elementary extension of , these formulae must also be realisable in , i.e. lies in , and the claim follows.

(Because of this, one should regard the notation carefully; the set that cuts out in the model may in fact be empty, but when we write for some definable , we interpret this syntactically rather than semantically (or equivalently, that holds in all extensions of , and not just in itself.)

On the other hand, invariant global types exist in abundance:

Lemma 2Let be a type over . Then there exists an invariant global type that refines (i.e. it contains all the formulae that does).

*Proof:* We view as a collection of logically consistent formulae. We enlarge this collection to a larger one by adding in the negations of all the formulae definable over that are not realisable in . Observe that this collection remains logically consistent, because any finite set of formulae in were realisable in , hence in (which is an elementary substructure). Hence, by Zorn’s lemma, one can extend to a global type .

We now claim that is invariant. Indeed, let be a sentence over that is contained in , and let be an automorphism that fixes . If is not in , then must be in (by completeness), and hence is in also, and hence must be realisable in (otherwise its negation would be in , and hence in ). But this is absurd since fixes . Thus does lie in , yielding invariance.

A major use of invariant global types for us will be that they can be used to generate sequences of indiscernibles (as defined in previous notes):

Lemma 3Let be a global invariant type of some arity , and construct recursively a sequence by requiring for all . (This is always possible since types are satisfiable once restricted to small sets, by saturation, as discussed earlier). Then are indiscernible over , i.e. the tuples for are elementarily indistinguishable (over ) for any fixed .

*Proof:* This is achieved by an induction on . The case is clear since the all have type over . Now we do the case. It suffices to show that and are elementarily indistinguishable over for all .

By construction, and have the same type over , and so and are elementarily indistinguishable over . So it remains to show that and are elementarily indistinguishable.

Let be an -definable relation that contains ; we need to show that contains also.

Since and have the same type over , by homogeneity there exists an automorphism of fixing that maps to . Since realises , we see that contains the sentence , hence by invariance contains also. Since realises , we conclude , as required.

This concludes the case. The higher case is similar and is left as an exercise.

** — 2. Intersections of wide types — **

Now we assume that the structure is equipped with an -invariant Kiesler measure . This leads to the notion of a *wide type* – a type such that all the -definable sets containing this type have positive measure. Intuitively, elements of a wide type are distributed “generically” in the structure.

In the previous notes we showed that wide types can be “split” amongst indiscernables, as follows:

Lemma 4Let be an element or tuple in , let be a wide type over for some set of constants , and let be a sequence of indiscernibles (over ) that has the same type as (over ). Then for any finite number in this sequence, one can find a type such that has the same type over as does over , for all .

We now use this lemma to show that sets defined by wide types intersect each other in a uniform fashion.

Lemma 5Let be types over , and let , be realisations of such that and are wide. Let , be -definable sets with parameters, contained inside an -definable set of finite measure; then if and only if .

*Proof:* By homogeneity, there is an automorphism fixing that sends to , and maps to another element of . Thus without loss of generality we may assume .

We assume for contradiction that and .

By Lemma 2, we may extend to an invariant global type . Observe that for any , either one has for all , or one has for all (since there is a -definable set between and . Suppose first that the former option holds for some , thus there is a uniform lower bound . We now define a sequence and an indiscernible sequence as follows:

- We initialise and to be a realisation of .
- Now suppose that have been chosen with indiscernible. By Lemma 4, we can find that has the same type over that has over for all . Since , this implies that for all . (Here we use the fact that is a type-definable formula over and .)
- Now, let be a realisation of . With this construction and Lemma 3 we see by induction that is also indiscernible; now we iterate the procedure.

Let be the set , then observe from the above construction that lies in and for all . On the other hand, we claim that is uniformly bounded away from zero, this contradicts the finite measure of by the pigeonhole principle.

To see the uniform lower bound, find an automorphism fixing that maps to . By hypothesis, , thus there exists a rational such that the predicate that models is in , hence in . By invariance, the predicate is in also, hence by construction of , , and the claim follows.

Now we consider the opposite case, in which for all . Then we run the construction slightly differently: for each in turn, set to be a realisation of , then set so that . (This is possible because for any definable set containing , the -definable set contains and thus has positive measure, and so the same is true for ; now use saturation.) Then again we see that the lie in , have intersection of measure zero, and have measure uniformly bounded from below, and we again obtain a contradiction.

Now we place a group structure on , and obtain a variant of the above result:

Proposition 6Let be types in , with wide. Suppose that , are contained in -definable sets such that has finite measure. Let be such that the type of over is wide. Assume also that the Keisler measure is translation-invariant. Then is also wide.

*Proof:* Suppose this is not the case, so that there exists an -definable set containing such that has zero measure. (Initially, one would need two different definable sets containing , but one can simply take their intersection.) On the other hand, as is wide, itself has positive measure. We can place in .

By using the fact that wide types over one set of constants can be refined to wide types over larger sets of constants (Lemma 2 from the previous notes), we see that we can recursively construct a sequence with wide for all . Since , we conclude from Lemma 5 that for all . On the other hand, the all have the same measure as , which is positive. Finally, the are all contained in , which has finite measure; this leads to a contradictoin.

This “generic intersection” property of translates of will be important in later arguments when creating near-groups.

## 4 comments

Comments feed for this article

30 October, 2009 at 6:10 am

ayhangunaydinI think the type p should be invariant in Lemma 1.

[Corrected, thanks – T.]4 November, 2009 at 12:58 pm

Terence TaoLou van den Dries has kindly made his own notes on the Hrushovski paper available at

http://www.math.uiuc.edu/~vddries/approx.dvi

I understand that they may continue to be updated in the future. (I think that in the next post in this series I will collect all the various links to other notes that people have been supplying.)

4 November, 2009 at 2:07 pm

LinkHow do you open .dvi files?

4 November, 2009 at 7:32 pm

Terence TaoA PDF version is also available at

Click to access approx.pdf