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.