Ramsey Theory

I.B. Leader
Michaelmas 2000
1 Monochromatic Systems
1.1 Ramseys Theorem
We write N for the set 1, 2, 3, . . . of positive integers. For any positive
integer n, we write [n] = 1, 2, . . . , n. For any set X, we denote the set
A X : [A[ = r of subsets of X of size r by X
(r)
.
By a k-colouring of N
(r)
, we mean a map c: N
(r)
[k]. We say that a
set M N is monochromatic for c if c[
M
(r) is constant.
Theorem 1 (Ramseys Theorem). Whenever N
(2)
is 2-coloured, there
exists an innite monochromatic set.
Proof. Pick a
1
N. There are innitely many edges from a
1
, so we can nd
an innite set B
1
Na
1
such that all edges from a
1
to B
1
are the same
colour c
1
.
Now choose a
2
B
1
. There are innitely many edges from a
2
to points
in B
1
a
2
, so we can nd an innite set B
2
B
1
a
2
such that all
edges from a
2
to B
2
are the same colour, c
2
.
Continue inductively. We obtain a sequence a
1
, a
2
, a
3
, . . . of distinct
elements of N, and a sequence c
1
, c
2
, c
3
of colours such that the edge a
i
a
j
(i < j) has colour c
i
. Plainly we must have c
i
1
= c
i
2
= c
i
3
= for some
innite subsequence. Then a
i
1
, a
i
2
, a
i
3
, . . . is an innite monochromatic set.
The result follows.
Remarks. 1. The same proof shows that if N
(2)
is k-coloured then we get
an innite monochromatic set. Alternatively, we could view 1 and 2 or
3 or . . . or k as a 2-colouring of N
(2)
, and then apply Theorem 1 and use
induction on k.
2. An innite monochromatic set is much more than having arbitrarily
large nite monochromatic sets. For example, consider the colouring in which
1
all edges within each of the sets 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, . . . are coloured blue and all other edges are coloured
red. Here there is no innite blue monochromatic set, but there are arbitrar-
ily large nite monochromatic blue sets.
Example. Any sequence (x
n
)
nN
in a totally ordered set has a monotone
subsequence: colour N
(2)
by giving ij (i < j) colour UP if x
i
< x
j
and colour
DOWN otherwise; the result follows by Theorem 1.
Theorem 2. Whenever N
(r)
is 2-coloured, there exists an innite monochro-
matic set.
Proof. The proof is by induction on r, the case r = 1 being trivial.
Suppose the result holds for r 1. Given c: N
(r)
[2], pick a
1
N.
Dene a 2-colouring c

of (N a
1
)
(r1)
by c

(F) = c(F a
1
) for all
F (N a
1
)
(r1)
. By induction, there exists an innite monochromatic
set B
1
Na
1
for c

; i.e. there exists a colour c

1
such that c(F a
1
) = c
1
for all F B
(r1)
1
.
Now choose a
2
B
1
. In exactly the same way, we get an innite set
B
2
B
1
a
2
and a colour c
2
such that c(F a
2
) = c
2
for all F B
(r1)
2
.
Continue inductively: we obtain a sequence a
1
, a
2
, a
3
, . . . of distinct ele-
ments of N and colours c
1
, c
2
, c
3
, . . . such that for any i
1
< i
2
< < i
r
we
have c(a
i
1
, a
i
2
, . . . , a
i
r
) = c
i
1
. But we must have c
i
1
= c
i
2
= c
i
3
= for
some innite subsequence. Then a
i
1
, a
i
2
, a
i
3
, . . . is an innite monochro-
matic set. The result follows.
Example. We saw that, given any (1, x
1
), (2, x
2
), (3, x
3
), . . . in R
2
we could
pick a subsequence inducing a monotone function. In fact we can insist
that the induced function is convex or concave: colour N
(3)
by giving ijk
(i < j < k) the colour convex or concave according as the corresponding
points form a convex or concave triple. The result follows by Theorem 2.
We can deduce the nite form of Ramseys Theorem from Theorem 2.
Corollary 3. Let m, r N. Then there exists n N such that whenever
[n]
(r)
is 2-coloured there is a monochromatic set M [n]
(m)
.
Proof. Suppose not. We construct a 2-colouring of N
(r)
without a monochro-
matic m-set, contradicting Theorem 2.
For each n r, we have a colouring c
n
: [n]
(r)
[2] with no monochro-
matic m-set. There are only nitely many ways to colour [r]
(r)
(two in fact) so
innitely many of c
r
[[r]
(r)
, c
r+1
[[r]
(r)
, c
r+2
[[r]
(r)
, . . . agree; say c
i
[[r]
(r)
= d
r
for
all i lying in some innite set A
1
, where d
r
is some colouring of [r]
(r)
. Among
2
the c
i
for i A
1
, innitely many must agree on [r+1]
(r)
; say c
i
[[r+1]
(r)
= d
r+1
for all i A
2
, where d
r+1
: [r + 1]
(r)
[2] and A
2
A
1
is innite.
Continue inductively: we obtain colourings d
n
: [n]
(r)
[2] for n = r,
r + 1, r + 2, . . . such that
(i) no d
n
has a monochromatic m-set (as there is some k such that
d
n
= c
k
[[n]
(r)
); and
(ii) for all n, d
n+1
[[n]
(r)
= d
n
.
Dene a colouring c: N
(r)
[2] by c(F) = d
n
(F) for any n max F. This
is well-dened by (ii), and has no monochromatic m-set by (i). So we have
our contradiction. The result follows.
Remarks. 1. This proof gives no information about the minimal possible
n(m, r). There are direct proofs which give upper bounds.
2. The above is a compactness proof: what we did was (essentially) show
that 0, 1
N
with the product topology (i.e. the topology derived from the
metric d(f, g) = 1/ minn : f(n) = g(n)) is compact.
Theorem 4 (The Canonical Ramsey Theorem). Whenever we have a
colouring of N
(2)
with an arbitrary set of colours, there exists an inginite set
M such that
(i) c is constant on M
(2)
; or
(ii) c is injective on M
(2)
; or
(iii) c(ij) = c(kl) i i = k (for all i, j, k, l M with i < j and k < l);
or
(iv) c(ij) = c(kl) i j = l (for all i, j, k, l M with i < j and k < l).
Note that this theorem implies Theorem 1: if we have only a nite set of
colours then (ii), (iii) and (iv) are impossible.
Proof. First 2-colour N
(4)
by giving ijkl (by which we mean henceforth
i < j < k < l) colour YES if c(ij) = c(kl) and colour NO if c(ij) = c(kl).
By Ramsey for 4-sets, we have an innite monochromatic set M. If M is
coloured YES then M is monochromatic for c (for given any ij and kl in M
(2)
,
choose any m < n in M with m > i, j, k, l; then c(ij) = c(mn) = c(kl).) So
in this case (i) holds.
Suppose then that M is coloured NO. Now 2-colour M
(4)
by giving ijkl
colour YES if c(il) = c(jk) and colour NO if c(il) = c(jk). Again by
3
Ramsey, there exists an innite M

M monochromatic for this colour-

ing. If M

is YES, choose x
1
< x
2
< x
3
< x
4
< x
5
< x
6
in M

; then
c(x
2
x
3
) = c(x
1
x
6
) = c(x
4
x
5
), a contradiction.
So M

is colour NO. Now 2-colour M

(4)
by giving ijkl colour YES if
c(ik) = c(jl) and colour NO is c(ik) = c(jl). By Ramsey, we have an
innite monochromatic set M

. If M

is colour YES then choose

x
1
< x
2
< x
3
< x
4
< x
5
< x
6
in M

; then c(x
1
x
3
) = c(x
2
x
5
) = c(x
4
x
6
), a
contradiction.
So M

is colour NO. Now 2-colour M

(3)
by giving ijk colour LEFT-
SAME if c(ij) = c(ik) and colour LEFT-DIFF if c(ij) = c(ik). We get an
innite M

monochromatic for this colouring. Then 2-colour M

(3)
by giving ijk colour RIGHT-SAME if c(ik) = c(jk) and colour RIGHT-DIFF
if c(ik) = c(jk). We get an innite monochromatic M

. Finally, 2-
colour M
(3)
by giving ijk colour MID-SAME if c(ij) = c(jk) and colour
MID-DIFF if c(ij) = c(jk). We get an innite monochromatic M

.
If M

is colour MID-SAME, choose x

1
< x
2
< x
3
< x
4
in M

; then
c(x
1
x
2
) = c(x
2
x
3
) = c(x
3
x
4
), a contradiction. So M

is MID-DIFF.
If M

is LEFT-SAME and RIGHT-SAME then it would also be MID-

SAME, a contradiction.
If M

is LEFT-SAME and RIGHT-DIFF then (iii) holds.

If M

is LEFT-DIFF and RIGHT-SAME then (iv) holds.

If M

is LEFT-DIFF and RIGHT-DIFF then (ii) holds.

Remark. We could do it all in one colouring of N
(4)
by colouring x
1
x
2
x
3
x
4
with the partition of [4]
(2)
induced by c on x
1
, x
2
, x
3
, x
4
. The number of
colours would be the number of partitions of a set of size

4
2

. In the same
way, we can show that if we arbitrarily colour N
(r)
we get an innite M N
and a set I [r] such that for any x
1
, x
2
, . . . , x
r
, y
1
, y
2
, . . . , y
r
M
(r)
we
have
c(x
1
, x
2
, . . . , x
r
) = c(y
1
, y
2
, . . . , y
r
) x
i
= y
i
for all i I.
So in Theorem 4, I = is (i), I = 1, 2 is (ii), I = 1 is (iii) and I = 2
is (iv). These 2
r
colourings are called the canonical colourings of N
(r)
.
1.2 Van der Waerdens Theorem
In this theorem we shall show:
whenever N is 2-coloured, for all m N there exists a monochro-
matic arithmetic progression of length m (i.e. a, a + d, a + 2d,
. . . , a + (m1)d all the same colour).
4
By the familiar compactness argument, this is the same as:
for all m N, there exists n N such that whenever [n] is 2-
coloured, there exists a monochromatic arithmetic progression of
length m.
In our proof (of the second form above), we use the following key idea: we
show more generally that for all k, m N, there exists n such that when-
ever [n] is k-coloured, there exists a monochromatic arithmetic progression
of length m. We write W(m, k) for the smallest n if it exists. Note that
proving a more general result by induction can actually be easier, because
the induction hypothesis is correspondingly stronger.
Another idea we use is the following: let A
1
, A
2
, . . . , A
r
be arithmetic
progressions of length lsay A
i
= a
i
, a
i
+ d
i
, . . . , a
i
+ (l 1)d
i
. We say
that A
1
, A
2
, . . . , A
r
are focussed at f if a
i
+ ld
i
= f for all i; for example,
1, 4 and 5, 6 are focussed at 7. If in addition each A
i
is monochromatic
and no two are the same colour then we say that they are colour-focussed at
f (for the given colouring).
Proposition 5. Let k N. Then there exists n N such that whenever [n]
is k-coloured, there exists a monochromatic arithmetic progression of length
3.
Proof. We make the following claim:
For all r k, there exists n such that whenever [n] is k-coloured,
EITHER there exists a monochromatic arithmetic progression of
length 3 OR there exist r colour-focussed arithmetic progressions
of length 2.
The result will follow immediately from this claimjust take r = k; then
whatever colour the focus is, we get a monochromatic arithmetic progression
of length 3.
We prove the claim by induction on r. Note that the case r = 1 is trivial
we may simply take n = k + 1. So assume that we are given n suitable for
r 1; we will show that (k
2n
+ 1)2n is suitable for r.
Given a k-colouring of [(k
2n
+ 1)2n] not containing a monochromatic
arithmetic progression of length 3, break up [(k
2n
+1)2n] into blocks of length
2n, namely B
i
= [2n(i 1) + 1, 2ni] for i = 1, 2, . . . , k
2n
+ 1. Inside each
block, there are r 1 colour-focussed arithmetic progressions of length 2 (by
our choice of n), together with their focus (as the length of each block is 2n).
Now there are k
2n
possible ways to colour a block, so some two blocks, say B
s
and B
s+t
, are coloured identically. Say B
s
contains a
i
, a
i
+d
i
, 1 i r1,
5
colour-focussed at f. Then B
s+t
contains a
i
+2nt, a
i
+d
i
+2nt, 1 i r1,
colour-focussed at f + 2nt, with corresponding colours the same. But now
a
i
, a
i
+d
i
+2nt, 1 i r 1, are arithmetic progressions colour-focussed
at f + 4nt. Also, f, f + 2nt is monochromatic of a dierent colour; so we
have r arithmetic progressions of length 2 colour-focussed at f + 4nt. This
completes the induction; the claim, and hence the result, follow.
Remarks. 1. The idea of looking at the number of ways to colour a block is
called a product argument.
2. The above proof gives W(3, k) k
k
k

k
4k

(k1)
, a tower-type bound.
Theorem 6 (Van der Waerdens Theorem). Let m, k N. Then there
exists n N such that whenever [n] is k-coloured, there exists a monochro-
matic arithmetic progression of length m.
Proof. The proof is by induction on m. The case m = 1 is trivial (for all k).
Now given m, we can assume as our induction hypothesis that W(m1, k)
exists for all k. We make the following claim:
For all r k, there exists n such that whenever [n] is k-coloured,
there exists either a monochromatic arithmetic progression of
length m or r colour-focussed arithmetic progressions of length
m1.
The result will follow immediately from this claimjust put r = k and look
at the focus.
The proof of the claim is by induction on r. For r = 1 we may simply
take n = W(m 1, k). So suppose r > 1. If n is suitable for r 1, we will
show that W(m1, k
2n
)2n is suitable for r.
Given a k-colouring of [W(m1, k
2n
)2n] with no monochromatic arith-
metic progression of length m, we can break up [W(m 1, k
2n
)2n] into
W(m 1, k
2n
) blocks of length 2n, namely B
1
, B
2
, . . . , B
W(m1,k
2n
)
where
B
i
= [2n(i 1) + 1, 2ni]. By denition of W(m1, k
2n
), we can nd blocks
B
s
, B
s+t
, . . . , B
s+(m2)t
identically coloured.
Now B
s
contains r 1 colour-focussed arithmetic progressions of length
m 1, together with their focus, say A
1
, A
2
, . . . , A
r1
colour-focussed at
f, where A
i
= a
i
, a
i
+d
i
, . . . , a
i
+ (m2)d
i
. Now look at the arithmetic
progression A

i
= a
i
, a
i
+ (d
i
+ 2nt), . . . , a
i
+ (m2)(d
i
+ 2nt) for i = 1,
2, . . . , r 1. Then A

1
, A

2
, . . . , A

r1
are colour-focussed at f + (m1)2nt.
But f, f +2nt, . . . , f +(m2)2nt is monochromatic and a dierent colour.
This completes the induction. The claim, and hence the result, follow.
6
We dene the Ackermann (or Grzegorczyk) hierarchy to be the sequence
of functions f
1
, f
2
, . . . : N N dened by
f
1
(x) = 2x
f
n+1
(x) = f
(x)
n
(1) (n 1),
so
f
2
(x) = 2
x
,
f
3
(x) = 2
2
2

x
,
f
4
(1) = 2, f
4
(2) = 2
2
= 4, f
4
(3) = 2
2
2
2
= 65536, . . . .
We say that a function f : N N is of type n if there exist c and d with
f(cx) f
n
(x) f(dx) for all x. Our proof above gives a bound of type m
on W(m, k), so our bound on W(m) = W(m, 2) grows faster than f
n
for
all nthis is often a feature of such double inductions. Shelah showed that
W(m, k) f
4
(m+k). Gowers showed that W(m) 2
2
2
2
2
2
2
m
. The best lower
bound known is W(m) 2
m
/8m.
Corollary 7. Whenever N is k-coloured, some colour class contains arbi-
trarily long arithmetic progressions.
Remark. We cannot guarantee an innitely long arithmetic progression. Ei-
ther
(i) colour N by colouring 1 red, then 2 and 3 blue, then 4, 5 and 6 red
then 7, 8, 9 and 10 blue, and so on; or
(ii) enumerate the innitely long arithmetic progressions as A
1
, A
2
, A
3
, . . .
(noting that there are only countably many). Choose x
i
, y
i
A
i
with
x
i
= y
i
for all i and x
i
, y
i
< x
i+1
, y
i+1
. Colour each x
i
red and each y
i
blue.
Theorem 8 (Strengthened Van der Waerden). Let m, k N. When-
ever N is k-coloured, there is an arithmetic progression of length m that, to-
gether with its common dierence, is monochromatic(i.e. there exist a, a+d,
a + 2d, . . . , a + (n 1)d and d all the same colour).
Proof. The proof is by induction on k; the case k = 1 is trivial.
Given n suitable for k 1 (i.e. such that whenever [n] is (k 1)-coloured
there exists a monochromatic arithmetic-progression-with-common-dierence
of length n), we will show that W(n(m 1) + k) is suitable for k. Indeed,
7
given a k-colouring of [W(n(m 1) + 1, k)], there exists a monochromatic
arithmetic progression of length n(m 1) + 1, say a, a + d, a + 2d, . . . ,
a + n(m 1)d. If d or 2d or . . . or nd is the same colour as this arithmetic
progression we are done. If not, we have d, 2d, . . . , nd (k 1)-coloured, so
we are done by induction.
Remark. The case m = 2 is known as Schurs Theorem: whenever N is
k-coloured, we can solve x + y = z in one colour class. We can also prove
Schurs Theorem from Ramseys Theorem: given a k-colouring c of N, de-
ne a k-colouring c

of [n]
(2)
(n large) by c

(ij) = c([j i[). By Ramsey,

there exists a monochromatic triangle; i.e. there exist u < v < w with
c

(uv) = c

(vw) = c

(wu). So c(v u) = c(w v) = c(w u), and since

(v u) + (w v) = (w u) we are done.
1.3 The Hales-Jewett Theorem
Let X be a nite set. A subset L of X
n
(the n-dimensional cube on alphabet
X) is called a line (or combinatorial line) if there exists a non-empty set
I = i
1
, i
2
, . . . , i
r
[n] and a
i
X for each i I such that
L = x X
n
: x
i
= a
i
for i I and x
i
1
= x
i
2
= = x
i
r
.
We call I the set of active coordinates for L. For example, in [3]
2
the lines
are:
(1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2), and (1, 3), (2, 3), (3, 3) with
I = 1;
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3) and (3, 1), (3, 2), (3, 3) with
I = 2; and
(1, 1), (2, 2), (3, 3) with I = 1, 2.
Note that the denition of a line does not depend on the ground set X.
Theorem 9 (The Hales-Jewett Theorem). Let m, k N. Then there
exists n N such that whenever [m]
n
is k-coloured there exists a monochro-
matic line.
Remarks. 1. The smallest such n is denoted by HJ(m, k).
2. The Hales-Jewett Theorem implies Van der Waerdens Theorem
we need only embed a Hales-Jewett cube of suciently high dimension lin-
early into N, and so that the embedding is injective on lines. For exam-
ple, given a k-colouring c of N, induce a k-colouring c

of [m]
n
(n large)
8
by c

((x
1
, x
2
, . . . , x
n
)) = c(x
1
+ x
2
+ + x
n
). By Hales-Jewett, there is
a monochromatic line, and this corresponds to a monochromatic arithmetic
progression of length m in N. So we should regard the Hales-Jewett theorem
as an abstract version of Van der Waerdens Theorem.
If L is a line in [m]
n
write L

and L
+
for its rst and last points (in the
ordering on [m]
n
given by x y if x
i
y
i
for all i). Lines L
1
, L
2
, . . . , L
k
are focussed at f if L
+
i
= f for all i. They are colour-focussed (for a given
colouring) if in addition each L
i
L
+
i
is monochromatic, no two the same
colour.
Proof (of Theorem 9). By induction on m; the case m = 1 is trivial.
Given m > 1, we may assume that HJ(m 1, k) exists for all k. We
make the following claim:
For all r k, there exists n such that whenever [m]
n
is k-coloured,
there exists EITHER a monochromatic line OR r colour-focussed
lines.
The result will follow immediately from this claimput r = k and look at
the focus.
The proof of the claim is by induction on r. For r = 1 we may take
n = HJ(m1, k).
Given n suitable for r, we shall show that n+HJ(m1, k
m
n
) is suitable
for r + 1. Write n

= HJ(m1, k
m
n
).
Given a k-colouring of [m]
n+n

with no monochromatic line, identify m

n+n

with [m]
n
[m]
n

. There are k
m
n
ways to colour a copy of [m]
n
. So by our
choice of n

, we have a line L in [m]

n

, say with active coordinate set I, such

that for all a [m]
n
and all b, b

LL
+
, we have c(a, b) = c(a, b

) = c

(a),
say. Now by denition of n, there exist r colour-focussed lines for c

, say L
1
,
L
2
, . . . , L
r
, with acrive coordinate sets I
1
, I
2
, . . . , I
r
respectively, and focus f.
But now let L

i
be the line through the point (L

i
, L

) with active coordinate

set I
i
I (i = 1, 2, . . . , r). Then L

1
, L

2
, . . . , L

r
are colour-focussed at
(f, L
+
). And the line through (f, L

) with active coordinate set I gives us

r + 1 colour-focussed lines. Thus our induction is complete and the claim,
and hence the result, follow.
A d-dimensional subspace or d-parameter set S in X
n
is a set of the
following form: there exist disjoint non-empty sets I
1
, I
2
, . . . , I
d
[n] and
a
i
X for each i [n] (I
1
I
2
I
d
) such that
S =

x X
n
:
x
i
= a
i
for all i [n] (I
1
I
2
I
d
)
x
i
= x
j
whenever i, j I
l
for some l

.
9
For example in X
3
, (a, b, 2) : a, b X and (a, a, b) : a, b X are 2-
parameter sets.
Theorem 10 (The Extended Hales-Jewett Theorem). Let m, k, d N.
Then there exists n N such that whenever [m]
n
is k-coloured, there exists
a monochromatic d-parameter set.
Proof. Regard X
dn
as (X
d
)
n
a cube on alphabet X
d
. Clearly any line in
this (on alphabet X
d
) is a d-parameter set on alphabet X, so we can take
n = dHJ(n
d
, k).
1.4 Gallais Theorem
Let S N
d
be a nite set. A homothetic copy of S is any set of the form
a + S where a N
d
and N. For example, in N
1
, a homothetic copy of
1, 2, . . . , m is precisely an arithmetic progression of length m.
Theorem 11 (Gallais Theorem). For any nite S N
d
and any k-
colouring of N
d
, there exists a monochromatic homothetic copy of S.
Proof. Let S = S(1), S(2), . . . , S(m). Given a k-colouring c of N
d
, dene
a k-colouring c

of [m]
n
(n large) by c

(x) = c(

i
S(x
i
)). By Hales-Jewett,
there is a monochromatic line, giving a monochromatic homothetic copy of
S (with the number of active coordinates).
Remarks. 1. Or by a product argument and focussing.
2. For S = (x, y) : x, y 0, 1, Gallais Theorem tells us that there
exists a monochromatic square. Could we have used 2-parameter Hales-
Jewett instead?No, this would only give us a rectangle.
2 Partition Regular Equations
2.1 Partition Regularity
Let A be an mn matrix with rational entries. We say that A is partition
regular (PR) (over N) if whenever N is nitely coloured, there is always a
monochromatic x N
n
with Ax = 0.
Examples. 1. Schur states that the matrix (1 1 1) is PR.
10
2. Strengthened Van der Waerden states that the matrix

1 1 1 0 . . . 0
1 2 0 1 . . . 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 m 0 0 . . . 1

is PR.
We also talk about the equation Ax = 0 being PR.
Not every matrix is PR: for example, (2 1) is not PR; for we can 2-
colour x N by the parity of maxi : 2
i
[x. Note that A is PR if and only if
A is PR for any Q0, so we could restrict our attention to integer
matrices if we wished.
Let A have columns c
(1)
, c
(2)
, . . . , c
(n)
Q
m
, so
A =

c
(1)
c
(2)
. . . c
(n)

.
We say that A has the columns property if there is a partition B
1
B
2
B
r
of [n] such that
(i)

iB
1
c
(i)
= 0; and
(ii)

iB
s
c
(i)

c
(j)
: j B
1
B
2
B
s1

for s = 2, 3, . . . , r
where '` denotes linear span over R. (Note that we could have equally said
over Q here: if a rational vector is a real linear combination of some rational
vectors then it is also a rational combination of them.)
Examples. 1. The matrix (1 1 1) has the columns property: take B
1
= 1, 3
and B
2
= 2.
2. The matrix

1 1 3
2 2 a
4 4 b

has the columns property if and only if (a, b) = (6, 12).

3. The matrix A = (a
1
a
2
. . . a
n
) has the columns property if and only if
either A = 0 or some non-empty subset of the non-zero a
i
sums to zero.
We shall prove:
11
Rados Theorem. A rational matrix A is PR if and only if A has the
columns property.
One strength of this result is that it shows that partition regularity, which
does not at rst appear to be checkable in nite time, in fact is checkable in
nite time.
First we show that Rados Theorem is true for one equation. We may
assume without loss of generality that a
1
, a
2
, . . . , a
n
= 0; then we must show
(a
1
a
2
. . . a
n
) is PR

iI
a
i
= 0 for some non-empty I [n].
Let p be prime. For x N, let d
p
(x) be the last non-zero digit in the base
p expansion of x, i.e. if x = d
r
p
r
+ d
r1
p
r1
+ + d
1
p + d
0
, 0 d
i
p 1
for all i, then d
p
(x) = d
L(x)
where L(x) = mini : d
i
= 0. For example, if
x = 1002047000 in base p then L(x) = 3 and d
p
(x) = 7.
Proposition 12. Let a
1
, a
2
, . . . , a
n
be non-zero rationals such that the
matrix (a
1
a
2
. . . a
n
) is PR. Then

iI
a
i
= 0 for some non-empty I [n].
Proof. We may assume without loss of generality that a
1
, a
2
, . . . , a
n
Z. Fix
a prime p with p >

n
i=1
[a
i
[, and dene a (p 1)-colouring of N by giving
x the colour d
p
(x). We know that

iI
a
i
x
i
= 0 for some x
1
, x
2
, . . . , x
n
all of the same colour, d, say. Let L = minL(x
i
) : 1 i n and let
I = i : L(x
i
) = L. Considering

iI
a
i
x
i
= 0 performed in base p, we
have

iI
da
i
0 (mod p) and so

iI
a
i
0 (mod p). But p >

n
i=1
[a
i
[
and so

iI
a
i
= 0.
Remark. Or: for each prime p we get a set I with

iI
a
i
0 (mod p),
so some xed set I has

iI
a
i
0 (mod p) for innitely many p, whence

iI
a
i
= 0.
Lemma 13. Let Q. Then whenever N is nitely coloured, there exist
monochromatic x, y and z with x +y = z.
Proof. (cf the proof of Theorem 8.) If = 0 we are done; if < 0 we may
rewrite our equation as z y = x. So we may assume without loss of
generality that > 0; say = r/s with r, s N.
So we need to prove that for all k, there exists an n such that, whenever
[n] is k-coloured, there exist monochromatic x, y and z with x +(r/s)y = z.
We shall prove this by induction on k.
For k = 1, take n = maxs, r + 1 and (x, y, z) = (1, s, r + 1).
Suppose k > 1. Given n suitable for k1, we shall show that W(nr+1, k)
is suitable for k. Indeed, given a k-colouring of [W(nr + 1, k)] we have
12
a monochromatic arithmetic progression of length nr + 1, say a, a + d, . . . ,
a+nrd, all of colour c. Look at ds, 2ds, . . . , nds. If, say, ids has colour c then
we are done, as a+(r/s)ids = a+idr and (a, ids, a+idr) is a monochromatic
triple with colour c. So we may assume the set ds, 2ds, . . . , nds is (k 1)-
coloured, and we are done by induction. The claim, and hence the result,
follow.
Theorem 14 (Rados Theorem for single equations). Let a
1
, a
2
, . . . , a
n
be non-zero rationals. Then (a
1
a
2
. . . a
n
) is PR if and only in

iI
a
i
= 0
for some non-empty I [n].
Proof. is Proposition 12.
Given a nite colouring of N, x i
0
I. For suitable monochromatic
x, y and z, we shall set
x
i
=

x if i = i
0
y if i I
z if i I i
0

.
We require that

a
i
x
i
= 0, i.e. that
a
i
0
x +

iI{i
0
}
a
i

z +

iI
a
i

y = 0,
i.e.
a
i
0
x a
i
0
z +

iI
a
i

y = 0,
i.e.
x +

iI
a
i

a
i
0
y z = 0,
and such x, y and z do indeed exist by Lemma 13.
Proposition 15. Let A be any matrix with entries in Q. If A is PR then it
must have the columns property.
Proof. We may assume without loss of generality that all the entries of A
are integers. Let the columns of A be c
(1)
, c
(2)
, . . . , c
(n)
. For any prime p,
colour N with the d
p
colouring. By assumption, there exists a monochromatic
x Z
n
with Ax = 0, i.e. x
1
c
(1)
+ x
2
c
(2)
+ + x
n
c
(n)
= 0. Say all the x
i
have colour d.
13
We have a partition B
1
B
2
B
r
of [n] given by
L(x
i
) = L(x
j
) = i, j B
s
for some s;
L(x
i
) < L(x
j
) = i B
s
, j B
t
for some s < t.
For innitely many primes p, say all p P, we get the same B
1
, B
2
, . . . , B
r
.
Considering

x
i
c
(i)
= 0 performed in base p, we have
(i)

iB
1
dc
(i)
0 (mod p), where by u v (mod p) with u, v Z
n
we mean u
j
v
j
(mod p) for all j; and
(ii) for all s 2,

iB
s
p
t
dc
(i)
+

iB
1
B
s1
x
i
c
(i)
0 (mod p
t+1
) for
some t.
From (i), and as d is invertible, we have

iB
1
c
(i)
0 (mod p) for
innitely many p, and so

iB
1
c
(i)
= 0.
From (ii), for all s 2 we have
p
t

iB
s
c
(i)
+

iB
1
B
s1
y
i
c
(i)
0 (mod p
t+1
)
(where y
i
= d
1
x
i
(mod p
t+1
)).
We now show that

iB
s
c
(i)
'c
(i)
: i B
1
B
2
B
s1
`. Suppose
not. Then there exists u Z
m
with u c
(i)
= 0 for all i B
1
B
2
B
s1
but with u (

iB
s
c
(i)
) = 0. So p
t
u (

iB
s
c
(i)
) 0 (mod p
t+1
), i.e.
u (

iB
s
c
(i)
) 0 (mod p) for innitely many p, a contradiction.
Let m, p, c N. A set S N is an (m, p, c)-set with generators
x
1
, x
2
, . . . , x
m
N if
S =

i=1

i
x
i
: j with
i
= 0 i < j,
j
= c,
i
p, p+1, . . . , p i > j

.
So S consists of all numbers in the lists:
cx
1
+
2
x
2
+
3
x
3
+ +
m
x
m
([
i
[ p i 2)
cx
2
+
3
x
3
+ +
m
x
m
([
i
[ p i 3)
.
.
.
cx
m1
+
m
x
m
([
m
[ p)
cx
m
.
Examples. 1. A (2, p, 1)-set is an arithmetic progression of length 2p + 1
together with its common dierence.
2. A (2, 2, 3)-set is an arithmetic progression of length 5, with middle
term divisible by 3, together with thrice its common dierence.
14
Theorem 16. Let m, p, c N and suppose N is nitely coloured. Then
there exists a monochromatic (m, p, c)-set.
Proof. Let = k(m1) + 1.
Given a k-colouring of B
0
= [n] with n large, look at
A
1
=

c, 2c, . . . ,

n
c

1
.
By Van der Waerden, there is a monochromatic arithmetic progression inside
A, say
P
1
= cx
1
n
1
d
1
, cx
1
(n
1
1)d
1
, . . . , cx
1
, . . . , cx
1
+n
1
d
1

where n
1
is large and P
1
has colour k
1
, say. Now we restrict attention to
B
1
=

d
1
, 2d
1
, . . . ,
n
1
( 1)p
d
1

.
Note that for any integers
2
,
3
, . . . ,

[p, p] and b
2
, b
3
, . . . , b

B
1
,
we have
cx
1
+
2
b
2
+
3
b
3
+ +

P
1
,
so in particular all sums of this form have colour k
1
.
Now look at
A
2
=

cd
1
, 2cd
1
, . . . ,
n
1
( 1)pc
d
1

.
By Van der Waerden, there is a monochromatic arithmetic progression inside
A
2
, say
P
2
= cx
2
n
2
d
2
, cx
2
(n
2
1)d
2
, . . . , cx
2
, . . . , cx
2
+n
2
d
2
,
where n
2
is large and P
2
has colour k
2
, say. Now we restrict attention to
B
2
=

d
2
, 2d
2
, . . . ,
n
2
( 2)p
d
2

.
Note that for any integers
3
,
4
, . . . ,

[p, p], and b

3
, b
4
, . . . , b

B
2
,
we have
cx
2
+
3
b
3
+
4
b
4
+ +

P
2
,
so in particular all sums of this form have colour k
2
.
1
Henceforth we shall omit the symbols and | in expressions such as this; they
should be understood where necessary.
15
Now look at A
3
= . . . .
Keep going times: we obtain x
1
, x
2
, . . . , x

such that each row of

the (, p, c)-set generated by x
1
, x
2
, . . . , x

is monochromatic. But since

= k(m 1) + 1, some m of these rows are the same colour, and we are
done.
Remark. For x
1
, x
2
, . . . , x
m
N, let
FS(x
1
, x
2
, . . . , x
m
) =

iI
x
i
: = I [m]

.
Then Theorem 16 for (m, 1, 1)-sets implies:
Whenever N is nitely coloured, there exist x
1
, x
2
, . . . , x
m
with
FS(x
1
, x
2
, . . . , x
m
) monochromatic.
This result is variously known as the nite sums theorem, Folkmans Theorem
or Sanderss Theorem.
Similarly, we can guarantee a monochromatic
FP(x
1
, x
2
, . . . , x
m
) =

iI
x
i
: = I [m]

by looking at 2
n
: n N.
Lemma 17. If A has the columns property then there exist m, p, c N
such that every (m, p, c)-set contains a solution to Ax = 0, i.e. we can solve
Ax = 0 with all x
i
in the (m, p, c)-set.
Proof. Let A have columns c
(1)
, c
(2)
, . . . , c
(n)
. As A has the columns prop-
erty, we have a partition B
1
B
2
B
r
of [n] such that
(i)

iB
1
c
(i)
= 0; and
(ii)

iB
s
c
(i)

c
(j)
: j B
1
B
2
B
s1

for all s 2.
Suppose

iB
s
c
(i)
=

iB
1
B
2
B
s1
q
is
c
(i)
.
Then for each s we have

i[n]
d
is
c
(i)
= 0
16
where
d
is
=

0 if i B
1
B
2
B
s
1 if i B
s
q
is
if i B
1
B
2
B
s1
.
Given x
1
, x
2
, . . . , x
r
N, put y
i
=

r
s=1
d
is
x
s
for i = 1, 2, . . . , n. Then
n

i=1
y
i
c
(i)
=
n

i=1
r

s=1
d
is
x
s
c
(i)
=
r

s=1
x
s
n

i=1
d
is
c
(i)
= 0.
So Ay = 0. Now we are done, for we may take m = r, take c to be the least
common multiple of the denominators of the q
i
, and take p to be c times
the maximum of the numerators of the q
i
. Then cy is in the (m, p, c)-set
generated by x
1
, x
2
, . . . , x
n
and A(cy) = 0.
Theorem 18 (Rados Theorem). Let A be a rational matrix. Then A is
partition regular if and only if A has the columns property.
Proof. is Proposition 15.
follows from Theorem 16 and Lemma 17.
Corollary 19 (The Consistency Theorem). If A and B are partition
regular then the matrix

A0
0 B

is also partition regular. In other words, if we

can guarantee to solve Ax = 0 in some colour class and By = 0 in some
colour class then we can guarantee to solve both in the same colour class.
Remark. This is not obvious by considerations of partition regularity alone.
Corollary 20. Whenever N is nitely coloured, some colour class contains
solutions to all PR equations.
Proof. Suppose not. Then we have N = D
1
D
2
D
k
, and, for each i,
a PR matrix A
i
such that D
i
does not contain a solution of A
i
x = 0. Then
consider the matrix

A
1
A
2
.
.
.
A
k

.
This is PR, by the Consistency Theorem, but no D
i
contains a solution to
it, a contradiction.
We say that D
i
N is partition regular if it contains a solution to every
PR equation. So Corollary 20 says that if N = D
1
D
2
D
k
then
some D
i
is PR. Rado conjectured, and Deuber proved, that if D is PR and
D = D
1
D
2
D
k
then some D
i
is PR.
17
2.2 Filters and Ultralters
A lter on N is a non-empty collection T {(N) such that
(i) T;
(ii) if A T and B A then B T (T is an up-set); and
(iii) if A, B T then A B T (T is closed under nite intersections).
Intuitively, we think of the sets of our lter as being the large subsets of N.
Examples. The following are lters
(i) A N : 1, 2 A;
(ii) A N : A
c
nite, the conite lter;
(iii) A N : E A nite where E is the set of even numbers.
An ultralter is a maximal lter. For any x N, the set A N : x A is
an ultralter, the principal ultralter at x.
Proposition 21. A lter T is an ultralter if and only if for all A N,
either A T or A
c
T.
Proof. This is obvious since we cannot add A to T if we already have A
c
.
Suppose T is an ultralter and A, A
c
T. Then we must have B T
with B A = (for otherwise T

= C N : C A B for some B T
is a lter containing T). Similarly, we must have C T with C A
c
= .
But then B C = , a contradiction.
Note. If A |, an ultralter, and A = B C, then B | or C |
(for otherwise B
c
, C
c
| by Proposition 21 whence A
c
= B
c
C
c
|, a
contradiction).
Proposition 22. Every lter is contained in an ultralter.
Proof. By Zorns Lemma, it is sucient to check that every non-empty chain
T
i
: i I has an upper bound. Indeed, put T =
iI
T
i
. Then
(i) T;
(ii) if A T and B A then A T
i
for some i, so B T
i
and so
B T;
18
(iii) if A, B T then A, B T
i
for some i (as the T
i
form a chain), so
A B F
i
and so A B T.
Remarks. 1. Any ultralter extending the conite lter is non-principal.
Also, if | is non-principal then | contains all conite sets; for if A | for
some nite A then x | for some x A by our note above.
2. The Axiom of Choice is needed in some form to get non-principal
ultralters.
The set of all ultralters on N is denoted N. We dene a topology on N
by taking as a base all sets of the form
C
A
= | N : A |, A N.
This is a base: it is sucient to check that

C
A
= N and that the in-
tersection of any two of the C
A
is another set of the putative base. Plainly

C
A
= N, and C
A
C
B
= C
AB
as A, B | if and only if A B |.
Thus open sets are of the form

iI
C
A
i
= | : A
i
| for some i I.
Note that N C
A
= C
A
c. So closed sets are of the form

iI
C
A
i
= | : A
i
| for all i I.
We have N inside N (identifying n N with the principal ultralter n at
n). Each point of N is isolated: C
{n}
= n. Also, N is dense in Nevery
non-empty open set in N meets N as n C
A
whenever n A.
Theorem 23. N is a compact Hausdor space.
Proof. Hausdor: Given | = 1, we have some A | with A 1. But then
A
c
1 and so | C
A
and 1 C
A
c.
Compact: Given closed sets (F
i
)
iI
with the nite intersections property
(i.e. all nite intersections are non-empty), we need to show that

iI
F
i
= .
Assume without loss of generality that each F
i
is basic, i.e. that F
i
= C
A
i
for
some A
i
N.
We rst observe that the sets (A
i
)
iI
also have the nite intersections
property. For we have C
A
i
1
C
A
i
2
C
A
i
n
= C
A
i
1
A
i
2
A
i
n
and so
A
i
1
A
i
2
A
i
n
= .
19
So we can dene a lter T generated by the A
i
:
T = A N : A A
i
1
A
i
2
A
i
n
for some i
1
, i
2
, . . . , i
n
I.
Let | be an ultralter extending T. Then A
i
| for all i, so u C
A
i
for
all i, and so
iI
C
A
i
= as desired.
Remarks. 1. If we view an ultralter as a function from {(N) 0, 1
then we have N 0, 1
P(N)
. We can check that the topology on N is the
restriction of the product topology, and also that N is a closed subset of
0, 1
P(N)
so compact by Tychonov.
2. N is the largest compact Hausdor space in which N is denseit is
called the Stone-

Cech compactication of N.
Let | be an ultralter and p a statement. We write
U
x p(x) to mean
x : p(x) |, and say that p(x) holds for most x or for |-most x. For
example,
(i) for | non-principal,
U
x x > 4;
(ii) for | = n we have
U
x p(x) p(n).
Proposition 24. Let | be an ultralter and p and q statements. Then
(i)
U
x (p(x) AND q(x)) (
U
x p(x)) AND (
U
x q(x))
(ii)
U
x (p(X) OR q(x)) (
U
x p(x)) OR (
U
x q(x))
(iii) if
U
x p(x) does not hold then
U
x (NOT p(x)).
Proof. Let A = x : p(x) and let B = x : q(x). Then
(i) A B | if and only if A | and B |;
(ii) A B | if and only if A | or B |;
(iii) if
U
x p(x) is false then A | and so A
c
|.
Note.
U
x
V
y p(x, y) need not be the same as
V
y
U
x p(x, y)even if
| = 1. For example, if | is non principal then
U
x
U
y x < y is true, but

U
y
U
x x < y is false.
For |, 1 N, dene
| +1 = A N :
U
x
U
y x +y A
= A N : x N : y : x +y A 1 |.
20
Proposition 25. So dened, + is a well-dened map from NN N.
It is associative and left-continuous.
Proof. First, we show that | +1 is an ultralter. Clearly | +1, and if
A | + 1 and B A then B | + 1. Suppose now that A, B | + 1,
i.e.
(
U
x
V
y x +y A) AND (
U
x
V
y x +y B).
Then by proposition 24 (i),

U
x ((
V
y x +y A) AND (
V
y x +y B))
whence in turn

U
x
V
y (x +y A AND x +y B),
i.e.

U
x
V
y (x +y A B),
i.e.
A B | +1
as required. Finally, suppose that A | +1. Then
x :
V
y x +y A |
so by Proposition 24 (iii),

U
x (NOT (
V
y x +y A))
whence in turn

U
x
V
y (NOT x +y A),
i.e.

U
x
V
y (x +y A
c
)
and so
A
c
| +1.
So we have shown that | +1 is an ultralter.
We next observe that +: N N N is associative. Indeed, for any
|, 1, J N,
| + (1 +J) = A N :
U
x
V+W
t x +t A
= A N :
U
x t : x +t A 1 +J
= A N :
U
x
V
y
W
z y +z t : x +t A
= A N :
U
x
V
y
W
z x +y +z A
= (| +1) +J.
21
Finally, we show that + is left-continuous, i.e. that for xed 1, the map
| | + 1 is continuous. So x V and an open set C
A
in our base for N.
Then
| +1 C
A
A | +1
x :
V
y x +y A |
| C
{x:
V
y x+yA}
,
so + is indeed left-continuous.
Fact. The operation + is neither commutative nor right-continuous.
We seek an idempotent ultralter, i.e. some | N such that | + | = |.
(Note that any such | must be non-principal, as n + n =

2n.)
Lemma 26 (The Idempotent Lemma). Suppose X is a non-empty com-
pact Hausdor topological space and +: X X X is an associative and
left-continuous binary operation. Then there is an element x X such that
x +x = x.
Proof. Consider S = Y X : Y compact and nonempty, Y + Y Y
(where by Y +Y we mean y +y

: y, y

Y ).
We rst show that S has a minimal element. Clearly X S, so S = ,
so by Zorns Lemma it is sucient to show that if Y
i
: i I is a chain in S
then Y =
iI
Y
i
S. Since in a compact Hausdor space a set is compact
precisely if it is closed, we see that Y is compact; also Y = since the Y
i
are
closed sets having the nite intersection property in the compact space X.
Also, for y, y

Y we have y, y

Y
i
for all i, so y +y

Y
i
+Y
i
Y
i
for all
i and so y +y

Y . Thus Y S, proving our claim.

Let Y be a minimal element of S and x x Y . We will show that
x +x = x.
We begin by showing that Y +x S. We see that Y +x is non-empty and
compact, since it is the continuous image of a compact set by left-continuity
of +. Also, by associativity of +, (Y +x)+(Y +x) = (Y +x+Y )+x Y +x.
This shows that Y +x Y .
Now, we know Y +x Y , so we must have Y +x = Y by minimality of
Y . Hence there exists y Y with y +x = x. Put Z = y Y : y +x = x.
We now show that Z S. By our remarks above, Z is non-empty. Note
that x is compact, and so closed in the compact Hausdor subspace Y of
X. So Z, which is the inverse image in Y of the set x under the continuous
map y y + x is closed, and so compact. Also, for y, y

Z, we have by
associativity of + that (y + y

) + x = y + (y

+ x) = y + x = x, and so
y +y

Z. This shows that Z S.

22
But Z Y and so Z = Y . In particular, x Z and so x + x = x as
desired.
Remark. Hence Y +x = x and so Y = x.
Corollary 27. There exists | N such that | +| = |.
Theorem 28 (Hindmans Theorem). Whenever N is nitely coloured,
there exist x
1
, x
2
, x
3
, . . . with FS(x
1
, x
2
, x
3
, . . . ) monochromatic.
Proof. Given N = A
1
A
2
A
k
, choose an idempotent | N. We have
A
i
| for some i; write A = A
i
. (Intuitively, we think of A as the largest
colour class.) So
U
y y A. Also, as | is idempotent,
U
x
U
y x + y A.
So
U
x
U
y FS(x, y) A by Proposition 24. Pick x
1
with
U
y FS(x
1
, y) A.
Now suppose inductively that we have found x
1
, x
2
, . . . , x
n
such that

U
y FS(x
1
, x
2
, . . . , x
n
, y) A. For each z FS(x
1
, x
2
, . . . , x
n
, y) we have

U
y z + y A and so
U
x
U
y z + x + y A. Thus by Proposition 24,

U
x
U
y FS(x
1
, x
2
, . . . , x
n
, x, y) A. Let x
n+1
be such an x.
The result follows by induction.
3 Innite Ramsey Theory
For innite M N, write M
()
for the collection L M : L innite of all
innite subsets of M. Motivated by Theorem 2, we ask: if we nitely colour
N
()
, is there an innite monochromatic set (i.e. does there exist M N
()
such that all L M
()
have the same colour)?
Proposition 29. There is a 2-colouring of N
()
without an innite monochro-
matic set.
Proof. We construct a 2-colouring c such that for all M N
()
and all
x M we have c(M x) = c(M)this is clearly sucient to prove the
proposition.
Dene a relation on N
()
by L M [LM[ < . This is clearly
an equivalence relation. Let the equivalence classes be E
i
: i I, and for
each i choose M
i
E
i
. Now dene c(M) to be RED if [MM
i
[ is even for
some i I and to be BLUE if [MM
i
[ is odd for some i I. It is easy to
check that this colouring has the required property.
Note that in the above proof we used AC.
A 2-colouring of N
()
corresponds to a partition N
()
= Y Y
c
for some
Y N
()
. A collection Y N
()
is called Ramsey if there exists M N
()
23
with M
()
Y or M
()
Y
c
. So Proposition 29 says that not all sets are
Ramsey.
We can induce the subspace topology on N
()
{(N), where we identify
{(N) with 0, 1
N
with the product topology. So a basic open neighbourhood
of M N
()
is L N
()
: L[n] = M [n] for some n. Writing M
(<)
for
the collection A M : A nite of nite subsets of M, we have a base of
open sets for N
()
:
M N
()
: A an initial segment of M, A N
(<)
.
Equivalently, we have a metric
d(L, M) =

0 if L = M
1/ min(LM) if L = M
.
We call this the -topology or usual topology or product topology on N
()
.
For A N
(<)
and M N
()
, write
(A, M)
()
= L N
()
: A is an initial segment of L and L A M.
(We think of this as the collection of sets which start as A and carry on
inside M.)
For xed Y N
()
, we say that M accepts A (into Y ) if (A, M)
()
Y ,
and that M rejects A if no L M
()
accepts A.
Notes. 1. If M accepts A then every L M
()
accepts A as well.
2. If M rejects A then every L M
()
rejects A as well.
3. If M accepts A and A B A M, then M accepts B as long as
max A min M.
4. M need not accept or reject A.
Lemma 30 (The Galvin-Prikry Lemma). Given Y N
()
, there exists
a set M N
()
such that either
(i) M accepts into Y ; or
(ii) M rejects all of its nite subsets.
Proof. Suppose no M N
()
accepts , i.e. that N rejects . We shall
inductively construct innite subsets M
1
M
2
M
3
of N and
a
1
, a
2
, a
3
, . . . N with a
i
M
i
for all i and such that M
i
rejects all subsets
of a
1
, a
2
, . . . , a
i1
. Then we shall be done, for a
1
, a
2
, a
3
, . . . rejects all
its nite subsets.
24
Take M
1
= N. Having chosen M
1
M
2
M
k
and a
1
, a
2
, . . . , a
k1
as above, we seek a
k
M
k
and M
k+1
M
k
such that M
k+1
rejects all nite
subsets of a
1
, a
2
, . . . , a
k
.
Suppose this is impossible. Fix b
1
M
k
with b
1
> a
i
for 1 i k 1.
We cannot take a
k
= b
1
and M
k+1
= M
K
so some N
1
M
()
k
accepts some
subset S of a
1
, a
2
, . . . , a
k1
, b
1
. And S must be of the form E
1
b
1

as M
k
rejects all subsets of a
1
, a
2
, . . . , a
k1
. Now pick b
2
N
1
with
b
2
> b
1
and try a
k
= b
2
and M
k+1
+ N
1
. We get N
2
N
()
1
accepting a
subset of a
1
, a
2
, . . . , a
k1
, b
2
say N
2
= E
2
b
2
. Keep going: we get
M
k
N
1
N
2
and b
1
< b
2
< b
3
< (b
1
N
i1
), together with
E
1
, E
2
, E
3
, . . . a
1
, a
2
, . . . , a
k1
such that E
n
b
n
is accepted by N
n
for all n. Passing to a subsequence if necessary, we may assume without loss
of generality that E
n
= E for all n. Then E is accepted by b
1
, b
2
, b
3
, . . . ,
contradicting the denition of M
k
.
Theorem 31. If Y is open then Y is Ramsey.
Proof. By Galvin-Prikry, there exists M N
()
with either
(i) M accepting ; or
(ii) M rejecting all its nite subsets.
If (i) then we have M
()
Y .
If (ii) then we will show M
()
Y
c
. Indeed, suppose we have L M
()
with L Y . Since Y is open, we must have (A, N)
()
Y for some initial
segment A of L. So in particular, we have (A, M)
()
Y , i.e. M accepts A,
a contradiction.
Remark. A collection Y is Ramsey if and only if Y
c
is Ramsey, so Theorem
31 also says that closed sets are Ramsey.
The -topology or Ellentuck topology or Mathias topology on N
()
has basic
open sets (A, M)
()
for A N
(<)
and M N
()
. This is a base for a
topology on N
()
:
N
()
= (, N)
()
so the union of our putative basic sets is indeed N
()
;
if (A, M)
()
and (A

, M

)
()
are basic sets then (A, M)
()
(A

, M

)
()
is either (A A

, M M

)
()
or .
Note that the -topology is stronger (i.e. has more open sets) than the usual
topology.
Theorem 32. If Y is -open then Y is Ramsey.
25
Proof. Choose M N
()
as given by Galvin-Prikry.
(i) If M accepts then M
()
Y .
(ii) If M rejects all its nite subsets then we shall show that M
()
Y
c
.
Indeed, suppose L M
()
with L Y . Since Y is -open, we must have
(A, L)
()
Y for some initial segment A of L. So L accepts A, contradicting
M rejects A.
We say Y N
()
is completely Ramsey if for all A N
(<)
and all
M N
()
there is some L M
()
such that (A, L)
()
is contained in either
Y or Y
c
.
This is a stronger property than being Ramsey. For example, let Y be
the non-Ramsey set from Proposition 29 and set
Y

= Y M N
()
: 1 M.
Then certainly Y

is Ramsey, as 2, 3, 4, . . .
()
Y
c
. But Y

is not com-
pletely Ramsey; A = 1 and M = N yield no L as desired.
Theorem 33. If Y is -open then Y is completely Ramsey.
Proof. Given A N
(<)
and M N
()
, we seek L M
()
with (A, L)
()
contained in Y or Y
c
. Now view (A, M)
()
as a copy of N
()
as follows.
We may assume without loss of generality that max A < min M. Write
M = m
1
, m
2
, m
3
, . . . , where m
1
< m
2
< m
3
< , and dene a function
f : N
()
(A, M)
()
by N A M
i
: i N. Clearly f is a homeomor-
phism in the -topology.
Let Y

= N N
()
: f(N) Y . Then Y

is -open since Y is -open.

So by Theorem 32, there exists L N
()
with L
()
contained in either Y or
Y
c
. Thus f(N) : N L
()
is contained in either Y or Y
c
, i.e. (A, f(L))
()
is contained in either Y or Y
c
.
So we know that, in the -topology, all locally big (i.e. open) sets are
completely Ramsey. Now we consider locally small (i.e. nowhere dense)
sets.
Given a space X, we say that A X is nowhere dense if A is not dense
in any non-empty open subset, equivalently if for any non-empty open O,
there is a non-empty open O

O such that O

A = , equivalently if

A
has empty interior. For example, N is nowhere dense in R.
Proposition 34. A set Y N
()
is -nowhere-dense if and only if for all
a N
(<)
and all M N
()
, there is some L M
()
with (A, L)
()
Y
c
.
26
Proof. The rst statement says that inside (A, M)
()
there is some (B, L)
()
missing Y while the second says that inside (A, M)
()
there is some (A, L)
()
missing Y . So it is immediate that the second statement implies the rst.
So suppose that Y is -nowhere-dense. Then

Y has non-empty interior
and so

Y is -nowhere-dense (since

Y =

Y ). But

Y is completely Ramsey
by Theorem 33 and so inside (A, M)
()
there exists some (A, L)
()
contained
in either

Y or (

Y )
c
. But int

Y = so (A, L)
()
(

Y )
c
and so (A, L)
()
Y
c
as required.
A subset A of a topological space X is called meagre or of rst category
if A =

n=1
A
n
with each A
n
nowhere dense. For example, Q is meagre in
R.
We can usually think of meagre sets as being small: for example, the
Baire Category Theorem states that if X is a non-empty complete metric
space and A is a meagre subset of X then A = X.
Theorem 35. Let Y be -meagre. Then for all A N
(<)
and all M N
()
,
there is some L M
()
such that (A, L)
()
Y
c
. In particular, Y is
-nowhere-dense.
Proof. Suppose we are given A N
(<)
and M N
()
. Write Y =

n1
Y
n
with each Y
n
-nowhere-dense.
By Proposition 34, we have M
1
M
()
with (A, M
1
)
()
Y
c
1
. Choose
x
1
M
1
with x
1
> max A.
Again by Proposition 34, we have M

2
M
()
1
with (A, M

2
)
()
Y
c
2
and
then M
2
M
()
2
with (Ax
1
, M
2
)
()
Y
c
2
. Choose x
2
M
2
with x
2
> x
1
.
Applying Proposition 34 four times, once for each subset of x
1
, x
2
, we
get M
3
M
()
2
such that each of the sets (A, M
3
)
()
, (A x
1
, M
3
)
()
,
(A x
2
, M
3
)
()
and (A x
1
, x
2
, M
3
)
()
is contained in Y
c
3
.
Keep going: we obtain M M
1
M
2
and max A < x
1
< x
2
<
with x
n
M
n
for all n and (A F, M
n
)
()
Y
c
n
for all F x
1
, x
2
, . . . x
n
.
Then (A, x
1
, x
2
, . . . )
()
Y
c
n
for all n and so (A, x
1
, x
2
, . . . )
()
Y
c
.
A set A in a topological space is a Baire set, or has the property of Baire,
if A = OM for some open O and meagre M. We can think of A as being
nearly open.
Notes. 1. If A is open then A is Baire.
2. If A is closed then A is Baire, since A = int A(A int A), where
A int A is nowhere dense as it is closed and contains no non-empty open
set.
The Baire sets form a -algebra:
27
(i) X is Baire.
(ii) If Y is Baire, say Y = OM, then
Y
c
= O
c
M
= (O

)M (since O
c
is closed, and using note (ii) above)
= O

(M

M)
so Y
c
is Baire.
(iii) If the sets Y
1
, Y
2
, Y
3
, . . . are Baire, say Y
i
= O
i
M
i
, then their union

n=1
Y
n
= (

n=1
O
n
)M for some M

n=1
M
n
and so

n=1
Y
n
is
Baire.
Since we noted above that open sets are Baire, it follows that any Borel
set is Baire.
Theorem 36. A collection Y is completely Ramsey if and only if it is
-Baire.
Proof. Suppose Y is -Baire, so Y = WZ with W open and Z meagre.
Given (A, M)
()
, we have L M
()
with (A, L)
()
contained in either W
or W
c
(by Theorem 33) and N L
()
with (A, N)
()
Z
c
(by Theorem 35).
So either
(A, N)
()
W Z
c
Y
or
(A, N)
()
W
c
Z
c
Y
c
and Y is completely Ramsey as required.
Suppose conversely that Y is completely Ramsey. We can write
Y = int Y (Y int Y ). so it will be sucient for us to show that Y int Y
is -nowhere-dense; we show in particular that given any base set (A, M)
()
in the -topology, there is a non-empty open set inside it which is disjoint
from Y int Y indeed, we have L M
()
with (A, L)
()
contained in either
Y or Y
c
.
If (A, L)
()
Y then (A, L)
()
is disjoint from Y int Y .
If (A, L)
()
Y
c
then again (A, L)
()
is disjoint from Y int Y .
So Y is -Baire, as required.
Thus any -Borel set is completely Ramsey, and so certainly any -Borel
set is Ramsey.
Note. Without Theorem 35, we would have shown that Y is completely
Ramsey if and only if Y is the symmetric dierence of an open set and
28
a nowhere dense set, and we would not have known that the completely
Ramsey sets form a -algebra.
Typeset in L
A
T
E
X 2 by Paul A. Russell.
29