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.
15 comments
Comments feed for this article
23 October, 2009 at 12:39 pm
Anand Pillay
I just saw the informal notes. Quite impressive.
A quick remark on the question about equivalence relations:
If the inf.-definable equivalence relation
is defined by
many formulas
and underlying language is of size at most
and one works in a universal model of cardinality much bigger than
, then
is bounded if the cardinality of set of classes is at most
.
In fact it is enough to show that if
is one of the formulas defining E, then there are
such that for any
,
for some
. This follows by compactness. For if not we can find as large as one wants set of
such that
if
. Then E has as many classes as you want, contradicting boundedness.
In the paper I guess there is always a countable language and by convention the inf. definable equiv. relations are defined by at most countably many formulas. So you get the bound continuuum.
It is best possible: e.g if G is saturated model of
, then smallest bounded index type definable subgroup is
and the quotient is
(profinite completion).
Maybe it is said in the paper but another definition of bounded for a inf. definable equiv. relation
on definable set
is that
does not get bigger when passing from one saturated model to an elementary extension.
Also my personal impression is that whenever the paper talks about countable saturated model then one could take it to mean universal (or monster model). But ask the author.
The main point about bounded (for an equiv. relation) is that it generalizes
is definable then bounded = finite) and in that special case logic topology is the discrete one.
finite (i.e. if
24 October, 2009 at 10:31 am
Terence Tao
Thanks for the argument! I’ve updated the notes accordingly.
25 October, 2009 at 4:12 am
Anand Pillay
Another brief comment, now on Terence’s notes (section 2) on Keisler measures.
I think the point of adding the predicates
is not so much to extend
to a Keisler measure on a universal model (in fact Keisler measures on a model
or definable set in that model always extend to elementary extensions, just by compactness). But rather to get definability of the measure (over some small set of parameters
) hence
-invariance of the measure hence
-invariance of the corresponding ideal.
As in 2.6 of the paper it is done in just one step: We have
for
, in some language
, including a common predicate for the
, and common function symbol for the group operation on
, and assume
finite for all
. We have normalized counting measure
for each
, assigning
measure 1. For
, and
, adjoin new formula
to L to get language
.
Expand each
to
-structure
, defining, for
,
to hold iff
. (Iterate if you feel like it, namely do same thing with the new formulas.. etc to get ctble languages
, and take
to be the union) Now take any model
of the common
-theory of the
. (e.g. a saturated or universal model..).and by virtue of the formulas
we have a
-definable Keisler measure
on
giving X measure 1.
So in fact no need to even mention nonstandard real numbers (sorry if I am mistaken here).
25 October, 2009 at 11:52 am
Alex Usvyatsov
A quick remark related to Anand’s response concerning Keisler measures and making them definable. In order to get used to this construction, it may be helpful to consider the special case when the measure
is a type. So suppose that
is a type over a model (for simplicity)
. Then one can add to the language predicate
for every formula
with the right number of variables, and interpret this predicate as the set
. In this expansion of the
, the type
is clearly definable.
Curiously enough, this construction can be used to show the existence of an indiscernible sequence in the type
(a fact also mentioned in Terry’s notes above). This can possibly be seen as an easy combinatorial application of this method (normally existence of indiscernible sequences is shown using Ramsey’s Theorem). Let
be a global extension of
(in the expanded language) definable over
. So for
in the universal domain,
if and only if
holds. Now construct a “Morley sequence” in
over
, that is,
. It is very easy to show that such a sequence is indiscernible over
(this would be true for any
extending
, which is invariant over
). In particular, this sequence is, of course, indiscernible with respect to the original (smaller) language.
This observation on existence of indiscernibles is not always enough for applications needed in the paper, because sometimes one needs to start with a fixed sequence and in a sense “keep” its finitary type (for this one would use Morley’s Theorem, equivalently, stronger partition results, such as Erdos-Rado Theorem).
Another small comment: a Keisler measure (by definition) does not need to be invariant over a small set (if it is, it is called an invariant Keisler measure).
25 October, 2009 at 6:21 pm
Terence Tao
Thanks for the comments! I think I understand Keisler measures a bit better now. I’ve adjusted the text a bit to reflect the above discussion.
When you interpret types
as special kinds of measures, I assume that this is like how points can be interpreted as Dirac mass measures, so that the measure
assigns 1 to any definable set that contains p, and 0 to any definable set that is disjoint from p.
The whole game of making a measure definable by enlarging the language appropriately seems analogous to making a set open (or measurable, etc.) simply by throwing it into the topology (or sigma-algebra, etc.) and seeing what it generates.
26 October, 2009 at 2:50 am
Alex Usvyatsov
Dear Terry,
You are absolutely right in your last observation – after all, all we are doing is making a certain function on the type space continuous by enlarging the topology.
Indeed, a type
is a
-Keisler measure: 1 if the formula is in
, 0 otherwise. Sorry for leaving this out.
Another thing I wanted to mention in my comment and forgot is that one can use existence of indiscernible sequences to see that e.g. a type-definable equivalence that has more than continuum many classes is unbounded (so I am assuming that everything is countable). Let
be such a relation, and
are pairwise nonequivalent. By Erdős-Rado theorem there is a subsequence of length
(all we care is that it is infinite) which is 2-indiscernible. Hence by compactness there is such a sequence of any length – so there are as many
-classes as we want. The point is that once we have an indiscernible sequence (2-indiscernible is enough in this case), we can apply compactness.
26 October, 2009 at 2:55 am
Alex Usvyatsov
My apologies again. I have a silly question: is there a way of previewing comments before posting them? [Unfortunately not; this is perhaps the biggest defect in this installation of wordpress (they cite security concerns). But I can correct the comment manually. -T]
29 October, 2009 at 2:48 am
Anand Pillay
29 October, 2009 at 4:22 am
Alex Usvyatsov
Here are some notes that I wrote on the proof of Corollary 1.2 for our seminar. Hope they will be of some help. Corrections are very welcome.
Let me be the first to (as Ward has put it) share my confusion. I am a bit unclear on the issue of parameters one works over. For example, in the proof of Corollary 1.2 Udi seems to be working over
, whereas the stabilizer is type definable over some model
, which is obtained in Lemma 2.14. In the proof of Corollary 1.2, for example, it doesn’t seem possible to just throw in constants for a model. In my notes, I dealt with this issue in the following way: take an ultra-product of counterexamples. Since it is
-saturated, we may assume that
lies in it. By working to begin with with formulas with parameters over the finite structures, we can strengthen the demand on
in the ultra-product: no subgroup defined with parameters (over
, say) which lies in
can finitely cover
.
First, I hope I am not making a mistake here. Second, my question is: is there something I am missing? Is there an easier way to avoid this issue?
1 November, 2009 at 4:55 am
Alex Usvyatsov
Apparently, the parameters issue is clarified in the new version of Udi’s paper. Indeed, in the proof of Corollary 1.2 one can work with parameters (e.g. like in my notes, or in Anand’s comment). On the other hand, using the correspondence with Lie group, one can obtain
over the empty set (see Lemma 4.5). So confusion withdrawn.
29 October, 2009 at 10:56 am
Terence Tao
Dear Anand and Alex,
Thank you very much for supplying your own notes on these papers, this will be very useful for our group to “catch up”…
30 October, 2009 at 10:48 am
Reading seminar 3: “Stable group theory and approximate subgroups”, by Ehud Hrushovski « What’s new
[…] types for us will be that they can be used to generate sequences of indiscernibles (as defined in previous notes): Lemma 3 Let be a global invariant type of some arity , and construct recursively a sequence […]
5 November, 2009 at 9:11 pm
Reading seminar 4: “Stable group theory and approximate subgroups”, by Ehud Hrushovski « What’s new
[…] that the index of in does not exceed in cardinality (i.e. has bounded index, see Lemma 1 of Notes 2). Indeed, if this were not the case, then one could find more than disjoint cosets in , and hence […]
20 November, 2009 at 11:54 am
Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovsk « What’s new
[…] Anand Pillay’s sketch of a simplified proof of Theorem 1.1. […]
2 May, 2012 at 12:17 am
Daniel Lowengrub
Hi,
be
without all of the
-definable sets of measure zero? Because we want
to be disjoint from all of those sets.
Thanks for the great notes. I have one small question. In the proof of lemma 2, shouldn’t
[Corrected, thanks – T.]