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 {X \cdot X^{-1}}) 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 {M} of a language {L}, and then consider a universal elementary extension {{\Bbb U}} of {M} (i.e. one that obeys the saturation and homogeneity properties as discussed in Notes 1. Later on, {L} will contain the language of groups, and then we will rename {{\Bbb U}} as {G} to emphasise this.

Recall from Notes 1 that a partial type over a set {A} is a set of formulae (with {n} variables for some fixed {n}) using {A} as constant symbols, which is consistent and contains the theory of {M}; 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 {A}-definable sets; if {p} is a type and {B} is an {A}-definable set given by some formula {\phi}, then either {\phi} lies in {p} (in which case we write {p \subset B}) or {\neg \phi} lies in {p} (in which case we write {p \subset \overline{B}}) but not both.

When the set {A} is small (i.e. has cardinality less than that of {{\Bbb U}}, which in particular would be true of {A} consisted of {M} union with a finite set, which is a very typical situation), then by saturation one can identify types (or partial types) with the subset {p({\Bbb U})} of {{\Bbb U}^n} 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 {p} – a type defined over the entire model {{\Bbb U}} – then one can no longer identify types with the set {p({\Bbb U})} that they cut out, because these sets are usually empty! However, what we can do is restrict {p} to some smaller set {A} of constants to create a type {p\downharpoonright_A} over {A}, defined as the set of all formulae in {p} that only involve the constants in {A}. It is easy to see that this is still a type, and if {A} is small, it cuts out a non-empty set in {{\Bbb U}^n}.

A global type {p} is said to be {M}-invariant, or invariant for short, if the set of formulae in {p} is invariant under any automorphism {\sigma} of {{\Bbb U}} that fixes {M}. In particular, given any {M}-definable set {A \subset {\Bbb U}^n \times {\Bbb U}^m} and {b \in {\Bbb U}^m}, we see that {p \subset A_b} if and only if {p \subset A_{\sigma(b)}}, where {A_b := \{ a \in {\Bbb U}^n: (a,b) \in A \}} is a slice of {A}. (Indeed, this gives an equivalent definition of invariance.)

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

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

Proof: Suppose {p} is realisable in {{\Bbb U}} by some {a \in p({\Bbb U})}. Since the formula {x=a} is definable in {{\Bbb U}}, we see that {p \subset \{ x: x = a \}}, i.e. {p} cuts out precisely the singleton set {\{a\}}. As {p} is invariant, {\{a\}} must then be invariant under all {M}-fixing automorphisms of {{\Bbb U}}. By homogeneity, this means that there is no element distinct from {a} which is elementarily indistinguishable from {a} over {M}; in other words, {\{a\}} is the set cut out by the type {tp(a/M)} of {a} over {M}.

By saturation, the formula {x \neq a} together with the formulae in {tp(a/M)} is not satisfiable, hence not finitely satisfiable. Thus there is a finite set of formulae in {tp(a/M)} that cut out {\{a\}}, i.e. {\{a\}} is definable over {M}. But as {{\Bbb U}} is an elementary extension of {M}, these formulae must also be realisable in {M}, i.e. {a} lies in {M}, and the claim follows. \Box

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

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

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

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

We now claim that {q} is invariant. Indeed, let {\phi} be a sentence over {{\Bbb U}} that is contained in {q}, and let {\sigma} be an automorphism that fixes {M}. If {\sigma(\phi)} is not in {q}, then {\neg \sigma(\phi)} must be in {q} (by completeness), and hence {\phi \wedge \neg \sigma(\phi)} is in {q} also, and hence must be realisable in {M} (otherwise its negation would be in {p'}, and hence in {q}). But this is absurd since {\sigma} fixes {M}. Thus {\sigma(\phi)} does lie in {q}, 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 3 Let {p} be a global invariant type of some arity {d}, and construct recursively a sequence {b_1, b_2, \ldots \in {\Bbb U}^d} by requiring {b_n \in p\downharpoonright_{M \cup \{b_1,\ldots,b_{n-1}\}}({\Bbb U})} for all {n=1,2,\ldots}. (This is always possible since types are satisfiable once restricted to small sets, by saturation, as discussed earlier). Then {b_1,b_2,\ldots} are indiscernible over {M}, i.e. the tuples {(b_{i_1},\ldots,b_{i_k})} for {i_1 < \ldots < i_k} are elementarily indistinguishable (over {M}) for any fixed {k}.

Proof: This is achieved by an induction on {k}. The {k=1} case is clear since the {b_n} all have type {p\downharpoonright_M} over {M}. Now we do the {k=2} case. It suffices to show that {(b_1,b_2)} and {(b_i,b_j)} are elementarily indistinguishable over {M} for all {i < j}.

By construction, {b_2} and {b_j} have the same type over {M \cup \{b_1\}}, and so {(b_1,b_2)} and {(b_1,b_j)} are elementarily indistinguishable over {M}. So it remains to show that {(b_1,b_j)} and {(b_i,b_j)} are elementarily indistinguishable.

Let {A} be an {M}-definable relation that contains {(b_1,b_j)}; we need to show that {A} contains {(b_i,b_j)} also.

Since {b_1} and {b_i} have the same type over {M}, by homogeneity there exists an automorphism {\sigma} of {{\Bbb U}} fixing {M} that maps {b_1} to {b_i}. Since {b_j} realises {p\downharpoonright_{M \cup \{b_1\}}}, we see that {p} contains the sentence {(b_1,x) \in A}, hence by invariance {p} contains {(b_i,x) \in A} also. Since {b_j} realises {p\downharpoonright_{M \cup \{b_i\}}}, we conclude {(b_i,b_j) \in A}, as required.

This concludes the {k=2} case. The higher {k} case is similar and is left as an exercise. \Box

— 2. Intersections of wide types —

Now we assume that the structure {{\Bbb U}} is equipped with an {M}-invariant Kiesler measure {\mu}. This leads to the notion of a wide type – a type such that all the {{\Bbb U}}-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 4 Let {b} be an element or tuple in {{\Bbb U}}, let {a} be a wide type over {M \cup \{b\}} for some set of constants {M}, and let {b_1,b_2,\ldots} be a sequence of indiscernibles (over {M}) that has the same type as {b} (over {M}). Then for any finite number {b_1,\ldots,b_n} in this sequence, one can find a type {a'} such that {a'} has the same type over {b_i} as {a} does over {b}, for all {1 \leq i \leq n}.

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

Lemma 5 Let {p,q} be types over {M}, and let {a,a' \in p({\Bbb U})}, {b,b' \in q({\Bbb U})} be realisations of {a,b} such that {tp(a/M \cup \{b\})} and {tp(a'/M \cup \{b'\})} are wide. Let {A_x}, {B_y} be {M}-definable sets with parameters, contained inside an {M}-definable set {X} of finite measure; then {\mu(A_a \cap B_b) > 0} if and only if {\mu(A_{a'} \cap B_{b'}) > 0}.

Proof: By homogeneity, there is an automorphism fixing {M} that sends {b} to {b'}, and maps {a} to another element of {p({\Bbb U})}. Thus without loss of generality we may assume {b=b'}.

We assume for contradiction that {\mu(A_a \cap B_b) > \delta > 0} and {\mu(A_{a'} \cap B_{b'}) = 0}.

By Lemma 2, we may extend {q} to an invariant global type {q'}. Observe that for any {\epsilon > 0}, either one has {\mu(A_a \cap B_x) \geq \epsilon} for all {x \in q'\downharpoonright_{M \cup \{a\}}}, or one has {\mu(A_a \cap B_x) \leq \epsilon} for all {x \in q'\downharpoonright_{M \cup \{a\}}} (since there is a {M \cup \{a\}}-definable set between {\{ x: \mu(A_a \cap B_x) \geq \epsilon \}} and {\{ x: \mu(A_a \cap B_x) > \epsilon \}}. Suppose first that the former option holds for some {\epsilon}, thus there is a uniform lower bound {\mu(A_a \cap B_x) > \epsilon}. We now define a sequence {a_1,a_2,\ldots \in p({\Bbb U})} and an indiscernible sequence {b_1,b_2,\ldots \in q({\Bbb U})} as follows:

  • We initialise {a_1=a} and {b_1} to be a realisation of {q'\downharpoonright_{M \cup \{a_1\}}}.
  • Now suppose that {a_1,\ldots,a_n,b_1,\ldots,b_n} have been chosen with {b_1,\ldots,b_n} indiscernible. By Lemma 4, we can find {a_{n+1} \in p({\Bbb U})} that has the same type over {b_i} that {a'} has over {b'} for all {1 \leq i \leq n}. Since {\mu(A_{a'} \cap B_{b'}) = 0}, this implies that {\mu( A_{a_{n+1}} \cap B_{b_i} ) = 0} for all {1 \leq i \leq n}. (Here we use the fact that {\mu( A_x \cap B_b )=0} is a type-definable formula over {M} and {b}.)
  • Now, let {b_{n+1}} be a realisation of {q'\downharpoonright_{M \cup \{a_1,\ldots,a_{n+1},b_1,\ldots,b_n\}}}. With this construction and Lemma 3 we see by induction that {b_1,\ldots,b_{n+1}} is also indiscernible; now we iterate the procedure.

Let {C_i} be the set {C_i := A_{a_i} \cap B_{b_i}}, then observe from the above construction that {C_i} lies in {X} and {\mu(C_i \cap C_j) = 0} for all {i < j}. On the other hand, we claim that {\mu(C_i)} is uniformly bounded away from zero, this contradicts the finite measure of {\mu(X)} by the pigeonhole principle.

To see the uniform lower bound, find an automorphism {\sigma_i} fixing {M} that maps {a_1} to {a_i}. By hypothesis, {\mu(A_{a_1} \cap B_{b_1}) > 0}, thus there exists a rational {r > 0} such that the predicate that models {\mu(A_{a_1} \cap B_x) > r} is in {\tilde q}, hence in {q'}. By invariance, the predicate {\mu(A_{a_i} \cap B_x) > r} is in {q'} also, hence by construction of {b_i}, {\mu(A_{a_i} \cap B_{b_i}) > r}, and the claim follows.

Now we consider the opposite case, in which {\mu(A_a \cap B_x) = 0} for all {x \in q'\downharpoonright_{M \cup \{a\}}}. Then we run the construction slightly differently: for each {n} in turn, set {b_n} to be a realisation of {q'\downharpoonright_{M \cup \{a_1,\ldots,a_{n-1},b_1,\ldots,b_{n-1}}}, then set {a_n \in p({\Bbb U})} so that {\mu(A_{a_n} \cap B_{b_n}) > \delta}. (This is possible because for any definable set {C} containing {p}, the {\bigwedge}-definable set {\{ x \in C: \mu(A_x \cap B_b) \geq \delta \}} contains {p} and thus has positive measure, and so the same is true for {b_n}; now use saturation.) Then again we see that the {C_i} lie in {X}, have intersection of measure zero, and have measure uniformly bounded from below, and we again obtain a contradiction. \Box

Now we place a group structure on {{\Bbb U}}, and obtain a variant of the above result:

Proposition 6 Let {p, q} be types in {M}, with {p} wide. Suppose that {p}, {q} are contained in {M}-definable sets {X, X'} such that {XX'} has finite measure. Let {a,b \in q} be such that the type of {a} over {M \cup \{b\}} is wide. Assume also that the Keisler measure is translation-invariant. Then {pa \cap pb} is also wide.

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

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 {a_1, a_2, \ldots \in q({\Bbb U})} with {tp(a_n/M \cup \{a_1,\ldots,a_{n-1}\})} wide for all {n}. Since {\mu(Aa \cap Ab) = 0}, we conclude from Lemma 5 that {\mu(A a_n \cap A a_i)=0} for all {1 \leq i < n}. On the other hand, the {\mu(Aa_i)} all have the same measure as {\mu(A)}, which is positive. Finally, the {Aa_i} are all contained in {XX'}, which has finite measure; this leads to a contradictoin. \Box

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