1 Introduction
Ramsey theory has substantial and diverse applications to many parts of mathematics. In particular, Ramsey’s theorem has foundational applications to model theory through the Ehrenfeucth–Mostowski construction of indiscernibles and generalizations thereof. In this paper we explore the converse direction, that is, we use model theory to obtain new proofs of classical results in Ramsey Theory.
The Stone–Čech compactification, obtained via ultrafilters, is a widely employed method for proving Ramsey theoretic results. One of its first major applications is the celebrated Galvin–Glazer proof of Hindman’s theorem, see, e.g., [Reference Blass4]. Our methods are related, but alternative, to the ultrafilter approach. We replace
$\beta G$
(the Stone–Čech compactification of a semigroup G) with a large saturated elementary extension of G, i.e., a monster model of
$\text {Th}(G/G)$
. One immediate advantage is that we work with elements of a natural semigroup with a natural operation. In contrast, elements of
$\beta G$
are ultrafilters, that is, sets of sets, and the semigroup operation among ultrafilters is far from straightforward.
This idea is not completely new: in his seminal work on the applications of topological dynamics to model theory [Reference Newelski14, Reference Newelski15], Newelski replaces the semigroup
$\beta G$
with the space of types over G with a suitably defined operation. Our approach is similar, except that, unlike Newelski, we do not pursue connections with topological dynamics, but rather offer an alternative realm of application. The investigation of alternative methods in the study of regularity phenomena has been called for by Di Nasso [Reference Di Nasso5, Open problem #1]. This article contains a possible answer.
The model theoretic tools employed in this paper are relatively basic. Section 2 is meant to give an accessible overview of the necessary notions for readers whose expertise is not primarily in model theory. Our results do not require assumptions of model theoretic tameness such as stability, NIP, etc., much like those that use nonstandard analysis, for example in [Reference Di Nasso, Goldbring and Lupini6]. Investigating the effect of such assumptions remains as future work.
When this paper was essentially complete, we became aware of [Reference Andrews, Conant and Goldbring2], which is worth mentioning since it employs similar methods in a related context.
The paper is divided into two parts. In the first part we prove that the notion of coheir leads to short and elegant proofs of well-known results. Most proofs in this part may be considered folklore, though they have not appeared in the literature so far. They are included here to provide a self-contained, gentle introduction to the techniques that are used in the second part.
As a preliminary illustrative step, we present a proof of Ramsey’s theorem (Theorem 3.1). Then we prove a generalization of Hindman’s theorem (Theorem 5.1), which is required in the second part of the paper. We also show how to combine Ramsey’s and Hindman’s theorems in a single proposition—the Milliken–Taylor theorem (Theorem 5.3). Finally, we prove an abstract algebraic version of the Hales–Jewett theorem (Theorem 6.4) due to Sabine Koppelberg [Reference Koppelberg11].
In the second part of the paper we prove two Ramsey-theoretic properties of semigroups (Lemmas 7.1 and 8.1). As an application, we derive a generalization of Carlson’s theorem on colourings of variable words which we present in the style of Koppelberg (Theorem 7.2) and in its classical form (Corollary 7.3). Lemma 8.1 is a partition theorem that generalizes Gowers’ FIN
$_k$
Theorem [Reference Gowers8] in a different direction than [Reference Lupini12].
The extent of the generalizations mentioned above is limited, and they could be obtained in other ways, but our motivation here is to show the use and relevance of model theoretic methods. Numerous papers in the literature strengthen or generalize the partition theorems considered here. The comparison of the results that appear in these papers is not always straightforward—a few are compared in [Reference Agostini and Colla1].
The proofs in this paper require a modicum of familiarity with model theory. However, the results can be stated in an elementary language, and in the rest of this introduction we introduce the necessary terminology.
Throughout the paper G is a semigroup and
$\Sigma $
a non-empty set of endomorphisms of G. For
${\bar a}\in G^{\le \omega }$
we write
$$ \begin{align*} {\text {fp}}^{\Sigma }\,\bar{a} = \big \{\sigma _{0}\,{a_{i_0}} \cdot\dots\cdot \sigma _{k}\,{a_{i_k}} : i_0<\dots <i_k<|\bar{a}|, \ \bar \sigma \in \big (\Sigma \cup \{\text {id}_G\}\big )^{k+1}, \ k<|\bar{a}|\big \}. \end{align*} $$
Overlined symbols, such as
$\bar a$
or
$\bar \sigma $
, always denote a tuple, and
$a_i$
,
$\sigma _i$
denote the ith entry of that tuple.
When
$\Sigma $
is empty, we write
${\text {fp}}\,\bar{a}$
.
Example 1.1. For future reference, we instantiate the definition above in the context of free semigroups. Let G be the set of words on a finite alphabet
$A\cup \{x\}$
, where x is a symbol not in A which we call variable. Let C be the set of words on the alphabet A. Words in C are called constant words, while those in
$G\smallsetminus C$
are called variable words. When G is endowed with the operation of concatenation of words, C and
$G\smallsetminus C$
are subsemigroups of G. For
$t\in G$
and
$a\in A$
, let
$t(a)$
be the word obtained by replacing all the occurrences of x in t by a. Note that the map
$\sigma _a:t\mapsto t(a)$
is an endomorphism of G. In the literature, when G is as above and
$\Sigma =\{\sigma _a:a\in A\}$
, the elements of
${\text {fp}}^{\Sigma }\,{\bar s}$
are called extracted words. We say that a tuple
$\bar a\in \big ({\text {fp}}^{\Sigma }\bar s\big )^{\omega }$
is an extracted sequence if
$a_i\in {\text {fp}}^{\Sigma }s_{\restriction \, [n_i,n_{i+1})}$
for some increasing sequence of positive integers
$\langle n_i:i<\omega \rangle $
. If, moreover,
$a_i\notin C$
for all i, we say that
$\bar a$
is an extracted variable sequence of
$\bar s$
.
The following definition will be used to express our results in the general context of semigroups.
Definition 1.2. Let
be a binary relation on G. We say that G is
-covered if for every finite
$A\subseteq G$
there is a c such that
. If c can be found in some fixed
$B\subseteq G$
, we say
-covered by B. We say that G is -closed if
implies
for all
${a},{b},{c}\in G$
. A
-chain in G is a tuple
$\bar{a}\in G^{\le \omega }$
such that
.
The preorder relation given by the length of the words on a free semigroup G is a natural example that is both -closed and
-covered. A less straightforward relation is used in the proof of Theorem 7.2.
Finally, we recall two standard notions. Let
$C\subseteq G$
be a subsemigroup. We say that C is nice if
$a\cdot b\in C$
implies
$a, b\in C$
. A homomorphism
$\sigma :G\to C$
such that
$\sigma _{\restriction C}=\text {id}_C$
is called retraction of G onto C. Note that the set of constant words in Example 1.1 is a nice subsemigroup and that the maps
$\sigma _a$
are retractions.
We are now ready to state Lemma 7.1.
Lemma. Let
$\Sigma $
be a finite set of retractions of G onto a nice subsemigroup C. Let
be a relation on G that makes it -closed and
-covered by
$G\smallsetminus C$
. Then, for every finite coloring of G, there is a
-chain
$\bar a\in (G\smallsetminus C)^\omega $
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus C$
is monochromatic.
When C and
$\Sigma $
are empty and
holds for all pairs, the lemma reduces to Hindman’s theorem (Theorem 5.1).
The appropriate choice of G, C,
$\Sigma $
, and
yields Carlson’s partition theorem (in particular no model theoretic argument is necessary, see Theorem 7.2 and its Corollary 7.3).
In the last section we prove Lemma 8.1 which is similar to the lemma above but deals with composition of homomorphisms. This is also stated in an elementary language and a general version of a partition theorem by Gowers is derived from it.
2 Coheirs, and coheir sequences
We assume that the reader is familiar with undergraduate model theory and in this section we only review the few prerequisites that go beyond that. Proofs are omitted. The reader may consult any standard model theory textbook, e.g., [Reference Tent and Ziegler18] (the intrepid reader may consult [Reference Zambella19], some lecture notes which use the same notation and quirks as this paper). The notation and terminology are standard with the possible exception of Definitions 2.3 and 2.5.
A sequence is a function whose domain is a linear order. A tuple is a sequence whose domain is an ordinal. The domain of the tuple
$ c $
is denoted by
$| c |$
and is called the length of
$ c $
.
Notation 2.1. Sometimes (i.e., not always) we may overline tuples as mnemonic. When a tuple
$\bar {c}$
is introduced,
$ c_i$
denotes the ith element of
$\bar {c}$
. We write
$ c_{\restriction I}$
, where
$I\subseteq |\bar {c}|$
, for the tuple which is naturally associated with the restriction of
$\bar {c}$
to I. The bar is dropped for ease of notation.
We denote the monster model by
or, when dealing with semigroups, by
. We always work over a fixed set of parameters
. When this set is a model, as it will often be, we denote it by M, or G in the case of semigroups.
We say that a type
$p(x)$
is finitely satisfied in A if every conjunction of formulas in
$p(x)$
has a solution in
$A^{|x|}$
. A global type that is finitely satisfiable in A is invariant over A.
If M is a model every consistent type
$p(x)\subseteq L(M)$
is finitely satisfied in M. For this reason in a few points in this paper it is necessary to work over a model. For simplicity, we always assume this.
The following is an easy, well-known fact.
Proposition 2.2. Every type
that is finitely satisfiable in M has an extension to a global type finitely satisfiable in M.
If
$p(x)$
is finitely satisfied in M, the extensions of
$p(x)$
that are also finitely satisfied in M are called coheirs of
$p(x)$
.
In many cases it is useful to focus on elements instead of their types. We introduce the following notation to express that
$\text {tp}( a /M, b )$
is finitely satisfied in M. (The notion is standard in model-theory, and it has no standard notation though.)
Definition 2.3. For every
and
we define
We call this the coheir–heir relation. We define the type
The tuples
$ a $
realizing this type are those such that
. We will use the symbol
for the union of the types
and
$\text {tp}( a /M)$
.
We imagine
as saying that
$ a $
is independent from
$ b $
over M. This is a very strong form of independence. In general it is not symmetric, that is,
is not the same as
(symmetry is equivalent to stability).
We shall use, sometimes without reference, the following easy lemma.
Lemma 2.4. The following properties hold for all small
$M, a , b $
, and
$c$
:
-
1.
for every
invariance; -
2.
for all finite
$ a_0\subseteq a $
and
$ b_0\subseteq b $
finite character; -
3.
and
transitivity; -
4.
there exists
$ a^{\prime} \equiv_{M,\, b} a $
such that
coheir extension.
Note that
is the intersection of all types in
$S(M, b )$
that are coheirs of
$\text {tp}( a /M)$
. As there may be more than one of such coheirs,
need not be a complete over
$M, b $
. In fact, completeness is a rather strong property.
Definition 2.5. If
is a complete type (over
$M, b $
) for every
, every
, and every tuple of variables x, then we say that
is stationary. We say n-stationary if the requirement above is restricted to
$|x|=n$
.
Stationarity is often ensured by the following property.
Proposition 2.6. Fix a tuple of variable x of length n. If for every
there is a formula
$\psi (x)\in L(M)$
such that
$\varphi (M^{|x|})=\psi (M^{|x|})$
then
is n-stationary.
Remark 2.7. Stationarity of
over every model M is equivalent to the stability of T. However, in unstable theories the assumption may hold for some particular model. For example, if every subset of
$M^n$
is the trace of a definable set, then
is n-stationary by the proposition above. This simple observation will be of help in the proof of Theorem 5.1. For natural example let
$T=T_{\textrm {dlo}}$
and let
have the order-type of
. By quantifier elimination every definable of
is union of finitely many intervals. By Dedekind completeness, the trace on A of any interval of
coincides with that of an M-definable interval.
Let
be a global type that is finitely satisfiable in M. We say that the tuple
$\bar {c}$
is a coheir sequence of
$p(x)$
over M if
$c_i\models p_{\restriction M,\, c_{\restriction i}}(x)$
for every
$i<|\bar {c}|$
.
The following is a convenient characterization of coheir sequences.
Lemma 2.8. For
$\bar {c}$
a tuple of length
$\omega $
, the following are equivalent:
-
1.
$\bar {c}$
is a coheir sequence over
$M;$
-
2.
and
$ c_{n+1}\equiv _{M,\, c_{\restriction n}} c_n$
for every
$n<\omega $
.
Let
$I,<_I$
be a linear order. We call a function
an I-sequence, or simply a sequence when I is clear.
If
$I_0\subseteq I$
we call
$ a_{\restriction I_0}$
, the restriction of
$\bar {a}$
to
$I_0$
, a subsequence of
$\bar {a}$
. When
$I_0$
is finite we identify
$ a_{\restriction I_0}$
with a tuple of length
$|I_0|$
.
Definition 2.9. Let
$I,<_I$
be an infinite linear order and let
$\bar {a}$
be an I-sequence. We say that a is a sequence of indiscernibles over A or, a sequence of A-indiscernibles, if
$ a_{\restriction I_0}\equiv _A a_{\restriction I_1}$
for every
$I_0,I_1\subseteq I$
of equal finite cardinality.
The following can be easily derived from the lemma above by induction.
Proposition 2.10. Every sequence of coheirs over M is M-indiscernible.
3 Ramsey’s theorem from coheir sequences
We illustrate the relation between coheirs and Ramsey phenomena in the simplest possible case: Ramsey’s theorem. The subsequent sections build on this proof for more sophisticated results.
In this chapter we deal with finite partitions. The partition of a set X into k subsets is often represented by a map
$f:X\to [k]$
. The elements of
$[k]=\{1,\dots ,k\}$
are also called colors, and the partition a coloring, or k-coloring, of X. We say that
$Y\subseteq X$
is monochromatic if f is constant on Y.
Let M be an arbitrary infinite set. Fix
$n,k<\omega $
and fix a coloring f of the set of all n-subsets of M, i.e., the complete n-uniform hypergraph with vertex set M,
$$ \begin{align*} \displaystyle f\ :\ {M\choose n}\ \ \to\ \ [k]. \end{align*} $$
We say that
$H\subseteq M$
is a monochromatic subgraph if the subgraph induced by H is monochromatic. In the literature monochromatic subgraphs are also called homogeneous sets.
The following is a very famous theorem which we prove here in an unusual way. The proof will serve as a blueprint for other constructions in this paper.
Ramsey’s Theorem 3.1. Let M be an infinite set. Then for every positive integer n and every finite coloring of the complete n-uniform hypergraph with vertex set M there is an infinite monochromatic subgraph.
Proof Let L be a language that contains k relation symbols
$r_1,\dots ,r_k$
of arity n. Given a k-coloring f we define a structure with domain M. The interpretation of the relation symbols is
$$ \begin{align*} r_i^M \ =\ \{ a_1,\dots,a_n\in M \ : \ f\big(\{a_1,\dots,a_n\}\big)= i\}. \end{align*} $$
We may assume that M is an elementary substructure of some large saturated model
. Pick any type
finitely satisfied in M but not realized in M and let
$\bar {c}=\langle c_i:i<\omega \rangle $
be a coheir sequence of
$p(x)$
.
There is a first-order sentence saying that the formulas
$r_i(x_1,\dots ,x_n)$
are a coloring of
${M\choose n}$
. Then by elementarity the same holds in
. By indiscernibility, all tuples of n distinct elements of
$\bar {c}$
have the same color, say
$1$
. We now prove that there is a sequence
$\bar a=\langle a_i:i<\omega \rangle $
in M with the same property.
We construct
$a_{\restriction i}$
by induction on i as follows.
Assume as induction hypothesis that the subsequences of length n of
$a_{\restriction i}, c_{\restriction n}$
all have color
$1$
. Our goal is to find
$a_i\in M$
such that the same property holds for
$a_{\restriction i},a_i, c_{\restriction n}$
. By the indiscernibility of
$\bar {c}$
, the property holds for
$a_{\restriction i}, c_{\restriction n}, c_n$
. And this can be written by a formula
$\varphi (a_{\restriction i}, c_{\restriction n}, c_n)$
. As
$\bar {c}$
is a coheir sequence, by Lemma 2.8 we can find
$a_i\in M$
such that
$\varphi (a_{\restriction i}, c_{\restriction n},a_i)$
. So, as the order is irrelevant,
$a_{\restriction i},a_i, c_{\restriction n}$
satisfies the induction hypothesis.
4 Idempotent orbits in semigroups
In this and the following sections we fix a semigroup G which we identify with a first-order structure. The language contains, among others, the symbol
$\cdot $
which is interpreted as a binary associative operation on G. We write
for a large saturated elementary extension of G.
For any two sets
we define
In this and the next section we abbreviate
, the orbit of
$ a $
under
, with
$ a _G$
. We write
for
. Similarly for
and
$ a \cdot _G b $
.
Lemma 4.1. If
is type definable over G then so is
for any
$ b $
.
Proof The set
is the union of
as
$ c $
ranges in
$ b _G$
. The set
is type definable, say by the the type
$\exists y\, p(x, y, c )$
where
Note that, by the invariance of
, if
, then
$\exists y\, p(x, y,f c )$
defines
. Therefore if
$q(z)=\text {tp}( b /G)$
then
$\exists y,z\, \big [q(z)\cup p(x, y,z)\big ]$
defines
.
By the invariance of
, for every
we have
. Therefore when
and
are invariant over G, also
is invariant over G. Below we mainly deal with invariant sets.
Proposition 4.2. For all G-invariant sets
,
, and
Proof Let
$ a {\cdot } b {\cdot } c $
be an arbitrary element of the l.h.s. where
and
. By extension (Lemma 2.4), there exists
$ {a^{\prime }} $
such that
. By transitivity (again Lemma 2.4),
. Therefore
$ {a^{\prime }} {\cdot } b {\cdot } c $
belongs to the r.h.s. Finally, as
$ {a^{\prime }} \equiv _{G,\, b \cdot c} a $
, also
$ a {\cdot } b {\cdot } c $
belongs to the r.h.s. by invariance.
Let
be a non-empty set. When
, we say that it is idempotent (over G).
Corollary 4.3. Assume
are both G-invariant. Then if
is idempotent, also
is idempotent.
Proof We check that if
is idempotent so is
because
by the lemma above
We show that, under the assumption of stationarity, the operation
$\cdot _G$
is associative. The quotient map
is almost a homomorphism.
Proposition 4.4. Assume
is
$1$
-stationary, see Definition 2.5. Fix
arbitrarily. Then
$ {a'} {\cdot } b' \equiv _G a {\cdot } b $
for every
$ {a'} \equiv _G a $
and
$ b' \equiv _G b $
such that
. Or, in other words,
$(a {\cdot } b )_G= a \cdot _G b$
.
Proof We prove two inclusions, only the second one requires stationarity.
$\subseteq $
As
holds by hypothesis,
$ a {\cdot } b \in a \cdot _G b $
. The inclusion follows by invariance.
$\supseteq $
By invariance it suffices to show that the l.h.s. contains
$ a \cdot _G\{ b \}$
. Let
$ {a'} \in a _G$
such that
. We claim that
$ {a'} {\cdot } b \in ( a {\cdot } b )_G$
. Both
$ a $
and
$ {a'} $
satisfy
. By
$1$
-stationarity,
$ a \equiv _{G,\, b } {a'} $
. Hence
$ a {\cdot } b \equiv _G {a'} {\cdot } b $
.
Corollary 4.5 (Associativity)
Assume
is
$1$
-stationary. Then for all G-invariant sets
,
, and
Proof We can assume that
,
, and
are G-orbits. Say of
$ a $
,
$ b $
, and
$ c $
respectively. We can assume that
and
. By Proposition 4.4 the set on the l.h.s. equals
$( a {\cdot } b {\cdot } c )_G$
. By a similar argument the set on the r.h.s. equals
$( {a'} {\cdot } b' {\cdot } c' )_G$
for some elements
$ {a'} $
,
$ b' $
, and
$ c' $
. Proposition 4.2 proves that inclusion
$\subseteq $
holds in general. But inclusion between orbits amounts to equality.
The following lemma proves the existence of idempotent orbits. The proof is self-contained, i.e., it does not use Ellis’ theorem on the existence of idempotents in compact left topological semigroups (however, the argument is very similar). As a comparison, finding a proof in the setting of nonstandard analysis is listed as an open problem in [Reference Di Nasso5].
Lemma 4.6. Assume
is
$1$
-stationary. If
is minimal among the idempotent sets that are type-definable over G, then
for some (any)
.
Proof Fix arbitrarily some
. By Corollary 4.3, the set
is contained in
, idempotent and type-definable over G by Lemma 4.1. Therefore by minimality
. Let
be the set of those
$ a $
such that
$ a \cdot _G b = b _G$
. This set is non-empty because
. It is easy to verify that
is type-definable over
$G, b $
. As it is clearly invariant over G, it is type-definable over G. By associativity it is idempotent. Hence, by minimality,
. Then
, which implies
$ b \cdot _G b = b _G$
. That is,
$ b $
has idempotent orbit. Finally, by minimality,
.
Corollary 4.7. Under the same assumptions of the lemma above, every idempotent set that is type-definable over G contains an element with an idempotent orbit.
5 Hindman’s theorem
In this section we merge the theory of idempotents presented in Section 4 with the proof of Ramsey’s theorem to obtain Hindman’s theorem [Reference Hindman10].
Let
$\bar{a}$
be a tuple of elements of G of length
$\le \omega $
. In Section 1 we defined
${\text {fp}}\ \bar{a}$
and the notions of -closed and
-covered. The relation
is introduced mainly for future reference. The classical Hindman’s theorem is obtained with the positive integers (as an additive semigroup) for G and
$<$
for
.
Hindman Theorem 5.1. Let
be a relation on G that makes it -closed and
-covered. Then for every finite coloring of G there is a
-chain
$\bar a$
such that
${\text {fp}}\,\bar a$
is monochromatic. If there is no
$g\in G$
such that
, we may further assume that the elements of the
-chain are all distinct.
Proof We interpret G as a structure in a language that extends the language of semigroups with a symbol for
and one for each subset of G. Let
be a saturated elementary superstructure of G. As observed in Remark 2.7, the language makes
trivially
$1$
-stationary.
We write
for the type-definable set
, which is non-empty because G is
-covered. We claim that
is idempotent. In fact, if
then, as
and
, we must have that
. Therefore, from the -closedness of G we infer
.
Let
$g_0$
be an element of
with idempotent orbit as given by Corollary 4.7. We can assume that
$g_0\notin G$
otherwise the sequence that is identically
$g_0$
trivially proves the theorem. We can assume that
$g_0\notin G$
otherwise the sequence that is identically
$g_0$
trivially proves the theorem. If we want the elements of the chain
$\bar {a}$
to be distinct it suffices require that
$g_0\notin G$
. By definition of
$g_0$
, this can be directly assumed when there is no
$g\in G$
such that
.
Let
be a global coheir of
$\text {tp}(g_0/G)$
. Let
$\bar {g}$
be a coheir sequence of
$p(x)$
, that is
$g_i\ \models \ p_{\restriction G,\, g_{\restriction i} }(x)$
.
We write
for the tuple
$ g_{i-1},\dots , g_{0}$
. By the idempotency of
$(g_0)_G$
and Proposition 4.4,
$h\equiv _Gg_0$
for all
and all i. It follows in particular that
is monochromatic, say all its elements have color
$1$
. Now, we use the sequence
$\bar {g}$
to define
$\bar a\in G^\omega $
such that all elements of
${\text {fp}}\,\bar a$
have color
$1$
.
Assume as induction hypothesis that
${\text {fp}}(a_{\restriction i},\,g_0)$
is monochromatic of color
$1$
. Our goal is to find
$a_i$
such that the same property holds for
${\text {fp}}(a_{\restriction i+1},\,g_0)$
.
First we claim that from the induction hypothesis it follows that, for all j, all elements of
have color
$1$
. In fact, the elements of
have the form
$b\cdot h$
for some
$b\in {\text {fp}}(a_{\restriction i})$
and
. As
$ h\equiv _Gg_0$
, we conclude that
$b\cdot h\equiv _Gb\cdot g_0$
, which proves the claim.
Let
$\varphi (a_{\restriction i},\, g_{i+1},\, g_{\restriction i+1})$
say that all elements of
have color
$1$
. As
$\bar {g}$
is a coheir sequence we can find
$a_i$
such that
$\varphi (a_{\restriction i},\,a_i,\, g_{\restriction i+1})$
. Hence all elements of
have color
$1$
. Therefore
$a_i$
is as required.
Hindman’s theorem generalizes to a proposition that subsumes Ramsey’s theorem. It is usually referred to as the Milliken–Taylor theorem [Reference Milliken13] and [Reference Taylor17]. By the following observation, we may use virtually the same proof.
Proposition 5.2. Assume
is
$1$
-stationary. Let
be a coheir sequence of some global coheir of
$\text {tp}( g /G)$
where
$ g $
has idempotent orbit. Let
be such that
for some finite non-empty
$I_i\subseteq \omega $
such that
$I_i<I_{i+1}$
. Then
$\bar {h}\equiv _G\bar {g}$
.
Proof Write
$n_i$
for the minimum of
$I_i$
. It suffices to prove that
$ h_i\equiv _{G, g_{\restriction n_i}} g_{n_i}$
. Note that the type
is satisfied both by
$ h_i$
and
$ g_{n_i}$
, hence the claim follows by stationarity.
Write
${\text {fp}}(\bar a)_n$
for the n-uniform hypergraph with vertex set
${\text {fp}}(\bar a)$
and as edges those sets
$\{h_1,\dots ,h_n\}$
such that
$h_i\in {\text {fp}}(a_{\restriction I_i})$
for some finite sets
$I_1<\dots <I_n$
.
Milliken–Taylor Theorem 5.3. Let
be a relation on G that makes it -closed and
-covered. Then for every positive integer n and every finite coloring of the complete n-uniform hypergraph with vertex set G there is a
-chain
$\bar a$
such that
${\text {fp}}(\bar a)_n$
is monochromatic.
Proof Given a coheir sequence
$\bar {g}$
as in the proof of Theorem 5.1 we want to define
$\bar a\in G^\omega $
such that
${\text {fp}}(\bar a)_n$
is monochromatic. By the proposition above,
is monochromatic for every
$i\ge n$
. As in the proof of Theorem 5.1, we define by induction
$\bar a\in G^\omega $
in such a way that
is a finite monochromatic subgraph of G.
6 The Hales–Jewett theorem
The Hales–Jewett theorem is a purely combinatorial statement that implies the van der Waerden theorem. The original proof by Alfred Hales and Robert Jewett is combinatorial [Reference Hales and Jewett9]. An alternative proof, also combinatorial, is due by Saharon Shelah [Reference Shelah16]. Our proof is similar to the proof by Andreas Blass in [Reference Blass4] (based on ideas from [Reference Bergelson, Blass and Hindman3]), but we use saturated models where he uses Stone–Čech compactification. We present three versions of the main theorem.
First we prove an abstract algebraic version due to Sabine Koppelberg [Reference Koppelberg11] which is easier to state and to prove (this version comes in two variants). The classical version follows easily from the algebraic one.
We work with the same notation as in Section 4. We say that an element
$ c $
is left-minimal (w.r.t.
) if
for every
.
Proposition 6.1. Assume
is
$1$
-stationary. Let
be idempotent and type-definable over G. Then
contains a left-minimal element
$ c $
with idempotent orbit.
Proof Construct by induction a chain of type-definable idempotent sets
and elements
such that
and
. For
$\alpha $
limit take the intersection. By idempotency of
, it is straightforward to check that
. The sets
are type-definable and idempotent by Lemma 4.1 and Corollary 4.3. For
$\alpha $
limit
is non-empty by compactness, as it is intersection of a chain of closed sets.
For some
$\alpha $
we cannot properly extend this construction. For this
$\alpha $
, for every
we have
. Hence every
is left-minimal. As
is idempotent, by Corollary 4.7 there is some
with idempotent orbit.
Proposition 6.2. Assume
is
$1$
-stationary. Let
be idempotent and type-definable over G. Let
$ c _G$
be idempotent and such that
. Then
-
1.
contains some
$ g $
with idempotent orbit; -
2. if moreover
$ c $
is left-minimal, then
$ c \equiv _G g $
for every
$ g $
as in
$1$
.
Note, parenthetically, that the set in 1 may not be type-definable, therefore Corollary 4.7 does not apply directly and we need an indirect argument.
-
1. From
we obtain that
is idempotent. As it is also type-definable,
contains a
$ b $
with idempotent orbit by Corollary 4.7. There is an
such that
$ b _G= a \cdot _G c $
, then
$ b \cdot _G c = b _G$
. From this we obtain that
$ c \cdot _G b $
is idempotent and contained in
. -
2. From
and the idempotency of
$ c _G$
we obtain
$ g _G= c \cdot _G g $
. As
, from the left-minimality of
$ c _G$
we obtain
. Hence
$ c _G= c \cdot _G g $
, by the idempotency of
$ g _G$
. Therefore
$ c _G= g _G$
, which proves 2.
The following is a technical lemma that is required in many proofs below.
Proposition 6.3. Assume
is
$1$
-stationary. Let
be a semigroup homomorphism definable over G. Then for every
-
1.
$\sigma \big [ a _G\big ] \ =\ (\sigma \, a )_G$
, -
2.
$\sigma \big [ a \cdot _G b \big ] \ =\ \sigma \, a \cdot _G\sigma \, b $
.
-
1. As
$ a \equiv _G {a'} $
implies
$\sigma \, a \equiv _G\sigma \, {a'} $
, inclusion
$\subseteq $
is clear. For the converse, note that the type
$\exists y\,\big [\sigma \,y=x \,\wedge \, y\equiv _G a \big ]$
is trivially realized by
$\sigma \, a $
. Therefore it is realized by all elements of
$(\sigma \, a )_G$
. Hence all elements of
$(\sigma \, a )_G$
are the image of some element in
$ a _G$
. -
2. Let
. By Proposition 4.4 we have
$\sigma \big [ a \cdot _G b \big ] =\sigma \big [( {a'} \cdot b' )_G\big ]$
. Then it suffices to prove that
$\sigma \big [( {a'} \cdot b' )_G\big ] \subseteq \sigma \, a \cdot _G\sigma \, b $
, because by 1 and Proposition 4.4 both sides of the equality are orbits. As
$\sigma $
preserves
and orbits, we obtain that
$\sigma ( {a'} \cdot b' )$
is in
$\sigma \, a \cdot _G\sigma \, b $
, as well as all other elements of
$\sigma \big [( {a'} \cdot b' )_G\big ]$
.
Hales–Jewett Theorem 6.4 (Koppelberg’s version)
Let G be an infinite semigroup and let
$C\subset G$
be a nice subsemigroup. Let
$\Sigma $
be a finite set of retractions of G onto C. Then, for every finite coloring of C, there is an
$a\in G\smallsetminus C$
such that
$\{\sigma \,a:\sigma \in \Sigma \}$
is monochromatic.
Proof Let
. Here
is a monster model in a language that expands the natural one with a symbol for all subsets of G and for every retraction in
$\Sigma $
. As observed in Remark 2.7, this makes
trivially
$1$
-stationary. Let
be the definable set such that
. By elementarity,
is a nice subsemigroup of
. The language contains also symbols for the retractions
.
By Proposition 6.1, there is a left-minimal
with idempotent orbit.
By niceness,
and
$ c $
satisfy the assumptions of Proposition 6.2. Hence, by the first claim of that proposition, there is an idempotent
. In particular,
. Now apply the second claim of Proposition 6.3, with
for
to obtain
for all
$\sigma \in \Sigma $
. As
$\sigma \, g $
is also idempotent, we apply Proposition 6.2 to conclude that
$\sigma \, g \equiv _G c $
. In particular the set
$\{\sigma \, g :\sigma \in \Sigma \}$
is monochromatic.
Though the element
$ g $
above does not need to belong to
$G\smallsetminus C$
, by elementarity
$G\smallsetminus C$
contains some a with the same property and this proves the theorem.
Finally we show how the classical Hales–Jewett theorem follows from its abstract version.
If C and X are two semigroups we denote by
$C*X$
their free product. That is,
$C*X$
contains finite sequences of elements of
$C\cup X$
, below called words, that alternate elements in C with elements in X. The product of two words is obtained concatenating them and, when it applies, replacing two contiguous elements of the same semigroup by their product. Note that C and X are nice subsemigroups of
$C*X$
. When X is the free semigroup generated by a variable x, we denote
$C*X$
by
$C[x]$
. If
$w(x)$
is an element of
$C[x]$
and
$a\in C$
we denote by
$w(a)$
the result of replacing x by a in
$w(x)$
.
Hales–Jewett Theorem 6.5 (Classical version)
Let C be a semigroup generated by some finite set A. Let x be a variable. Then for every finite coloring of
$C[x]$
there is a
$w(x)\in C[x]\smallsetminus C$
such that
$\{ w(a): a\in A\}$
is monochromatic.
Proof Let
$G=C[x]$
. For every
$a\in A$
the homomorphism
$\sigma _a:w(x)\mapsto w(a)$
is a retraction of G onto C. Hence we can apply the theorem above.
We conclude with a variant of Theorem 6.4 that applies to a broader class of semigroup homomorphisms. This result is not required for the following.
For
$\Sigma $
a set of maps
$\sigma :G\to C$
and
$c\in C$
we define
$$ \begin{align*} \displaystyle\Sigma^{-1}[c]\ =\ \bigcap_{\sigma\in\Sigma}\sigma^{-1}[c]. \end{align*} $$
Clearly, when the maps in
$\Sigma $
are retractions,
$\Sigma ^{-1}[c]$
is non-empty for all
$c\in C$
because it contains at least c.
Hales–Jewett Theorem 6.6 (Yet another variant)
Let C be a semigroup and let
$\Sigma $
be a finite set of homomorphisms
$\sigma :G\to C$
such that
$\Sigma ^{-1}[c]$
is non-empty for all
$c\in C$
. Then, for every finite coloring of C, there is a
$g\in G$
such that the set
$\{\sigma \,g\ :\ \sigma \in \Sigma \}$
is monochromatic.
Proof Let
$G*C$
be the free product of the two semigroups. Any homomorphism
$\sigma :G\to C$
extends canonically to a retraction of
$G*C$
onto C. The elements of G that occur in a word are replaced by their image under
$\sigma $
, finally the elements in the resulting sequence are multiplied. This extension is denoted by the same symbol
$\sigma $
.
Apply Theorem 6.4 to obtain some
$w\in G*C$
such that
$\{\sigma \,w:\sigma \in \Sigma \}$
is monochromatic. Suppose
$w=c_0\cdot g_0\cdots c_n\cdot g_n$
for some
$g_i\in G$
and
$c_i\in C$
, where one or both of
$c_0$
or
$g_n$
could be absent. Pick some
$h_i\in \Sigma ^{-1}[c_i]$
and let
$g=h_0\cdot g_0\cdots h_n\cdot g_n$
. Then
$\{\sigma \,g:\sigma \in \Sigma \}$
is monochromatic as required to complete the proof.
7 Carlson’s theorem
This section is devoted to the following lemma and some of its consequences.
Lemma 7.1. Let
$\Sigma $
be a finite set of retractions of G onto a nice subsemigroup C. Let
be a relation on G that makes it -closed and
-covered by
$G\smallsetminus C$
. Then, for every finite coloring of G, there is a
-chain
$\bar a\in (G\smallsetminus C)^\omega $
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus C$
is monochromatic.
Proof The models
and
are as in the proof of Theorem 6.4. The language is the same with
included. Let
. By Proposition 6.1 there is some left-minimal
with idempotent orbit. As G is
-covered by
$G\smallsetminus C$
, the set
is non-empty. As G is -closed and C is nice,
and
$ c $
satisfy the assumptions of Proposition 6.2. Then,
contains some
$g_0$
with idempotent orbit. By Proposition 6.3, we obtain that
for all
$\sigma \in \Sigma $
. As
$(\sigma \,g_0)_G$
is also idempotent, we apply the second claim of Proposition 6.3, with
for
to conclude that
$\sigma \,g_0\equiv _G c $
for all
$\sigma \in \Sigma $
. Now, let
$\bar {g}$
be a coheir sequence as in Theorem 5.1, and assume the notation thereof. As
then
$ c \cdot _G g_0 = g_0\cdot _G c = (g_0)_G$
. Hence
$ h\equiv _Gg_0$
for all i and all
. In particular all these h have the same color, say color
$1$
. Now, we can use the sequence
$\bar {g}$
to define
$\bar a\in (G\smallsetminus C)^\omega $
such that all elements of
${\text {fp}}^\Sigma \,\bar a\smallsetminus C$
have color
$1$
by reasoning as in the proof of Theorem 5.1.
Carlson’s theorem is a result that combines the theorems of Hindman and Hales–Jewett and has a number of important consequences. We refer the reader to [Reference Dodos and Kanellopoulos7] for a discussion of some of these consequences. The definitions in Example 1.1 will help matching the notation.
We first present a Koppelberg-style version of the theorem. It is obtained from the lemma above applying a suitable coding.
Carlson Theorem 7.2 (À la Koppelberg)
Let
$\Sigma $
be a finite set of retractions of G onto a nice subsemigroup C. Let
$\bar s\in (G\smallsetminus C)^\omega $
. Then for every finite coloring of G, there is an increasing sequence of positive integers
$\langle n_i:i<\omega \rangle $
and some
$a_i\in {\text {fp}}^{\Sigma }s_{\restriction \,[n_i,n_{i+1})}\smallsetminus C$
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus C$
is monochromatic.
Proof Let
$G_*$
be the free semigroup generated by the alphabet
$$ \begin{align*} \{\langle \sigma,g\rangle \ :\ \sigma\in\Sigma\cup\{\text{id}_G\},\ g\in G\smallsetminus C\}. \end{align*} $$
The semigroup
$C_*$
is defined as
$G_*$
, only
$\sigma $
is restricted to range over
$\Sigma $
. Clearly
$C_*$
is a nice subsemigroup of
$G_*$
. We associate to each
$\sigma \in \Sigma $
the endomorphism of
$G_*$
that substitutes
$\sigma $
for every occurrence of
$\text {id}_G$
in a word. These maps, which we denote by
$\sigma _*$
, are retractions of
$G_*$
onto
$C_*$
.
If
$g_*\in G_*$
has the form
$\langle \sigma _1,g_1\rangle \cdots \langle \sigma _n,g_n\rangle $
we call
$\sigma _1\,g_1\cdots \sigma _n\,g_n\in G$
the evaluation of
$g_*$
. We denote the evaluation by
${\textrm {eval}}(g_*)$
. As
$\tau \,\sigma =\sigma $
for every
$\tau ,\sigma \in \Sigma $
, we have that
${\textrm {eval}}(\sigma _*\,g_*)=\sigma \,{\textrm {eval}}(g_*)$
. The evaluation of
$g_*\in C_*$
belongs to C and, as C is nice, and the evaluation of
$g_*\in G_*\smallsetminus C_*$
belongs to
$G\smallsetminus C$
.
We color each element of
$G_*$
with the color of its evaluation.
We define the relation
on
$G_*$
. First, we need to define the well-formed elements of
$G_*$
. These are elements of the form
$\langle \sigma _1,s_{i_1}\rangle \cdots \langle \sigma _n,s_{i_n}\rangle $
for some
$i_1<\dots <i_n$
. Now, for
$h_*,g_*\in G_*$
we define
if one of the following holds:
-
1.
$h_*$
is not well-formed while
$g_*$
is; -
2. the product (i.e., concatenation)
$h_*g_*$
is well-formed.
It is immediate to verify that
is
$G_*$
is -closed and
-covered by
$G_*\smallsetminus C_*$
. Therefore by Lemma 7.1 there is a
-chain
$\bar a_*\in (G_*\smallsetminus C_*)^\omega $
such that
${\text {fp}}^{\Sigma }\bar a_*\smallsetminus C_*$
is monochromatic. We can assume that all elements of
$\bar a_*$
are well-formed (only the first element might be ill-formed, but we can drop it). Then the sequence
$ \langle {\textrm {eval}}( a_{i*}) :i\in \omega \rangle $
is as required by the lemma.
From the algebraic version of Carlson’s theorem we obtain the classical one in the same way as for the Hales–Jewett theorem (Theorem 6.5), which we refer to for the notation.
Corollary 7.3 (Carlson’s theorem, classical version)
Let C be a semigroup generated by some finite set A. Let x be a variable. Let
$\bar s\in \big (C[x]\smallsetminus C\big )^\omega $
. Let
$\Sigma $
contain, for every
$a\in A$
, the function
$w(x)\mapsto w(a)$
. Then, for every finite coloring of
$C[x]$
, there is an increasing sequence of positive integers
$\langle n_i:i<\omega \rangle $
and some
$a_i\in {\text {fp}}^{\Sigma }s_{\restriction \,[n_i,n_{i+1})}\smallsetminus C$
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus C$
is monochromatic
$($
with the terminology of Example 1.1,
$\bar a$
is an extracted variable sequence of
$\bar s)$
.
8 Gowers’ partition theorem
The following is similar to Lemma 7.1 but here
$\Sigma $
contains compositions of homomorphisms.
Lemma 8.1. For
$0<i<n$
, let
$G_i$
be a nice subsemigroup of
$G_{i+1}$
and let
$\sigma _i:G_{i+1}\to G_i$
be homomorphisms. Let
be a relation on
$G_n$
that makes it -closed and
-covered by
$G_n\smallsetminus G_{n-1}$
. Finally, let
$\Sigma =\big \{\sigma _i\circ \dots \circ \sigma _{n-1}: 0< i< n\big \}$
. Then, for every finite coloring of
$G_n$
, there is a
-chain
$\bar a\in \big (G_n\smallsetminus G_{n-1}\big )^\omega $
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus G_{n-1}$
is monochromatic.
Proof For convenience, we let i run from
$0$
, hence we agree that
$\sigma _0:G_1\to G_0=G_1$
is the identity. Let
and
. Note that the
are non-empty because
$G_n$
is
-covered by
$G_n\smallsetminus G_{n-1}$
. Also, as
is a nice subsemigroup of
, we have that
.
We claim there is some
with idempotent orbit such that, if we define
$ b_i=\sigma _i\, b_{i+1}$
for
$0\le i< n$
, the following holds:
$$ \begin{align*} b_n\cdot_G b_i \ =\ b_i\cdot_G b_n \ =\ ( b_n)_G. \end{align*} $$
Note that these equalities may be replaced by
$$ \begin{align*} b_i\cdot_G b_{i+1} \ =\ b_{i+1}\cdot_G b_i \ =\ ( b_{i+1})_G. \tag{$\sharp_i$}\end{align*} $$
Let
$ b_0= b_1$
be any element of
with idempotent orbit. We assume as induction hypothesis that we have
for
$i\le k$
, with idempotent orbits, such that
$ b_i=\sigma _i\, b_{i+1}$
and
$\sharp _i$
hold for all
$i<k$
. We show how to find
$ b_{k+1}$
.
We prove that
$ b_k$
and the set
, which below we denote by
for short, satisfy the assumptions of Proposition 6.2. The proof of the idempotency of
is left to the reader. We prove that
, the proof of
is similar. As
by nicety, it suffices to prove that
$ b_k\cdot _G\sigma _k^{-1}[ b_k]$
is contained in
$\sigma _k^{-1}[ b_k]$
. This latter inclusion holds because, by the induction hypothesis,
$$ \begin{align*}\sigma_k\Big[ b_k\cdot_G\sigma_k^{-1}[ b_k]\Big] \ =\ \sigma_k[ b_k]\cdot_G b_k \ =\ b_{k-1}\cdot_G b_k \ =\ ( b_k)_G.\end{align*} $$
Now we apply Proposition 6.2 to find an idempotent
. Therefore
$\sharp _k$
is satisfied. Moreover
$\sigma _k\, b_{k+1}\in ( b_k)_G$
by Proposition 6.3, hence we can assume
$ b_k=\sigma _k\, b_{k+1}$
as claimed above.
Finally, as in the proof of Theorem 5.1, the required chain
$\bar a$
is obtained from a coheir sequence of a global coheir of
$\text {tp}( b_n/G)$
.
Remark 8.2. The lemma above continues to hold, with essentially the same proof, if for
$\Sigma $
we take a set of the form
$$ \begin{align*}\displaystyle\Sigma\ =\ \bigcup^{n-1}_{i=1}\ \Sigma_i\circ\dots\circ\Sigma_{n-1}, \end{align*} $$
where
$$ \begin{align*}\Sigma_i\circ\dots\circ\Sigma_{n-1}\ =\ \{\sigma_i\circ\dots\circ\sigma_{n-1}\ :\ \sigma_i\in\Sigma_i,\dots,\sigma_{n-1}\in\Sigma_{n-1}\}, \end{align*} $$
and where
$\Sigma _i$
are some finite sets of homomorphisms
$G_{i+1}\to G_i$
such that for every
$g\in G_i$
the set
$\Sigma _i^{-1}[g]$
is non-empty.
Let
$G_i$
be the set of functions
$a:\omega \to \{0,\dots ,i\}$
with finite support that is, the set
$\mathop {\text {supp}}(a)$
$=\{x\in \omega \,:\,a\,x\neq 0\}$
is finite. We introduce a semigroup operation on
$G_i$
by defining
$(a{\cdot }b)\,x=\max \{ax,bx\}$
. This makes
$G_i$
a nice subsemigroup of
$G_{i+1}$
.
Corollary 8.3 (Gowers’ partition theorem)
With
$G_i$
as above, let
$\sigma _i:G_{i+1}\to G_i$
be homomorphisms and let
$\Sigma $
be as in Lemma 8.1. Then for every finite coloring of
$G_n$
there is an
$\bar a\in \big (G_n\smallsetminus G_{n-1}\big )^\omega $
such that
${\text {fp}}^{\Sigma }\bar a\smallsetminus G_{n-1}$
is monochromatic and
$\mathop {\mathrm {supp}}(a_i)<\mathop {\mathrm {supp}}(a_{i+1})$
.
The homomorphisms
$\sigma _i$
usually considered in the literature are so-called tetris operations, i.e.,
$(\sigma _i\,a)x=\max \{a\,x-1,\ 0\}$
, or generalizations thereof. However the theorem is more general.
Proof Let
be the relation
$\mathop {\text {supp}}(a)<\mathop {\text {supp}}(b)$
and apply Theorem 8.1.
Acknowledgments
The second author is grateful to Pierre Simon for suggesting the comparison with nonstandard analysis. Both authors would like to thank Vassilis Kanellopoulos for helpful conversation. This study was partially funded by GNSAGA.
