Generalisation of infinite Ramsey's theorem to countably infinite or variable edge arities

Question

The usual statement of the infinite Ramsey's Theorem, as appears e.g. in Wikipedia page on Ramsey's Theorem is (paraphrasing slightly):

If $X$ is an infinite set, and $C$ is a finite set, and $n$ is a finite number, and we colour the $n$-element subsets of $X$ with colours from $C$, then $X$ has an infinite monochromatic subset $M$, meaning that every $n$-element subset of $M$ has the same colour.

My questions are:

1. Is there a generalisation to the case where n is infinite, e.g. if $n$ is $ω$ and we are colouring countably infinite subsets of $X$ (we may need to assume that $X$ is much larger than countably infinite)?

2. Is there a generalisation to the case where we fix a finite range $1\leq n'\leq n\in\mathbb N$ and colour subsets of $X$ whose size is no less than $n'$ and no greater than $n$ (instead of subsets of $X$ whose size is precisely $n$)?

Answer 1

For part $2$, the answer is yes. You can ensure this inductively: Say you are coloring all $n'$-sized subsets of $X$ for $1\le n'\le n$. First, extract from $X$ an infinite subset $X_1$ with all $1$-element subsets of the same color. Now extract from $X_1$ an infinite subset $X_2$, all of whose $2$-element subsets have the same color, and so on.

(Note we cannot ensure for $i\ne j$ that the color of the $i$-element sets is the same as the color of the $j$-element sets. This is simply not possible, as our coloring may explicitly depend on the size of the set being colored.)

Ramsey's theorem admits strengthenings where the homogeneous set (the set $M$ in the notation from the question) is uncountable. For each specific uncountable cardinal $\kappa$ and $n>0$ there is a cardinal $\lambda$ such that any coloring of the $n$-sized subsets of a set of size $\lambda$ admits a homogeneous set of size $\kappa$. The cardinal $\lambda$ is typically larger than $\kappa$. Inductively we see that, picking $\lambda$ large enough, we can ensure the generalization of $2$ to hold as well, we just need the sets $X_1,\dots$ as above to each be large enough, and the precise size can be computed easily.

One could ask about the more general question of coloring, for all positive $n\in \mathbb N$, all $n$-sized subsets and asking for a set simultaneously homogeneous for all $n$. The argument above would not work (there are no infinite decreasing sequences of cardinals under the axiom of choice). However, these versions still hold, as long as we admit the existence of certain large cardinals (the set $X$ we begin with must indeed be very large).

For part $1$ the answer is no. The axiom of choice is needed here. That it is not possible to have a Ramsey's theorem for $\omega$-tuples is a result of Erdős and Rado, see

MR0065615 (16,455d). Erdős, P.; Rado, R. Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc. (3) 2, (1952). 417-439.

Given a set $X$, consider a well-ordering $<$ of the collection $[X]^{\aleph_0}$ of countable subsets of $X$, and color a subset $A$ with color $0$ if $A$ is the $<$-smallest member of $[A]^{\aleph_0}$ and with color $1$ otherwise. If there is an infinite homogeneous set $H$ for this coloring, one quickly reaches a contradiction: If $A$ is the $<$-smallest member of $[H]^{\aleph_0}$ (which exists, since $<$ is a well-ordering), then $A$ has color 0 (by definition) so, since $H$ is homogeneous, any countable subset of $H$ has color 0. Now, if $B\subset C$ are both countable infinite subsets if $H$, we have $C<B$ since $C$ has color 0, so it is the $<$-smallest member of $[C]^{\aleph_0}$. But we can easily find an increasing sequence $A_0\subset A_1\subset\dots$ of countable infinite subsets of $H$. This gives us a decreasing sequence $A_0>A_1>\dots$ in the well-ordering.

Note that the proof gives the strongest possible negative result: The original set $X$ can be as large as you want, and we are only coloring the countable subsets of $X$ (one could imagine coloring larger infinite subsets; but if there is a Ramsey's theorem for such a version, one easily derives from it a Ramsey's theorem for countable infinite subsets), and we are only looking for a countable homogeneous set.

That choice is needed is a consequence of results of Mathias that shows that in Solovay's model where all sets of reals are Lebesgue measurable, Ramsey's theorem holds for colorings of the countable infinite subsets of $\mathbb N$, see

MR0491197 (58 #10462). Mathias, A. R. D. Happy families. Ann. Math. Logic 12 (1977), no. 1, 59–111.

There is some pretty and interesting combinatorics of versions of Ramsey's theorem for colorings of infinite subsets in the absence of choice and particularly in the context of the axiom of determinacy. These results are also closely connected to the theory of large cardinals.