We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:
Theorem: Suppose the complete graph on countably many vertices has its edges colored in one of colors. Then there is a monochromatic (i.e. an infinite subgraph all of whose edges are the same color).
The finite Ramsey theorem implies that there is a monochromatic for every positive integer , but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.
Given a non-principal ultrafilter on , any partition of into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in , and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on .