Proving Infinite Ramsey's theorem

Question

I am looking for a proof of the infinite Ramsey theorem which uses the finite Ramsey's theorem. I have been unable to find such a proof. Does there exist such a proof? If so, where can I find it.

Answer 1

According to these notes (PDF) by Arnie Miller, the infinite Ramsey theorem is not a corollary of the finite Ramsey theorem.

Answer 2

The infinite Ramsey theorem is not any kind of easy corollary of the finite version. This is true in several senses, The most trivial one is that we understand both theorems very well, and there is no known proof of the infinite theorem from the finite one that is genuinely simpler than just proving the infinite theorem from scratch. (There is a proof of the finite theorem from the infinite one, using compactness.)

It would actually be remarkable if there were a relationship. The finite Ramsey theorem, in a sense, is entirely a result about natural numbers. But the infinite Ramsey theorem is about infinite sets of numbers. So we cannot directly represent an instance of the infinite Ramsey theorem as an instance of the finite Ramsey theorem, which blocks the most naive kind of proof.

Another way to see that the infinite theorem is stronger is to ask how difficult it is to construct solutions. For the finite Ramsey theorem, we can find the finite homogeneous set that is constructed in the theorem by just searching for it. It may take a long time, but if all we have to do is search the powerset of a finite set, we can eventually do it.

On the other hand, it is known that there are instances of the infinite Ramsey theorem in which the coloring itself is computable but there is no computable homogeneous set. This means that, for these instances, given any $k$-tuple of numbers, we can tell what color is assigned to that $k$-tuple by using some fixed algorithm, but there is no algorithm that will compute an infinite homogeneous set.

What this computability result tells us is that we cannot prove the infinite version from the finite version by induction alone. If we imagine a hypothetical world in which every set of naturals is computable, this world would satisfy every induction axiom for the naturals, and would satisfy the finite Ramsey theorem, but it would not satisfy the infinite Ramsey theorem (this claim can be stated rigorously and proved). So the infinite Ramsey theorem requires stronger set existence axioms, while the finite Ramsey theorem does not.

A similar phenomenon happens with many Ramsey-type combinatorial theorems: the infinite version is often far stronger than the finite version. There are at least three kinds of Ramsey-type theorems:

1. If we have a target size for a desired kind of structure, then all finite colorings of sufficiently large initial segments of the naturals contain a monochromatic structure of the target size. Examples: the finite Ramsey theorem, or van der Waerden's theorem.

2. All finite colorings the the set of natural numbers contain arbitrarily large (finite) monochromatic structures of the desired kind. Examples: Folkman's theorem, or a corollary of Szemerédi's theorem

3. All finite colorings of the set of natural numbers contain an infinite monochromatic structure of the desired kind. Examples: Hindman's theorem, or the infinite Ramsey theorem.

As a rule of thumb, each type of theorem has as a corollary a theorem of the type before it. But in general it is not possible to strengthen a theorem of one type to easily prove the corresponding theorem of the next type - assuming the theorem of the next type is even true. For example, it is not possible to extend Szemerédi's theorem to produce infinite monochromatic arithmetical progressions, because that generalization is false.