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 .
The standard proof
Pick a vertex . By infinite pigeonhole, there exists a color such that has infinitely many neighbors of color ; call these neighbors . Pick a vertex . Again by infinite pigeonhole, there exists a color such that has infinitely many neighbors in of color ; call these neighbors . And so forth. By induction we define a sequence of vertices such that the edge has color for all . By a final application of infinite pigeonhole, infinitely many of the colors are the same, so we are done.
I was worried about whether this proof uses some form of dependent choice, but it does not; one only has to put a total order on the set of colors, and at each step where we invoke infinite pigeonhole we can take the unique infinite subset with minimal color.
This proof is substantially the same as the above proof, but I think it’s a nice application of ultrafilters nonetheless.
Fix a non-principal ultrafilter on the vertex set of . The coloring on the edges of give a coloring of the vertices as follows: to each vertex we associate a partition of the remaining vertices by the color of the corresponding edges, so exactly one of the blocks of this partition is in , corresponding to the color . In probabilistic terms, is adjacent to an edge of color almost surely.
The colors define a partition of the vertex set, and exactly one of the blocks is in , corresponding to some color . In probabilistic terms, is (adjacent to an edge of color almost surely) almost surely. But now it is straightforward to define by induction a sequence of vertices all connected to each other by an edge of color .
Of course, this proof can be carried out without the ultrafilter , but it’s interesting to see how the ultrafilter encodes the infinitely many choices one would have to make if one did not place a total order on the set of colors.
The finite Ramsey theorem
Recall that the finite Ramsey theorem says the following.
Theorem: Fix positive integers . There exists a positive integer such that, if the edges of are colored with colors, there is a monochromatic .
Proof. Suppose there are for which the theorem is false. Then for every positive integer , there exists a coloring of the edges of by colors with no monochromatic . These colorings can be described as functions where and is the set of subsets of of size . We will use these colorings to construct a coloring of the edges of by colors with no monochromatic , which contradicts the infinite Ramsey theorem.
We do this as follows. Let be a non-principal ultrafilter on . Our graph will have vertex set , the quotient of by the equivalence relation if ; in probabilistic terms, if almost surely. There is also an edge from to of color if ; in probabilistic terms, if is connected to by an edge of color almost surely. This construction is known as an ultraproduct in logic and model theory. It is not hard to see that the resulting graph is indeed a equipped with a -coloring on its edges. This follows from Łoś’s theorem, although it is not hard to see directly.
Consider an -element subset of ; for concreteness consider representatives of its elements. This subset is monochromatic if and only if almost all of the graphs are monochromatic, but by assumption this does not occur. (This also follows from Łoś’s theorem.) Hence does not have a monochromatic , and this contradicts the infinite Ramsey theorem.
Of course this proof is completely nonconstructive! Nevertheless, I think it is valuable to know that ultraproducts provide a machinery for automatically constructing infinitary results to nonconstructive but finitary ones. There is a post by Terence Tao discussing similar applications of ultraproducts as the one above; we will have more to say about ultraproducts in a later post. One can also regard the above argument as an application of the compactness theorem for first-order logic; we will also have more to say about this in a later post.