Ramsey’s Theorem

Figure 26-1. A party with no clique or anticlique of three.

We are going to prove a theorem that bears on these puzzles. Recall that by a partition of a nonempty set we mean a family of nonempty subsets thereof, called the classes of the partition, such that every element of the original set belongs to exactly one of these classes. By a size-k set we mean a set with exactly k elements.

26.1 Theorem (Ramsey’s theorem). Let r, s, n be positive integers with n ≥ r. Then there exists a positive integer m ≥ n such that for X = {0, 1, . . . , m − 1}, no matter how the size-r subsets of X are partitioned into s classes, there will always be a size-n subset Y of X such that all size-r subsets of Y belong to the same class.

A set Y all of whose size-r subsets belong to the same one of the s classes is called a homogeneous set for the partition. Note that if the theorem holds as stated, then it clearly holds for any other size-m set in place of {0, 1, . . . , m − 1}.

For instance, it holds for the set of partiers at a party where m persons are present. In the puzzles, the size-2 subsets of the set of persons at the party were partitioned into two classes, one consisting of the pairs of persons who like each other, the other, of the pairs of persons who dislike each other. So in both problems r = s = 2. In the first, where n = 3, we showed how to prove that m = 6 is large enough to guarantee the existence of a homogeneous set of size n—a clique of three who like each other, or an anticlique of three who dislike each other. We also showed that 6 is the least number m that is large enough. In the second problem, where n = 4, we reported that

m= 18 is large enough, and that 18 is in fact the least value of m that is large enough. In principle, since there are only finitely many size-r subsets of {0, . . . , m − 1},

and only finitely many ways to partition these finitely many subsets into s classes, and since there are only finitely many size-n subsets, we could set a computer to work searching through all partitions, and for each looking for a homogeneous set. If some partition were found without a homogeneous set, the computer could go on to do a similar check for {0, . . . , m}. Continuing in this way, in a finite amount of time it would find the least m that is large enough to guarantee the existence of the required homogeneous set.

In practice, the numbers of possibilities to be checked are so large that such a procedure is hopelessly infeasible. We do not at present have sufficient theoretical insight into the problem to be able to reduce the number of possibilities that would have to be checked to the point where a computer could feasibly be employed in surveying them in order to pinpoint the least m. And it is entirely conceivable that because of the such physical limitations as those imposed by the speed of light, the atomic character of matter, and the short amount of time before the universe becomes unable to sustain life, we are never going to know exact what the value of the least m is, even for some quite small values of r, s, and n.

So let us set aside the difficult problem of finding the least m that is large enough, and turn to proving that there is some m that is large enough. The proof of Theorem 26.1 that we are going to present will make a ‘detour through the infinite’. First we prove the following infinitary analogue:

26.2 Theorem (Infinitary Ramsey’s theorem). Let r, s be positive integers. Then no matter how the size-r subsets of the set X = {0, 1, 2, . . . } are partitioned into s classes, there will always be an infinite subset Y of X such that all size-r subsets of Y belong to the same class.

Note that if the theorem holds as stated, then it clearly holds for any other enumerably infinite set in place of {0, 1, 2, . . . }. (If Zeus threw a party for an enumerable infinity of guests, any two of whom either liked each other or disliked each other, there would either be infinitely many guests, any two of whom liked each other, or infinitely many, any two of whom disliked each other.) In fact Theorem 26.2 holds for any infinite set X , because any such set has an enumerably infinite subset (though it requires the axiom of choice to prove this, and we are not going to go into the matter).

The proof of Theorem 26.2 will be given in this section, and the derivation of Theorem 26.1 from it—which will involve an interesting application of the compactness theorem—in the next. Before launching into the proof, let us introduce some notation that will be useful for both proofs.

A partition of a set Z into s classes may be represented by a function f whose arguments are the elements of Z and whose values are elements of {1, . . . , s}: the ith class in the partition is just the set of those z in Z with f (z) = i. Let us write f : Z → W to indicate that f is a function whose arguments are the elements of Z and whose values are elements of W . Our interest is in the case where Z is the collection of all the size-r subsets of some set X. Let us denote this collection [X]r . Finally, let us write ω for the set of natural numbers. Then the infintary version of

Proof of Theorem 26.2: Our proof will proceed as follows. For any fixed s > 0, we show by induction on r that for any r > 0 we can define an operation such that if f : [ω]r → {1, . . . , s}, then ( f ) is a pair ( j, Y ) with f : [Y ]r → { j}.

Basis step: r = 1. In this case the definition of ( f ) = ( j, Y ) is easy. For each of the infinitely many size-1 sets {b}, f ({b}) is one of the finitely many positive integers k ≤ s. We can thus define j as the least k ≤ s such that f ({b}) = k for infinitely many b, and define Y as {b : f ({b}) = j}.

Induction step: We assume as induction hypothesis that has been suitably defined for all g : [ω]r → {1, . . . , s}. Suppose f : [ω]r+1 → {1, . . . , s}. In order to define

( f ) = ( j, Y ), we define, for each natural number i, a natural number bi , infinite sets Yi , Zi , Wi , a function fi : [ω]r → {1, . . . , s}, and a positive integer ji ≤ s. Let Y0 = ω. We now suppose Yi has been defined, and show how to define bi , Zi , fi , ji , Wi , and

Yi+1.

called the levels of the tree; and (iii) a two-place relation R subject to the following conditions:

(1)Rab never holds for b in T0.

(2)For b in Tn+1, Rab holds for exactly one a, and that a is in Tn .

When Rab holds, we say a is immediately below b, and b is immediately above a. Figure 26-2 is a picture of a finite tree with ten nodes and four levels. Line segments

connect nodes immediately below and above each other.

Figure 26-2. A finite tree.

A branch through a tree is a sequence of nodes b0, b1, b2, . . . with each bn immediately below bn+1. Obviously, an infinite tree none of whose levels is infinite must have infinitely many nonempty levels. The following is not so obvious.

26.3 Lemma (Konig’s¨ lemma). An infinite tree none of whose levels is infinite must have an infinite branch.

Postponing the proof of this result, let us see how it can be used as a bridge between the finite and the infinite.

Proof of Theorem 26.1: Suppose that Theorem 26.1 fails. Then for some positive integers r, s, n, with n ≥ r, for every m ≥ n there exists a partition

f : [{0, 1, . . . , m − 1}]r → {1, . . . , s}

having no size-n homogeneous set Y . Let T be the set of all such partitions without size-n homogeneous sets for all m, and let Tk be the subset of T consisting of those f with m = n + k. Let Rfg hold if and only if for some k

f: [{0, 1, . . . , n + k − 1}]r → {1, . . . , s}

g: [{0, 1, . . . , n + k}]r → {1, . . . , s}

and g extends f, in the sense that g assigns the same value as does f to any argument in the domain of f . It is easily seen that for any g in Tk+1 there is exactly one f in Tk that g extends, so what we have defined is a tree.

There are only finitely many functions from a given finite set to a given finite set, so there are only finitely many nodes f in any level Tk . But our initial supposition was that for every m = n + k there exists a partition f in Tk , so the level Tk is nonempty for all k, and the tree is infinite. Konig’s¨ lemma then tells us there will be an infinite branch f0, f1, f2, . . . , which is to say, an infinite sequence of partitions, each extending the one before, and none having a size-n homogenous set. We can then define a partition

F : [ω]r → {1, . . . , s}

as follows. For any size-r subset x of ω, let p be its largest element. Then for any k large enough that p < n + k, x will be in the domain of fk , and we have

fk (x) = fk+1(x) = fk+2(x) = · · ·.

Let F(x) be this common value.

By the infinitary version of Ramsey’s theorem, F has an infinite homogeneous set. That is, there is an infinite Y and a j with 1 ≤ j ≤ s such that F: [Y ]r → { j}. Let Z be the set of the first n elements of Y , and take k large enough that the largest element of Z is less than n + k. Then Z will be a size-n subset of {0, . . . , n + k − 1}, with fk (x) = F(x) = j for all size-r subsets x of Z . In other words, Z will be a size-n homogeneous set for fk , which is impossible, since fk is in T . This contradiction completes the proof.

Proof of Lemma 26.3: To prove Konig’s¨ lemma we are going to use the compactness theorem. Let LT be the language with one one-place predicate B and with one constant t for each node t in the tree T . Let consist of the following quantifier-free sentences:

for all pairs of nodes s, t belonging to the same level; and

for every node s, where u1, . . . , um are all the nodes immediately above s. [If there are no nodes above s, the sentence (3) is just Bs.]

We first show that if has a model M, then T has an infinite branch. By (1) there will be at least one node r in T0 such that Br is true in M. By (2) there will in fact be exactly one such node, call it r0. By (3) applied with r0 as s, there will be at least one node r immediately above r0 such that Br is true in M. By (2) there will in fact be exactly one such node, call it r1. Repeating the process, we obtain r0, r1, r2, . . . , each immediately above the one before, which is to say that we obtain an infinite branch.

We next show that does have a model. By the compactness theorem, it is enough to show that any finite subset of has a model. In fact, we can show that for any k, the set k containing the sentence (1), all the sentences (2), and all the sentences

(3) for s of level less than k has a model. We can then, given a finite , apply this fact to the least k such that all s occurring in are of level <k, to conclude that has a model.

To obtain a model of k , let the domain be T , and let the denotation of each constant r be the node r. It remains to assign a denotation to B. Take any tk at level Tk , and take as the denotation of B the set consisting of tk , the node tk−1 at level Tk−1 immediately below tk , the node tk−2at level Tk−2 immediately below tk−1, and so on down until we reach a node t0 at level 0.

The presence of t0 in the denotation of B will make (1) true. Since we have included in the denotation of B only one node ti at each level Ti for i ≤ k and none at higher levels, (2) will be true. For a sentence of form (3) with s of level i < k, the first disjunct will be true unless s is ti , in which case the Bti+1 will be among the other disjuncts, and will be true. In either case, then, (3) will be true for every sentence of this type ink . [The sentence of form (3) with tk as s will be false, but that sentence is not in k .]

Before indicating the connection of Ramsey’s theorem with the kind of logical phenomena we have been concerned with in this book, we digress a moment to present a pretty application of Ramsey’s theorem.

26.4 Corollary (Schur’s theorem). Suppose that each natural number is ‘painted’ exactly one of some finite number of ‘colors’. Then there are positive integers x, y, z all the same color such that x + y = z.

Proof: Suppose the number of colors is s. Paint each size-2 set {i, j}, i < j, the same color as the natural number j − i. By Ramsey’s theorem (r = 2, n = 3), there are a positive integer m ≥ 3 and a size-3 subset {i, j, k} of {0, 1, . . . , m − 1} with i < j < k, such that {i, j}, { j, k} and {i, k} are all the same color. Let x = j − i, y = k − j, and z = k − i. Then x, y, z are positive integers all the same color, and x + y = z.

Ramsey’s theorem is, in fact, just the starting point for a large body of results in combinatorial mathematics. It is possible to add some bells and whistles to the basic statement of the theorem. Call a nonempty set Y of natural numbers glorious if Y has more than p elements, where p is the least element of Y . Since every infinite set is automatically glorious, it would add nothing to the infinitary version of Ramsey’s theorem to change ‘infinite homogeneous set’ to ‘glorious infinite homogeneous set’. It does, however, add something to the statement of the original Ramsey’s theorem to change ‘size-n homogeneous set’ to ‘glorious size-n homogeneous set’.

Let us call the result of this change the glorified Ramsey’s theorem. Essentially the same proof we have given for Ramsey’s theorem proves the glorified Ramsey’s theorem. (At the beginning, take T to be the set of partitions without glorious size-n homogeneous sets, and towards the end, take Z to be the set of the first q elements of Y , where q is the maximum of n and p, p being the least element of Y.) There is, however, an interesting difference in logical status between the two.

While the proof we have presented for Ramsey’s theorem involved a detour through the infinite, F. P. Ramsey’s original proof of Ramsey’s theorem did not. Using a reasonable coding of finite sets of natural numbers by natural numbers, Ramsey’s theorem can be expressed in the language of arithmetic, and by ‘formalizing’ Ramsey’s proof, it can be proved in P. By contrast, the glorified Ramsey’s theorem, though it can be expressed in the language of arithmetic, cannot be proved in P.

It is an example of a sentence undecidable in P that is far more natural, mathematically speaking, than any we have encountered so far. (The sentences involved in Godel’s¨ theorem or Chaitin’s theorem, for instance, are ‘metamathematical’, being about provability and computability, not ordinary mathematical notions on the order of those occurring in Ramsey’s theorem.) Unfortunately, the Paris–Harrington theorem,