Van der Waerden’s Theorem is false for $latex \omega_1 $

One of my main research problems involves something I think is related to arithmetic progressions in . After learning a nice proof of Van der Waerden’s Theorem, and sharing it with colleagues, Daniel Soukup asked a nice question about Van der Waerden’s Theorem on . We answered it, and the example was sufficiently nice that I would like to share it.

Van der Waerden’s Theorem

First off let’s recall Van der Waerden’s Theorem, which was discovered before Ramsey’s famous theorem:

Van der Waerden’s Theorem (1926). If the enemy colours the natural numbers using only finitely many colours, then one of the colours must contain an arbitrarily long (but finite) arithmetic progression.

I learned that in the 50s Van der Waerden wrote an essay explaining his thought process as he discovered his proof. It is a wonderful essay about 8 pages in length and includes diagrams that he would have drawn on the chalkboard, special cases that help understanding, and the 5 important observations that lead to the proof. After reading this essay I really feel like I have absorbed the theorem, and I strongly recommend that people interested in Ramsey theory of the integers read it.

You can find a reproduction of the essay in Alexander Soifer’s 2009 book “The Mathematical Coloring Book“.

What about ?

Since I was so excited about the proof, I shared it with a couple of friends including Ivan Khatchatourian and Daniel Soukup. After seeing the proof Daniel asked the following question:

Question 1. Does Van der Waerden’s Theorem hold for ? In the simplest case, if the enemy colours the countable ordinals with finitely many colours, must there exist such that and all have the same colour?

After understanding what the question says, it is pretty obvious that the answer is “Yes”, because the natural numbers still get coloured, so we can use the original Van der Waerden’s theorem. Okay, so let’s fix the question so that it is not a corollary:

Question 2. If the enemy colours the countable ordinals with countably many colours, must there exist such that and all have the same colour?

There we go, now this is a problem.

It turns out (after some hemming and hawing) that the answer is “No”, there is a colouring of using countably many colours such that there are no “3 progressions” as described.

The “C”

Our original idea was actually to show that the theorem did hold using the pressing down lemma. This seemed plausible, and got us thinking about stationary and club sets. Eventually we stumbled on the following “problem club set” which turns out to give us the “bad” colouring.

Fact. There is a (“stretched out”) club subset such that if then . (In one sense C is “inaccessible from below”.)

There are many ways to get , the slickest is to take an chain of countable elementary submodels, and let , the submodels’ versions of .

If this gives you chills, you can instead take to be the collection of all limit ordinals that are limits of limits of limits of limits of … ( many times). This will also work.

Regardless of how you get such a , let’s show that there is a countable colouring on it that breaks Van der Waerden’s theorem.

The Colouring

Let’s colour all of the elements of with colour , and then for any , we know that the interval between and the next element of is countable, so colour the points in that interval in any injective way (without using the colour ).

Now we see that if we take any two elements and let be the minimum value of above both we get that so the colours of and must be different.