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 mathbb{Z} . 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 omega_1 . 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 omega_1 ?

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 omega_1 ? In the simplest case, if the enemy colours the countable ordinals with finitely many colours, must there exist alpha, beta in omega_1 such that alpha, alpha + beta and alpha + 2 beta 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 alpha, beta in omega_1 such that alpha, alpha + beta and alpha + 2 beta 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 omega_1 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 C subseteq omega_1 such that if alpha, alpha + beta < c in C then alpha + 2 beta < c . (In one sense C is “inaccessible from below”.)

There are many ways to get C , the slickest is to take an omega_1 chain {C_alpha : alpha in omega_1} of countable elementary submodels, and let C := {C_alpha cap omega_1 : alpha in omega_1} , the submodels’ versions of omega_1 .

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

Regardless of how you get such a C , 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 C with colour 0 , and then for any c in C , we know that the interval between c and the next element of C is countable, so colour the points in that interval in any injective way (without using the colour 0 ).

The big things are elements of C
The big things are elements of C

Now we see that if we take any two elements alpha, alpha + beta in omega_1 and let c in C be the minimum value of C above both we get that alpha + 2beta < c so the colours of alpha + beta and alpha + 2 beta must be different.

This is the colouring.
This is the colouring.

2 thoughts on “Van der Waerden’s Theorem is false for $latex omega_1 $”

Comments are closed.