= Solution
An <ultrafilter> on $\mathbb N=\{1,2,\ldots\}$ is a family $p\subseteq\mathcal P(\mathbb N)$ satisfying the proper <filter> axioms: $\mathbb N\in p$, $\varnothing\notin p$, <closure> under finite <intersections>, and upward <closure> under inclusion. In addition, for every $A\subseteq\mathbb N$, exactly one of $A$ and $A^c$ belongs to $p$. Equivalently, an <ultrafilter> is a maximal proper <filter>. The <principal ultrafilter> at $n$ consists of all <subsets> containing $n$; an <ultrafilter> not of this form is a <nonprincipal ultrafilter>.
To prove existence, start with the <cofinite filter> and order the proper <filters> containing it by inclusion. The <union> of a chain is still a proper <filter>: finitely many of its members lie in one <filter> of the chain, and no constituent contains the empty <set>. Thus <Zorn lemma> supplies a maximal such <filter> $p$. If $A\notin p$, adjoining $A$ cannot generate a proper <filter>; otherwise maximality fails. Consequently some $B\in p$ has $B\cap A=\varnothing$, so $A^c\in p$ by upward <closure>. This proves the <ultrafilter> alternative. No finite $A$ can belong to $p$, because $A^c$ is <cofinite> and already belongs to $p$. In particular $p$ contains no singleton and is a \b[<nonprincipal ultrafilter>]. The same argument, starting from any proper <filter>, proves the <ultrafilter lemma> used below.
Define $\beta\mathbb N$ to be the <set> of all <ultrafilters> on $\mathbb N$, with basic <open sets>
$$
\widehat A=\{p\in\beta\mathbb N:A\in p\},\qquad A\subseteq\mathbb N.
$$
They form a <topological basis> because $\widehat{\mathbb N}=\beta\mathbb N$ and $\widehat A\cap\widehat B=\widehat{A\cap B}$. Moreover $(\widehat A)^c=\widehat{A^c}$, so they are <clopen sets>. This is the <compact Hausdorff topology on ultrafilters>. If $p\ne q$, some $A$ belongs to $p$ but not $q$, and then $\widehat A$ and $\widehat{A^c}$ are disjoint open <neighbourhoods> of the two points. Thus $\beta\mathbb N$ is <Hausdorff>.
For <compactness>, take an <open cover> and refine it by basic <open sets> $\widehat{A_\lambda}$. If no finite subfamily covers, then for every finite collection of indices the <intersection> $\bigcap A_\lambda^c$ is nonempty. Indeed, if that <intersection> were empty, the corresponding $A_\lambda$ would cover $\mathbb N$, and every <ultrafilter> would contain at least one of them by the finite <ultrafilter> alternative. The complements therefore have the <finite intersection property> and generate a proper <filter>. Extend it to an <ultrafilter> $q$ by the proved <ultrafilter lemma>. Then $A_\lambda^c\in q$ for every $\lambda$, so $q$ belongs to none of the covering $\widehat{A_\lambda}$, a contradiction. A finite basic subcover lies inside a finite subcover of the original cover. Hence
$$
\boxed{\beta\mathbb N\text{ is compact and Hausdorff}.}
$$
The map $n\mapsto p_n$, where $p_n$ is the <principal ultrafilter> at $n$, identifies the discrete natural numbers with a <dense subset>: any nonempty $\widehat A$ has $A\ne\varnothing$ and contains $p_n$ for $n\in A$.
<Hindman theorem> states that every <finite colouring> of the positive <integers> admits an increasing <sequence> $x_1<x_2<\cdots$ whose <finite-sums set>
$$
FS(x_1,x_2,\ldots)=\left\{\sum_{i\in F}x_i:\varnothing\ne F\subseteq\mathbb N\text{ finite}\right\}
$$
is <monochromatic>. We now give the <Idempotent-ultrafilter proof of Hindman's theorem>. For $A\subseteq\mathbb N$, write $A-x=\{y\in\mathbb N:x+y\in A\}$. The addition on $\beta\mathbb N$ is defined by
$$
A\in p+q\quad\Longleftrightarrow\quad\{x\in\mathbb N:A-x\in q\}\in p.
$$
Take an <idempotent ultrafilter on the natural numbers> $p$, whose existence is allowed, so $p+p=p$. It is a <nonprincipal ultrafilter>: addition of principal points is $p_m+p_n=p_{m+n}$, whereas no positive <integer> satisfies $2m=m$.
Exactly one <colour class> $A$ belongs to $p$. Define
$$
A^*=A\cap\{x:A-x\in p\}.
$$
By idempotence, $A^*\in p$. The <idempotent-ultrafilter star-set lemma> needed for the recursion is that $A^*-x\in p$ whenever $x\in A^*$. To prove it, put $D=A-x\in p$. Idempotence again gives
$$
D^*=D\cap\{y:D-y\in p\}\in p.
$$
For $y\in D^*$, we have $x+y\in A$ and $A-(x+y)=D-y\in p$, hence $x+y\in A^*$. Thus $D^*\subseteq A^*-x$, proving the lemma by upward <closure>.
Choose $x_1\in A^*$. Suppose $F_n=FS(x_1,\ldots,x_n)\subseteq A^*$ has been constructed. Every factor of
$$
A^*\cap\bigcap_{s\in F_n}(A^*-s)\cap\left\{z:z>\sum_{i=1}^nx_i\right\}
$$
belongs to $p$: the translate factors do by the just-proved lemma, and the last factor does because it is <cofinite> and $p$ is a <nonprincipal ultrafilter>. The finite <intersection> is therefore nonempty. Choose $x_{n+1}$ in it. Then $x_{n+1}$ and every $s+x_{n+1}$ with $s\in F_n$ lie in $A^*$, so $F_{n+1}\subseteq A^*$. This constructs a strictly increasing <sequence>, indeed $x_{n+1}>\sum_{i\le n}x_i$, and proves <Hindman theorem>.
Finally apply <Hindman theorem> to obtain a <monochromatic> <finite-sums set> $FS(y_1,y_2,\ldots)$. We construct a <divisibility chain inside a finite-sums set> using disjoint successive blocks of indices. Start with $x_1=y_1$. If $x_i=m$, take $2m$ unused terms after all indices used so far, and split them into two groups of $m$ consecutive terms. In each group its $m+1$ <partial sums>, including $0$, contain two in the same <congruence class> modulo $m$ by the <pigeonhole principle>. Their difference is a nonempty consecutive sum divisible by $m$, and positivity makes it at least $m$. Let $x_{i+1}$ be the sum of these two selected sums. Then $m\mid x_{i+1}$ and $x_{i+1}\ge2m>m$.
The index <set> defining $x_{i+1}$ lies strictly after all previous index <sets>. Discard the other terms in these two groups before continuing. Because the chosen index <sets> are disjoint, every finite sum of distinct $x_i$ is a finite sum of distinct $y_j$, retaining the same colour. Therefore
$$
\boxed{x_1<x_2<\cdots,\qquad x_i\mid x_{i+1}\ \text{for every }i,\qquad FS(x_1,x_2,\ldots)\text{ is monochromatic}.}
$$
Back to article page
