Proof of Ramsey Theorem with explicit use of AC

Question

What are minimal axiomatic requirements to prove Ramsey Theorem?

This one:

Let $X$ be some countably infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists some infinite subset $M$ of $X$ such that the size $n$ subsets of $M$ all have the same colour.

How to prove it explicitly using Countable Axiom of Choice?

Answer 1

EDIT: The question was about countably infinite set, not an infinite set, so this post does not answer the original question. I've decided to leave this answer here anyway, since it might still be interesting for the OP if he wants to know more relation of various versions of Ramsey Theorem to AC.

---

You can probably find some results about strength of Ramsey Theorem as a Choice Principle in Halbeisen's book Combinatorial Set Theory, Chapter 5, where several related Choice principles are mentioned.

A pdf-file with draft version of this book can be found at the website of the course on set theory he is teaching. (I'd say that version is very close to the final version, which was published.)

I'll quote some relevant results, proofs and more details can be found in the book.

$C(\aleph_0,\infty)$: Every countable family of non-empty sets has a choice function (this choice principle is usually called Countable Axiom of Choice).

RPP: If $X$ is an infinite set and $[X]^2$ is 2-coloured, then there is an infinite subset $Y$ of $X$ such that $[Y]^2$ is monochromatic.

Theorem 5.17. $C(\aleph_0,\infty)$ $\Rightarrow$ RPP $\Rightarrow$ KL $\Rightarrow$ $C(\aleph_0,n)$.

---

EDIT 2: After I learned that I originally wrote about a different version of the Ramsey theorem, I tried to check whether the same book mentions somewhere this version and - as expected, it does. Again, I've copied here some relevant parts, starting from p.11.

Ramsey proved his theorem in order to investigate a problem in formal logic, namely the problem of finding a regular procedure to determine the truth or falsity of a given logical formula in the language of First-Order Logic, which is also the language of Set Theory (cf. Chapter 3). However, Ramsey’s Theorem is a purely combinatorial statement and was the nucleus—but not the earliest result—of a whole combinatorial theory, the so-called Ramsey Theory. We would also like to mention that Ramsey’s original theorem, which will be discussed later, is somewhat stronger than the theorem stated below but is, like König’s Lemma, not provable without assuming some form of the Axiom of Choice (see Proposition 7.8).

Theorem 2.1 (Ramsey's theorem). For any number $n\in\omega$, for any positive number $r\in\omega$, for any $S\in[\omega]^\omega$, and for any colouring $\pi\colon{[S]^n}\to r$, there is always an $H \in [S]^\omega$ such that $H$ is homogeneous for $\pi$, i.e., the set $[H]^n$ is monochromatic.

The proof is done by first proving the case $n=2$:

Proposition 2.2. For any positive number $r\in\omega$, for any $S \in [\omega]^\omega$, and for any colouring $\pi \colon [S]^2 \to r$, there is always an $H \in [S]^\omega$ such that $[H]^2$ is monochromatic.

The proof uses Infinite Pigeon-Hole Principle, but it is only needed for countable infinite sets in this proof.

Infinite Pigeon-Hole Principle. If infinitely many objects are coloured with finitely many colours, then infinitely many objects have the same colour.

Answer 2

The proof given here uses only dependent choice.

Answer 3

This version of Ramsey's theorem is already provable in predicative second-order arithmetic $\mathsf{ACA_0}$. See Simpson's bible Subsystems of Second-Order Arithmetic, starting at p. 46, then in Ch III.7. (You can freely download the first chapter of SoSOA at http://www.math.psu.edu/simpson/sosoa/ which will explain what this means, if you are not familiar with the reverse mathematics programme.)

Answer 4

Martin gave an excellent answer, I would like to add a bit on his.

Indeed for a well-ordered set, no choice is needed to prove the Ramsey theorem. Countable sets are well-ordered. The proof is even constructive in the sense that we actually know what is the homogeneous set.

Let us see some examples of infinite sets who fail to have this property.

1. Suppose that $S$ is a Russell set, namely the union of a countable collection of pairs without a choice function. Formally we write $S=\bigcup_{n\in\mathbb N}S_n$ where $S_n$'s are pairwise disjoint sets of size $2$.

   Color now $S^{(2)}$ as follows: $c({x,y})=1$ if and only if for some $n$, $S_n=\{x,y\}$. If $Y$ was an infinite homogeneous subset of $Y$ then all the pairs from $Y$ would have the same color. It is clearly not $1$, because that would imply all the points in $Y$ are in the same pair. Therefore all the pairs in $Y^{(2)}$ are colored $0$ which means that no two points in $Y$ come from the same pair. However the defining property of $S$ was that no such $Y$ exists.

2. The trick above can easily extended for $n>2$ to any set which can be written as a union of a countable set of pairwise disjoint sets of size $n$.

3. Returning to the set $S$, let us see a non-obvious generalization for $n=3$. We color $S^{(3)}$ as follows: $c(\{a,b,c\})=1$ if and only if there is $n$ such that $S_n\subseteq\{a,b,c\}$.

   If $Y$ was an infinite homogeneous subset, it is clear that $Y$ cannot be colored $1$, suppose that $S_1,S_2$ and $S_3$ are all subsets of $Y$. Choose exactly one point from each of the three sets, $\{a_1,a_2,a_3\}$ it is clear that the color of this triplet is $0$. However if all triplets from $Y$ are colored $0$ then no two points are in the same pair (since you could have added any third point and you would get a triplet colored by $1$) and therefore $Y$ selects a point from infinitely many pairs, a contradiction again.

   This generalization can be carried out further using the same idea for larger $n$'s.