MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Since infinite partition relation take place outside of $AC$ (the optimum result seems to be offered by the Erdös-Rado Theorem), $AD$ might be useful to establish infinite partition relations with uncountable homogeneous sets on $\mathbb{R}$. But I might completely be off... – Carlo Von Schnitzel Dec 16 '11 at 1:09
up vote 15 down vote accepted

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.

share|cite|improve this answer
I'm still interested in the answer to my first question, but I suspect that you're right, that the answer is yes. – Noah Schweber Jan 11 '12 at 23:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.