# Does a red/blue coloring of the infinite subsets of $\mathbb{N}$ necessarily give an infinite monochromatic $M\subset \mathbb{N}$?

The infinite Ramsey theorem states that for any $n$, if all the subsets of $\mathbb{N}$ of size $n$ are colored red/blue, then there is an infinite $M$ all of whose subsets of size $n$ are monochromatic.

My question is whether there is an analogue if the infinite subsets of $\mathbb{N}$ are coloured red/blue--does this imply that there is an infinite subset $M$ all of whose infinite subsets are monochromatic?

• Could you be more specific? Let $P_\infty(X)$ denote the set of infinite subsets of $X$. I assume we are given a map $f\colon P_\infty(\mathbb N)\to\{r,b\}$ and the question is whether there exists $M\in P_\infty(\mathbb N)$ such that $f|_{P_\infty(M)}$ is constant? – Hagen von Eitzen Jan 20 '13 at 16:50
• I meant exactly what you wrote. – Spook Jan 20 '13 at 17:01

Define an equivalence relation on infinite subsets of $\mathbb N$:

$A \equiv B \iff |A \Delta B| \text{ is finite}$

From each class select a representative, using the axiom of choice:

$f: \mathcal{P}^{\infty}(\mathbb N)/_{\equiv} \to \mathcal{P}^{\infty}(\mathbb N)$ such that $f(x)\in [f(x)]_{\equiv}$.

Define a coloring: $A$ is blue iff $|A \Delta f([A])|$ is even.

If a set $M$ is blue (red), then after removing a single element it changes color, which means there is no $M$ monochromatic in your sense.

No. In fact, you cannot guarantee an infinite monochromatic subset, even if you start with an infinite uncountable set. This result was first shown by Erdős and Rado, and uses the axiom of choice in an essential way:

Let $X$ be infinite, and fix a well-ordering $\prec$ of $[X]^{\aleph_0}$, the collection of countably infinite subsets of $X$. Now, given a countably infinite subset $A$ of $X$, if $A$ is $\prec$-smaller than all elements of $[A]^{\aleph_0}\setminus\{A\}$, color $A$ red. Otherwise, color $A$ blue.

We check that this coloring has no infinite monochromatic subset. In effect, given $H$ infinite such that all sets in $[H]^{\aleph_0}$ have the same color, this color must necessarily be red: Consider the $\prec$-least element $H_0$ of $[H]^{\aleph_0}$.

But this is a problem: Suppose $A\subset B$ are elements of $[H]^{\aleph_0}$. Since the color of $B$ is red, it follows that $B\prec A$. Now, we can easily find an increasing sequence of countably infinite subsets of $H$: $$C_0\subset C_1\subset C_2\subset\dots\subset H.$$ But then $\dots\prec C_2\prec C_1\prec C_0$ is an infinite descending sequence in the well-ordering $\prec$, a contradiction.

That choice is essential can be observed by noticing that your question has a positive answer in certain models of $\mathsf{ZF}$. For example, a positive answer holds in Solovay's model where all sets of reals are measurable (this was first proved by Mathias), and it also holds in all natural models of determinacy. In fact, the study of infinitary partition relations plays a significant role in the combinatorics of models of determinacy.

The reason that the result holds in these models but fails under choice can be explained by noticing that we get homogeneous sets if we restrict ourselves to "nicely definable" partitions. The first result in this direction is the Galvin-Prikry theorem: $[\mathbb N]^{\aleph_0}$ can be identified with a subset of the Cantor set (identifying sets with characteristic functions). This identification gives it a Polish structure. In terms of this topology, as long as $[\mathbb N]^{\aleph_0}$ is partitioned into finitely many Borel pieces, we can find infinite homogeneous sets.

This theorem was later generalized and explained by using Mathias argument as a template. This led to the notion of the Ellentuck topology. It turns out that a partition of $[\mathbb N]^{\aleph_0}$ admits an infinite homogeneous set as long as the pieces of the partition have the Baire property in the Ellentuck topology. Borel sets in the standard topology are Borel in this topology, and Borel sets have the Baire property, so this generalizes the Galvin-Prikry theorem. Also, in Solovay's model and natural models of determinacy, all partitions have this property. Kechris's book "Classical descriptive set theory" has a nice proof of these results.

An annoying open problem that remains is whether determinacy itself proves the infinitary version of Ramsey's theorem. The result holds in all known models of determinacy, and it is a consequence of $\mathsf{AD}^+$, a technical strengthening of determinacy for which it is still open whether it is indeed strictly stronger than determinacy. Similarly, we do not know what its consistency strength is: The infinitary version holds in Solovay's model, for which we require an inaccessible cardinal. But we do not know whether the inaccessible is needed.

• It may be useful for some readers to emphasize that you wrote "natural models of determinacy". As far as I know, it's still an open problem whether the infinitary partition relation can be deduced from AD. – Andreas Blass Jan 20 '13 at 21:28
• Hi Andreas. Yes, this is still open. We also do not know whether it requires an inaccessible consistency-wise. – Andrés E. Caicedo Jan 20 '13 at 21:29

It's easy to construct a counterexample using transfinite recursion. Fix a well-ordering of least possible order type of the infinite subsets of $\Bbb{N}$. Now go down this list, at each step making sure that the listed set has both a red subset and a blue subset. Since at each step you have fixed the colour of $< 2^{\aleph_0}$ sets, and each infinite subset of $\Bbb{N}$ has $2^{\aleph_0}$ infinite subsets, there are always plenty of sets to choose from.

• This construction seems much simpler than the other two. Did you come up with it yourself? – Ari Brodsky Jan 21 '13 at 3:12
• Yes. This sort of thing is very easy if you're at all familiar with transfinite recursion. – Chris Eagle Jan 21 '13 at 10:25
• Interesting that your answer relies on the cardinality of $\mathbb N$, which the other answers don't. Your answer extends to sets up to size $\mathfrak c$, but not larger. I still like your answer, nevertheless. – Ari Brodsky Oct 1 '13 at 17:56
• @AriBrodsky More or less the same construction works for sets of any size. Let $X$ be any set. Well-order the countably infinite subsets of $X$. When you come to a countably infinite set $M$, if some subset of $M$ has been colored, do nothing; if no subset of $M$ has been colored, then color $M$ red; pick a proper subset of $M$ and color it blue; pick a proper subset of that and color it red; and so on. – bof Oct 4 '13 at 9:45