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.
