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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.