2-colorings of the reals - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:48:17Z http://mathoverflow.net/feeds/question/83579 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83579/2-colorings-of-the-reals 2-colorings of the reals Noah S 2011-12-16T00:14:24Z 2011-12-16T01:17:05Z <p>It's easy to prove that, if $\mathbb{R}$ is well-orderable, then there is a 2-coloring of pairs of reals with no uncountable homogeneous set, i.e., there is an $m: [\mathbb{R}]^2\rightarrow 2$ such that for all uncountable sets $U\subseteq\mathbb{R}$, there are $x, y, z\in U$ such that $m(\lbrace x, y\rbrace)\not=m(\lbrace x, z\rbrace)$.</p> <p>Proof: Let $&lt;_w$ be a well-ordering of $\mathbb{R}$, and let $m(\lbrace x, y\rbrace)=0$ if $x&lt; y\iff x&lt;_w y$ and $m(\lbrace x, y\rbrace)=1$ if $x&lt; y\iff y&lt;_w x$. Then a homogeneous set for $m$ yields a well-ordered increasing or decreasing sequence of reals with the same cardinality. But there is no uncountable increasing or decreasing sequence of reals, since the reals have a countable dense subset. So we are done.</p> <p>My question is, What happens if we don't assume that $\mathbb{R}$ is well-ordered? That is:</p> <p>Question 1: Does there exist a model of $ZF$ in which $\mathbb{R}$ is not well-orderable but there is a 2-coloring of $\mathbb{R}$ with no homogeneous set of the same cardinality as $\mathbb{R}$?</p> <p>A somewhat related question has to do with the complexity of colorings without nice homogeneous sets:</p> <p>Question 2: Does every Borel 2-coloring of pairs of reals have a Borel homogeneous set with the same cardinality as $\mathbb{R}$? Does every measurable 2-coloring of pairs of reals have a measurable homogeneous set with the same cardinality as $\mathbb{R}$?</p> http://mathoverflow.net/questions/83579/2-colorings-of-the-reals/83583#83583 Answer by François G. Dorais for 2-colorings of the reals François G. Dorais 2011-12-16T01:12:20Z 2011-12-16T01:17:05Z <p>Fred Galvin showed that if $c:[\mathbb{R}]^2\to\lbrace0,1\rbrace$ is such that $c^{-1}(0)$ and $c^{-1}(1)$ both have the Baire property, then there is a perfect set $P \subseteq \mathbb{R}$ which is $c$-homogeneous. (Note that perfect sets have size $2^{\aleph_0}$.)</p> <p>Since Borel sets have the Baire property and perfect sets are Borel, Galvin's Theorem answers your second question.</p> <p>Shelah has shown that it is relatively consistent with ZF+DC that every subset of any Polish space (like $[\mathbb{R}]^2$) has the Baire property. Galvin's proof seems to run in ZF+DC, so it looks like it is consistent that every $2$-coloring of $[\mathbb{R}]^2$ has a homogeneous set of size $2^{\aleph_0}$.</p> <p>I just realized that I misread your first question. The answer to that question is surely yes, but I don't have a handy model to show you right now. (I'll try to find one later.)</p> <p>By the way, if you want to color triples of reals, you can't always get a perfect homogeneous set. For triples, this is illustrated by the coloring <code>$$c(x,y,z) = \left\{\begin{array}{cc}0 &amp; \mbox{when }2y &lt; x+z \\ 1 &amp; \mbox{when }2y \geq x+z\end{array}\right.$$</code> where $x &lt; y &lt; z$. But Galvin showed that you can always get a perfect set whose triples assume at most two colors. Blass later showed that for colorings of $n$-tuples, you can always get a perfect set that takes on at most $(n-1)!$ colors and that this is best possible.</p>