26 - Ramsey's Theorem

Summary

Ramsey's theorem is a combinatorial result about finite sets with a proof that has interesting logical features. To prove this result about finite sets, we are first going to prove, in section 26.1, an analogous result about infinite sets, and are then going to derive, in section 26.2, the finite result from the infinite result. The derivation will be an application of the compactness theorem. Nothing in the proof of Ramsey's theorem to be presented requires familiarity with logic beyond the statement of the compactness theorem, but at the end of the chapter we indicate how Ramsey theory provides an example of a sentence undecidable in P that is more natural mathematically than any we have encountered so far.

Ramsey's Theorem: Finitary and Infinitary

There is an old puzzle about a party attended by six persons, at which any two of the six either like each other or dislike each other: the problem is to show that at the party there are three persons, any two of whom like each other, or there are three persons, any two of whom dislike each other.

The solution: Let a be one of the six. Since there are five others, either there will be (at least) three others that a likes or there will be three others that a dislikes. Suppose a likes them. (The argument is similar if a dislikes them.) Call the three b, c, d.