Using Ultrafilters to Prove Ramsey-type Theorems

Abstract

Ultrafilters are a tool, originating in mathematical logic and general topology, that has steadily found more and more uses in multiple areas of mathematics, such as combinatorics, dynamics, and algebra, among others. The purpose of this article is to introduce ultrafilters in a friendly manner and present some applications to the branch of combinatorics known as Ramsey theory, culminating with a new ultrafilter-based proof of van der Waerden’s theorem.

MSC:

• Primary 05D10
• Secondary 03E75; 54D80

ACKNOWLEDGMENT

The author wishes to thank the two anonymous reviewers (whose careful reading and sound suggestions helped improve this paper nontrivially), and Fred Galvin for clarifying certain issues and providing some useful bibliographical pointers, especially regarding the history of the Galvin–Glazer argument. The author was supported by a postdoctoral fellowship from DGAPA–UNAM.

Notes

1 As a matter of fact, if one sees $\wp (X)$ as a Boolean algebra, equipped with the operations of union for joins, intersection for meets, and complement for negatives, then one can clearly see that the definition stated above is equivalent to defining an ultrafilter as the preimage of 1 under a Boolean algebra homomorphism $\wp (X)\to \{0,1\}$.

2 The author first came in contact with this nonstandard definition in a set of notes by Andreas Blass.

3 Throughout this article we consider colorings with only two colors in order to simplify matters, since for the problems that we study here this does not make a difference, and the same arguments work with any finite number of colors. However, the reader should be warned that this is not the case in certain contexts, as there are examples of Ramsey-type properties that are true for 2-colorings but fail for arbitrary finite colorings [4]. As a particularly striking recent example, for every coloring of $\mathbb{N}$ with two colors, there are infinitely many monochromatic solutions to the Diophantine equation $x+y=z^2$, whereas there exists a coloring of $\mathbb{N}$ with three colors such that no nontrivial solution to the same equation can be monochromatic [11].

4 The reader interested in delving deep into the development of this theory can consult [17], or, for a rather compact, but complete, exposition of all the tools used in this article, see [24, Section 2.1, pp. 27–30].

5 Technically, the condition needed on the semigroup X is that for every finite $F\subseteq X$ and for every infinite $A\subseteq X$ there are finitely many $a_1,\dots ,a_n\in A$ such that the set $\{x\in X|a_i*x\in F\mathrm{ }\text{for}\mathrm{ }\text{all}\mathrm{ }i\}$ is finite.

6 The story, as presented here, seems to agree with Galvin’s own recollections, as verified by the author through personal communication.

7 There is also a proof of Hindman’s theorem, based on tools from topological dynamics, due to Furstenberg and Weiss [8].

8 As noted before, an interested reader can consult [24, Section 2.1, pp. 27–30] for a short but complete account of all the results mentioned here, or look into [17] for a more extensive treatment.

9 A closed left ideal of S is a closed subset $I\subseteq S$ satisfying $x*y\in I$ whenever $x\in S$ and $y\in I$.

Additional information

Notes on contributors

David J. Fernández-Bretón

David Fernández-Bretón received his Ph.D. from York University in 2015. He is currently an assistant professor at Instituto Politécnico Nacional in Mexico City, after having held postdoctoral positions at the University of Michigan, the University of Vienna, Cinvestav, and Universidad Nacional Autónoma de México.

Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, Coyoacán, 04510, CDMX, Mexico Current address: Escuela Superior de Física y Matemáticas, Instituto Politécnico Nacional, Col. San Pedro Zacatenco, Alcaldía Gustavo A. Madero, 07738, CDMX, Mexico. [email protected]