At UCLA we just concluded our third seminar in our reading of “Stable group theory and approximate subgroups” by Ehud Hrushovski. In this seminar, Isaac Goldbring made some more general remarks about universal saturated models (extending the discussion from the previous seminar), and then Henry Towsner gave some preliminaries on Kiesler measures, in preparation for connecting the main model-theoretic theorem (Theorem 3.4 of Hrushovski) to one of the combinatorial applications (Corollary 1.2 of Hrushovski).
As with the previous post, commentary on any topic related to Hrushovski’s paper is welcome, even if it is not directly related to what is under discussion by the UCLA group. Also, we have a number of questions below which perhaps some of the readers here may be able to help answer.
Note: the notes here are quite rough; corrections are very welcome. Henry’s notes on his part of the seminar can be found here.
(Thanks to Issac Goldbring for comments.)
— 1. More remarks on universal models —
Recall from the previous seminar that if we have any structure of a language (e.g. could be a group, and the language of groups), then we can (assuming some set-theoretic axioms, such as the existence of inaccessible cardinals) obtain an elementary extension of , enjoying the following properties:
- (i) (Saturation) If has strictly smaller cardinality than , then every partial type over is realisable in ; and
- (ii) (Homogeneity) If is as above and are elementarily indistinguishable over , then there is an automorphism of that maps to .
Another way of phrasing saturation: if one has a “small” family of formulae (where “small” means “having cardinality less than that of “) which is finitely realisable in (i.e. for any finite collection of these formulae, one can find obeying these formulae), then it is realisable (one can find obeying all of the formulae). Equivaqlently the topology on generated by the definable sets (which form a clopen base) is compact.
Remark 1 has the following “universal” property: any small model of the theory of (i.e. any structure elementarily equivalent to ) can be embedded into . Indeed, if one throws in all the elements of as constants, the model can be described as a partial type over the small set , and one simply applies saturation to obtain the embedding.
(A side remark: in Hrushovski’s paper, it is not completely clear whether one is working with the universal model (in which saturation holds over all small sets ) or merely a countably saturated one. If it is the latter, then the above remark does not quite hold, but it seems that one can get around this by replacing “small model” with “small elementary substructure of ” throughout the paper. But this seems to not make a significant difference to the substance of the paper.)
Usually we fix a universal structure , and abbreviate as . (In the combinatorial applications, will be a group, and we will thus call it .)
Remark 2 Universal models have the following useful cardinality gap property: if is a definable set, then either is finite, or (i.e. is large); there are no definable sets of intermediate cardinality. Proof: let be a defining formula for . If is infinite, then the formula together with the formulae for every are finitely realisable, hence realisable by saturation, but this is absurd. Note that this argument in fact shows that any -definable set (i.e. a partial type) is either finite or large. For -definable sets over some infinite set of constants , it was claimed that such sets either have cardinality less than or equal to , or are large, but I didn’t check this.
(Question: if one only assumes countable saturation (which may be the case in Hrushovski’s paper), then one has a smaller cardinality gap: definable sets can be finite or uncountable. It wasn’t clear to us whether the rest of the paper would work if one just had this gap.)
Now we obtain an analogous cardinality gap for equivalence relations.
Lemma 1 Suppose the language is at most countable. Let be a -definable equivalence relation on (one could also consider equivalence relations on ). Then either the cardinality of the classes is at most (the cardinality of the continuum), or is .
Proof: Let be one of the defining relations of the equivalence relation , which we can assume to be symmetric. By the greedy algorithm, we see that one of the following two statements must be true:
- There exists finitely many such that for every , is true for at least one .
- There exists a countable sequence such that fails for all .
Suppose the latter possibility holds. Then by transfinite induction (using the least ordinal with cardinality ) and saturation, we can obtain a family of cardinality such that fails for all . This implies that has equivalence classes, and we are done. Thus the only case remaining is if every defining relation enjoys the first property. But then we see that the equivalence class that an element belongs to is determined by the precise set of obeying for each , and this implies that the number of classes is at most .
We remark that is best possible. Indeed, consider the integers in the language of groups, and take a universal extension of these integers. Consider the relation defined by cosets of the group (i.e. if and agree modulo for every (standard) natural number ). Then this is a -definable relation, but the set of equivalence classes is equivalent to the profinite integers , which have the cardinality of the continuum.
Equivalence relations whose set of classes have cardinality at most are known as bounded equivalence relations. (It may be that one does not actually need the above dichotomy to establish the results in Hrushovski’s paper, and just take the above statement as the definition of a bounded equivalence relation.)
Observe that the proof of the above lemma shows that if a bounded equivalence relation is definable rather than merely -definable, then the number of classes is finite. Thus bounded can be viewed as a generalisation of “finite”.
The boundedness of a certain equivalence relation (created by a certain stabiliser group) is essential in ensuring that we can define a certain locally compact “logic topology” on the quotient space, which is apparently what allows the Gleason-Yamabe theory of topological groups to kick in; presumably we will see more of this in later seminars. (This idea also appears in previous work, such as this paper by Hrushovski, Peterzil, and Pillay.)
— 2. Keisler measures —
To obtain combinatorial results, Hrushovski applies the contradiction and compactness method: assume that a combinatorial result fails, obtain a sequence of counterexamples to that result, and extract some sort of limiting object to which an infinitary theory (in this case, stability theory) can be applied. In this section we discuss what happens to the combinatorial concept of (normalised) cardinality along such a limit; what one gets at the end is an object known as a Kiesler measure.
Suppose we have a finite set in a group . Then given any other set in , we can define a normalised counting measure of by the formula (this measure could be infinite if is infinite). More generally, given , one can define . We will often omit the superscript and use for all the measures on simultaneously. Thus for instance one has , and if and .
Now suppose one has a sequence of groups, each with a finite set . Then we have a sequence of normalised counting measures on (and on powers ). We can then take an ultralimit of all of these objects, obtaining a group (the ultrapower of the ), a subset of (the ultrapower of the ), and a “measure” , which assigns to every subset of a non-standard real number (or ) . Thus for instance . In practice we will be working inside (or small powers of , such as ), which by hypothesis will have bounded measure, so the case will not be relevant.
In applications, the will have bounded doubling, thus is bounded in ; taking ultraproducts, we see that is bounded also (i.e. less than a standard real number).
Now we want to extend this ultrapower to a universal model . To do this, we have to specify the language . will of course contain the language of groups, but if that is all that the language contains, then one cannot refer to or in this language. To add in is easy: one simply adds a unary predicate for membership in , so that “” is now a formula in . To add is a bit trickier: to keep the language countable, one is not allowed to measure all sets in the model, and also one does not want to work with non-standard real numbers. So instead, what one does is add predicates that are interpreted as “” for any definable set with parameters , and any (standard) rational number . (Note that by adding these predicates, one enlarges the space of possible definable sets; but one can iterate this countably many times to deal with this apparent circularity.) We thus obtain a countable set of predicates (even after iteration). With all these predicates, the language is now capable of interpreting as a standard (extended) real number (the supremum of all rational for which ); when the model is the ultrapower , this standard real number is simply the standard part of the non-standard real number .
[A slight subtlety: when one collapses to the standard real numbers, the predicate now deviates very slightly from its original interpretation ““. What is now true is that this predicate is implied by , and in turn implies ““, just as the assertion that a non-standard number is larger than is implied by the standard part being larger than , and in turn implies .]
With this language , we can now pass to a universal model . This is a group with a set , and a real number assigned to any set in or definable with parameters. It inherits all the elementary properties of , for instance is finitely additive and one has and . (One can use compactness and the Carathéodory extension theorem to extend to a -additive measure on the “Borel -algebra” generated by the definable sets; this is basically the Loeb measure construction, but we will not need it here.)
By construction, is a Keisler measure – a finitely additive measure on the definable sets. By construction, it is also -invariant – i.e. it is invariant under all automorphisms of that fix . One consequence of this is that the quantity depends only on the type of over . Actually, there is a stronger statement – the quantity depends continuously on using the topology generated by the -definable sets (by using the predicates ). Because of this, we call an -definable Keisler measure.
Remark 3 One does not need to pass through the non-standard real numbers here; instead, one can interpret directly as in the finite models , take an ultralimit (or some other theory that contains all the statements that are true in all but finitely many of the ) and then take a universal extension, and then reconstruct as the supremum of all for which holds. I find the temporary non-standard interpretation of to be helpful though in understanding why ends up deviating slightly from .
— 3. Wide types —
Recall that a partial type in over some set of constants is a set of -ary formulae using , which then defines a -definable (over ) subset of , being the set of all -tuples that realise those formulae. A complete type is a maximal such set of formulae (or a minimal -definable set, equivalently), or equivalently an orbit of the automorphism group of .
Note that given a complete type and a definable set, the type either falls entirely inside the set or is disjoint from it. (Indeed, a complete type can be thought of as an ultrafilter on the algebra of definable sets.) In practice, all the types we will consider will lie inside a definable set such as , which will have finite measure in applications.
Now for a key concept. A (partial or complete) type is wide if the set it defines it cannot be contained in a definable set of zero measure. More generally, a type is wide over a set of constants if it cannot be contained in an -definable set of zero measure. Wide sets are thus somewhat “generic” or “Zariski-dense” in some sense.
Lemma 2 Every wide partial type over can be refined to a wide complete type over .
Proof: Let be a wide partial type over . By finite additivity of , cannot be covered by finitely many -definable sets of measure zero, thus by saturation (compactness), cannot be covered by all of such sets at once. If we set to be with all the -definable sets of measure zero, is then also a partial type which is wide (since it is disjoint from, and hence not contained in, any -definable set of measure zero). If we then complete to any complete type (e.g. by taking an element of and computing its type), this type is then also wide.
A typical application of this lemma will be to start with a wide complete type over some set of constants, and then enlarge the set of constants, thus turning the complete type back into a partial type; but if one can show that the partial type remains wide, then one can refine it back to a wide complete type.
— 4. Types and group operations —
Types are well behaved with respect to group operations. For instance, if is a partial type over , and , then the shift of (defined by taking the set in or defined by and shifting it by ) is a partial type over ; if contained and was a complete type, then so is .
In a similar vein, if is a partial or complete type over , then is a partial or complete type over .
Slightly less obvious is that if are partial types over , then the product set is also a partial type over . Indeed, for any -definable sets containing , we see that is contained in the set , which is -definable (being cut out by the formula ““). On the other hand, if lies in all the , i.e. for each one can find realisations of the formula ““, then (as the intersection of definable sets is still definable) this whole family of formulae is finitely realisable, and thus (by saturation) realisable, which means that . Thus we have exhibited as a finite type.
— 5. Indiscernibles —
We already have a notion of elementary indistinguishability: two -tuples are elementarily indistinguishable (over some set of constants ) if every formula involving obeyed by is also obeyed by and vice versa (i.e. have the same type, or equivalently (by homogeneity) there is an automorphism that maps to ).
We can build upon this notion: a sequence is indiscernible (over ), if for every , the -tuples for are elementarily indistinguishable; thus the are indistinguishable, but also every ordered pair for are indistinguishable, and so forth. In practice, indiscernibles will be constructed by lots of Ramsey theory, and are sort of a way of pre-emptively doing all the Ramsey theory at once.
Lemma 3 Let be an -definable set for some , and for each , let be the slice (note that this is a -definable set). We assume that all the are contained in an -definable set of finite measure. Let be such that , and let be an indiscernible sequence (over ) with the type of (i.e. they are all elementarily indistinguishable from . Then any finite number of the have non-empty intersection (in fact their intersection has positive measure).
Proof: We establish this by induction. Suppose that we already know that
for all (note that this is already true for by hypothesis and indiscernability). We claim that
for also. Note by indiscernability that these measures do not actually depend on the choices of . Suppose for contradiction that we had
for one, and hence (by indiscernability) for all . In particular, this shows that the sets
are disjoint modulo null sets for . On the other hand, these sets have uniformly positive measure by induction hypothesis and indiscernability. Thus their union has unbounded measure, which contradicts the hypothesis that they all lie in a set of finite measure.
A remark: the above argument was phrased using the Kiesler measure , but the same argument also works for a more general structure known as a -ideal. We’re not clear yet whether this additional generality will be necessary for the applications at hand.
Now we combine wide types and indiscernables, showing that wide types can be perturbed to “look the same” with respect to any finite number of indiscernibles:
Lemma 4 Let 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 .
Proof: To abbreviate notation we suppress “over ” in everything that follows. (We’ll probably use this convention again in later seminars.)
Let be a formula obeyed by and , then the definable set cut out by is such that the slice has positive measure (since is wide). By the previous lemma, is thus non-empty, so we can find an such that is true for all . At present depends on ; but by using saturation one can make independent of , and the claim follows.