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 1 Let
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 2 Let
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 3 Let
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 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
.
We now use this lemma to show that sets defined by wide types intersect each other in a uniform fashion.
Lemma 5 Let
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 6 Let
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
ayhangunaydin
I think the type p should be invariant in Lemma 1. [Corrected, thanks – T.]
4 November, 2009 at 12:58 pm
Terence Tao
Lou 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
Link
How do you open .dvi files?
4 November, 2009 at 7:32 pm
Terence Tao
A PDF version is also available at
Click to access approx.pdf