2-colorings of the reals - MathOverflow

2-colorings of the reals

2011-12-16T00:14:24Z

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)$.

Proof: Let $<_w$ be a well-ordering of $\mathbb{R}$, and let $m(\lbrace x, y\rbrace)=0$ if $x< y\iff x<_w y$ and $m(\lbrace x, y\rbrace)=1$ if $x< y\iff y<_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.

My question is, What happens if we don't assume that $\mathbb{R}$ is well-ordered? That is:

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}$?

A somewhat related question has to do with the complexity of colorings without nice homogeneous sets:

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}$?

Answer by François G. Dorais for 2-colorings of the reals

2011-12-16T01:12:20Z

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}$.)

Since Borel sets have the Baire property and perfect sets are Borel, Galvin's Theorem answers your second question.

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}$.

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.)

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 $$c(x,y,z) = \left\{\begin{array}{cc}0 & \mbox{when }2y < x+z \\ 1 & \mbox{when }2y \geq x+z\end{array}\right.$$ where $x < y < 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.