Ramsey’s Theorem
Today in lecture, I heard an amusing proof of Ramsey’s Theorem which I reproduce here. The terminology used in it is quite … entertaining.
Notation: X is a set, then [X]k is the set of k-element subsets of X.
Ramsey’s Theorem: for all integers k ≥ 1, if X is an infinite set and F is a function from [X]k to a finite set C, then X has an infinite homogeneous subset Y, i.e. F restricted to [Y]k is constant.
Proof: By induction on k. The case k=1 follows from the pigeonhole principle. Now suppose Ramsey’s theorem holds for k. It suffices to prove the statement for X=ω. Fix an F as in the statement of the theorem.
Definition: If Y⊆ω is infinite, then a k-element subset {i1 < … < ik} is happy if for all j,j’∈Y, j,j’>ik, F(i1,…,ik, j) = F(i1,…,ik, j’).
Definition: An infinite Y⊆ω is pretty good if every {i1 < … < ik} in Y is happy.
Claim: There is an infinite, pretty good Y⊆X. Given this claim, can define a function G from [X]k to C by G(i1,…,ik) = F(i1,…,ik, j) for some (or any) j in Y, j>ik. By the inductive hypothesis, there is an infinite Z⊆Y such that G restricted to [Z]k is constant. Thus, F restricted to [Z]k+1 is constant as well, and the theorem follows.
Definition: An infinite Y⊆ω is a-dorable if a>0 is an integer and letting Z be the first a elements of Y, every {i1 < … < ik} in [Z]k is happy.
Proof of Claim:
Lemma: Assume Y⊆ω is infinite and a-dorable. Then there is an infinite Y’⊆Y with the first a elements of Y equal to the first a elements of Y’ and Y’ a-dorable.
Proof of Lemma: let Z be the first a+1 elements of Y. Let i* be the maximal element of Z (the (a+1)th element of Y). Apply the pigeonhole principle a finite number of times to find an infinite Y’⊆Y with Z⊆Y’ such that every {i1 < … < ik, i*} in [Z]k+1 is happy in Y’. Lemma follows.
Let Y0=ω. Then Y0 is 0-dorable. Inductively construct a tower Y0⊆Y1⊆Y2⊆… of infinite sets such that for each a, the first a elements of Ya equal the first a elements of Ya+1 and each Ya is a-dorable. Then the intersection of all the Ya for a∈ω is infinite (since it contains a subset of a elements for every a∈ω) and pretty good. This proves the Claim, and the theorem.