Warren Smith wrote:
I'll take you up on offer to send description of coloring & impossibility proof. This sounds incredible.
The 'if' and 'only if' parts of the proof are completely different, so I'll present them here as separate proofs. Don't publish these proofs anywhere, since the question is one of Imre Leader's problems for undergraduates at Trinity. NB: I've liberally assumed the Axiom of Choice everywhere, but that's okay because the statement of the continuum hypothesis doesn't even make sense without it (without AC, we can't compare the sizes of infinite sets). Introduction: 2-colouring of Q^2: --------------------------------- This isn't part of the proof of the main result, but it's a similar construction to the CH-dependent construction for R^3. Let's suppose we want to colour the points of Q^2 red or blue such that each row contains finitely many red points and each column contains finitely many blue points (Q = set of rationals). To do this, define an injection f: Q --> N (set of naturals), and colour a point red if f(x) <= f(y) and blue otherwise. Each row has finitely many red points, as there are only finitely many x for a given y such that f(x) <= f(y). Every column has finitely many blue points by symmetry. Theorem 1: continuum hypothesis ==> 3-colouring of R^3: ------------------------------------------------------- Let (x,y,z) be the coordinates of an arbitrary point in R^3. Let {a,b,c} be a permutation of (x,y,z), the details of which are given below. We define an injective (it may as well be bijective, but we only require injectivity) function f from the reals to the set of all countable ordinals (ordinals indexed by the first uncountable ordinal omega_1). Now, we assume without loss of generality that f(a) >= f(b) and f(a) >= f(c). We can do this since we haven't yet fixed the permutation. For fixed a, let g_a be an injection from the ordinals less than or equal to f(a) to the natural numbers (this can be done since f(a) is a countable ordinal). Now, we assume without loss of generality that g_a(f(b)) >= g_a(f(c)). Again, since we've only fixed a in the permutation, we're allowed to do this. We then colour the point (x,y,z) according to the following rules: * (x,y,z) is red if x = c, otherwise; * (x,y,z) is green if y = c, otherwise; * (x,y,z) is blue (and z = c, by process of elimination). I'll show that every line parallel to the x-axis contains finitely many red points, and the other cases follow by symmetry. Let's fix some y and z, and assume wlog that f(z) >= f(y). Now, a point is coloured red only if g_z(f(x)) <= g_z(f(y)). Note that g_z and f are injections, and g_z(f(y)) is a positive integer. There are only finitely many positive integers below g_z(f(y)) (trivially), so only finitely many values of x correspond to the point (x,y,z) being coloured red. Q.E.D. Theorem 2: ¬ CH ==> ¬ 3-colouring of R^3: ----------------------------------------- Assume there exists a subset V of R, which has cardinality strictly intermediate between |N| and |R|. Also assume there exists a 3-colouring of R^3, with the intention of deriving a contradiction. A 3-colouring of R^3 gives a 3-colouring of N x V x R, as N and V are subsets of R. Note that we can express V as a disjoint union of countable sets (proof: well-order V, and define an equivalence relation ~ such that x ~ y if one of (x,y) can be obtained from the other by applying the 'successor' operator finitely many times). A basic corollary of this is that |N x V| = |N x N x V/N| = |N x V/N| = |V| < |R|. Since every line parallel to the z-axis contains finitely many blue points, then there must be at most |N x N x V| = |V| blue points in total. As there are |R| > |V| planes parallel to the xy-plane, at least one of them (indeed, uncountably many!) must have no blue points whatsoever. So, we get a plane of the form N x V such that each row has only finitely many red points and each column has only finitely many green points. Since every line parallel to the y-axis contains finitely many green points, there must be at most |N x N| = |N| green points in total. However, there are |V| > |N| lines parallel to the x-axis, so at least one of them must contain no green points whatsoever, and thus be entirely red. Whence, we obtain a contradiction. By contraposition, we get that a 3-colouring of R^3 implies the continuum hypothesis. Sincerely, Adam P. Goucher http://cp4space.wordpress.com