Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Why do you think that the axiom of choice is used in the proof? –  Carl Mummert Oct 6 '12 at 8:29
    
@Carl: Probably because (part of) it is used in both of the most common proofs. The slightly grubby one uses $AC_\omega$; the neat one uses $BPI$. –  Brian M. Scott Oct 6 '12 at 8:34
    
@Carl: For the same reason there are people who think the axiom of choice is involved in choosing a single element from an infinite set, perhaps. –  Asaf Karagila Oct 6 '12 at 9:16
    
Ramsey's theorem is equivalent to AC for countable families of finite sets: projecteuclid.org/… –  Shahab Oct 7 '12 at 3:31
add comment

4 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
@Carl Thanks for notifying me, I've missed that. I've left the answer anyway, since it might still be interesting for the OP. –  Martin Sleziak Oct 6 '12 at 8:34
    
!Martin: Thanks, I do think this is interesting, even though the original question was murky about why choice would be used to prove a result that follows from ZF. (+1) –  Carl Mummert Oct 6 '12 at 8:37
add comment

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.)

share|improve this answer
1  
To expand on the meaning of this: because the result is provable in $\mathsf{ACA}_0$, there is no need to use the axiom of choice at all in the proof, it will go through in ZF. –  Carl Mummert Oct 6 '12 at 8:27
add comment

The proof given here for the case $c=2$ uses only countable choice. The extension to arbitrary $c$ does not require choice.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.