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 NW(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 + 3 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 \aleph_0-colouring of the real numbers, there exist distinct numbers abcd 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 f : \mathbb{R} \to \mathbb{N} there are four distinct reals, abcd 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.

This entry was posted in Logic. Bookmark the permalink.

One Response to Colouring natural numbers, colouring real numbers

  1. Rowsety Moid says:

    I like things like this. Thanks for posting about it.

    I think Chris Freiling’s “Axioms of Symmetry: Throwing Darts at the Real Line” is fun in a similar way. It’s described succinctly in the e-mail quoted in the middle section of this page:

    http://consc.net/notes/continuum.html

Leave a Reply

Your email address will not be published. Required fields are marked *