Colouring natural numbers, colouring real numbers

If you have lots of objects lined up in a row, and only a relatively small palette of colours to paint them with, then you’ll expect to be able to find some patterns lurking in any colouring of the objects.

Here’s a famous and lovely combinatorial theorem to that effect due to Van der Waerden.

For any r and k, there is an N big enough so that, however the numbers 1, 2, 3, … N are coloured with r colours, there will be an monochromatic arithmetic progression of numbers which is k long.

For example, suppose you have r = 7 colours, and put k = 4, then there is a number N = W(7, 4) such that, it doesn’t matter how you colour the first N or more positive integers with 7 colours, you’ll find an arithmetical sequence of numbers a, a + e, a + 2e, a + 3e  which are all the same colour. As is so often the way with numbers that crop up in this sort of combinatorics, no one knows how big W(7, 4) is: the best published upper limit for such numbers is huge.

Here’s a simple corollary of  Van der Waerden’s theorem (take the case where k = 4, and remark that  a + a + 3e  = a + e + a + 2e)

For any finite number of colours, however the positive integers are coloured with those colours, there will be distinct numbers a, b, c, d the same colour such that a + d = b + c.

So far so good. But now let’s ask: does this still hold if instead of considering a finite colouring of the countably many positive integers we consider a countable colouring of  the uncountably many reals? In other words, does the following claim hold:

(E) For any $latex \aleph_0$-colouring of the real numbers, there exist distinct numbers a, b, c, d the same colour such that a + d = b + c.

Or since a colouring is a function from objects to colours (or numbers labelling colours) we can drop the metaphor and rephrase (E) like this.

(E*) For any function $latex f : \mathbb{R} \to \mathbb{N}$ there are four distinct reals, a, b, c, d such that f(a)  = f(b) = f(c) = f(d), and a + d = b + c.

So is (E*) true? Which, you might think,  seems a natural enough question to ask if you like combinatorial results and like thinking about what results carry over from finite/countable cases to non-countable cases. And the question looks humdrum enough to have a determinate answer.   No?

Yet Erdős showed that (E*) can’t be proved or disproved by ZFC. Why so? Because (E*) turns out to be equivalent to the negation of the Continuum Hypothesis. Which is surely a surprise. At any rate,  (E*) is the most seemingly humdrum proposition I’ve come across, a proposition not-obviously-about-the-size-of-sets, that is independent of our favourite foundational theory.

Make of that what you will! — but I just thought it was fun to spread the word. You’ll learn more, and be able to follow up references, in an arXiv paper by Stephen Fenner  and William Gasarch here.