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.

Adding ultrafilters

Leave a Reply Cancel reply