Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] It was a stupid question!!!!!!!!!! or...

Expand Messages
  • GASARCH
    On my last blog I asked the following: TRUE OR FALSE: For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same
    Message 1 of 1 , Nov 5, 2007
    • 0 Attachment
      On my last blog I asked the following: TRUE OR FALSE:
      For every coloring of R (the reals) with a countable number of colors there exists x,y,z,w of the same color such that x+y=z+w.


      And I pointed out that when I asked this in seminar I got 5 thought it was TRUE, 4 thought it was FALSE, 5 thought it was a STUPID QUESTION.

      The answer is: ITS A STUPID QUESTION. More rigorously the following is true and was proven by Erdos:
      The statment above is true iff the Continuum Hypothesis is false. (See this (pdf) or this (ps). for an exposition of the proof.


      SO, what to make of this? This is a natural question that is ind of ZFC. How Natural is it? Erdos worked on it, not some logician looking around for a problem to be ind of ZFC.

      Does this make us think CH is true or false? Actually, more is known:
      Let L(x1,..., xn) be a linear form over the reals (but not x1-x2). If CH is true then there is a coloring of the reals with a countable number of colors such that there is no e1,..., en which are all the same color such that L(e1,..., en)=0. (Exposition of proof in same document linked to above.)
      If CH is true then the entire theory of countable colorings and linear forms is known. And boring. If CH is false then much more interesting things happen. Jacob Fox proved the following:

      Let STAT(s) be the statement
      For every coloring of R with a countable number of colors there exists x1, x2, ..., x{s+3} such thatthey are all the same color, andx1 + sx2 = x3 + x4 + ... + x{s+3}
      THENSTAT(s) is true iff 20 > ℵs

      Jacob Fox is also (judging from his resume) not a logician. He is a combinatorist. Actually he's a graduate student so it may be too early to say what he is.

      To determine CH should we use its consequences as reasons for or against assuming it? Even if we do, do you want the entire theory to be known and boring? I ask this non-rhetorically. See Opinion 68 of Zeilberg's blog or The papers of Penelope Maddy: believing the axioms I. and believing the axioms II.

      --
      Posted By GASARCH to Computational Complexity at 11/05/2007 01:38:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.