Item — HN Reader

There is an infinite version of Ramsey's theorem.

Suppose you consider the collection of pairs of positive whole numbers, and each pair is colored either red or blue. Then there is an infinite set S of positive whole numbers such that any pair of items from S are the same color.

In symbols:

P = { (a,b) : a in N, b in N }

C : P -> {0,1}

There exists S an infinite subset of N and c in {0,1} such that for all a in S and b in S, C(a,b)=c.

The proof is quite simple, I use it regularly to boggle 13 and 14 year olds.

1 comments

I figured out the proof on my drive in to work. It is simple.

At all points we're going to have an infinite set of integers to process, a clique of integers whose connections to each other and all of the integers left to process is red, and a clique of integers whose connections to each other and all of the integers left to process is blue. (red clique, blue clique)

We start with all of N as our set, and our cliques are empty sets.

At each point we take the first thing in our set, and remove it from the set. If there are an infinite number of things left in our set that it has a red connection to, then put it into the red clique and remove all things from the set that its connection is blue to. Else put it into the blue clique and remove all things from the set that its connection is red to. This step can always be done and leaves us with 2 cliques (one of which grew by one) and an infinite set of integers to process.

After we do this an infinite number of times at least one of the red and blue cliques must now be infinite in size. And we're done.

That's an elegant way to express it - thank you. My method has more of the "TA DA!" about it, and tends to generate a sense of "Gosh!", but I like the quiet elegance of yours.

Nice one.