Ultrafilter quantifiers and Hindman’s theorem

A filter on \mathbb N is a consistent notion of largeness for subsets of \mathbb N. “Largeness” has the following properties.

  • if A is large and A \subseteq B then B is large
  • if A and B are large then A \cap B is large
  • the empty set is not large

At most one of A and A^\text{c} is large; an ultrafilter is a filter which always has an opinion about which it is.

  • either A or A^\text{c} is large

The usual notation for “A is large” is A \in \U, where \U is the ultrafilter. This casts ultrafilters as sets, rather than notions of largeness. To bring the notion of largeness to the foreground we can use ultrafilter quantifiers; we write \U(x)\ A(x), read “for \U-most x, A(x) holds” (where we have also identified A with the predicate “is a member of A“).

  • if \U(x)\ \phi(x) and \phi \implies \psi then \U(x)\ \psi(x)
  • if \U(x)\ \phi(x) and \U(x)\ \psi(x) then \U(x)\ \phi(x) \wedge \psi(x)
  • \forall x\ \phi(x) \implies \U(x)\ \phi(x) \implies \exists x\ \phi(x)
  • \neg [\U(x)\ \phi(x)] \iff \U(x)\ \neg \phi(x)

From this point of view \forall x\ \phi(x) says that the set of elements with property \phi is everything, and \exists x\ \phi(x) that the set of elements with property \phi is non-empty. \U behaves like a mixture of \forall and \exists, with the considerable advantage that logical operations pass through \U unchanged without having to worry about De Morgan’s laws.

Adding ultrafilters

It turns out that the set of ultrafilters on \mathbb N is a model for the Stone–Čech compactification \beta \mathbb N of (\mathbb N, +). \mathbb N is embedded as the set of principal ultrafilters (“A is large if and only if n \in A“), and the addition on \mathbb N extends to \beta \mathbb N:

    \[\U + \V = \{A : \{x : A-x \in \V\} \in \U\}.\]

(Here A-x should be interpreted as (A-x) \cap \mathbb N.) But to use this addition with quantifiers all we need to know is that (\U+\V)\ \phi(x) \iff \U(x)\ \V(y)\ \phi(x+y). If you can see that from the first definition then your brain is wired differently from mine.

It is a fact that there exist idempotent ultrafilters, with \U + \U = \U. Given such a \U, we can play the following game. Suppose that \U(x)\ \phi(x). Then (\U+\U)(x)\ \phi(x), so \U(x)\ \U(y)\ \phi (x+y) and therefore \U(x)\ \U(y)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y) (by ANDing with the original assertion, and the original assertion with the dummy variable x replaced by y). In particular, \exists x\ \U(y)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y). But now we can fix a good choice of x and repeat the whole process with \psi(y) = \phi(x) \wedge \phi(y) \wedge \phi (x+y) in place of \phi to get that

    \[\exists x\ \exists y\ \U(z)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y) \wedge \phi(z) \wedge \phi(x+z) \wedge \phi(y+z) \wedge \phi (x+y+z).\]

Iterating, we eventually obtain an infinite sequence x_1, x_2, \ldots such that \phi holds for every sum of finitely many of the x_i. Together with the observation that whenever \mathbb N is finitely coloured exactly one of the colour classes is \U-large this proves Hindman’s theorem, that we can always find an infinite sequence x_1, x_2, \ldots such that every sum of finitely many terms has the same colour.

A version of this argument with more of the details filled in is on the Tricki.

Leave a Reply

Your e-mail address will not be published.