Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 9 / 3

A proper filter on a set $\mathcal{F}$ on $\mathbb{N}$ contains $\mathbb{N}$, excludes the empty set, is closed under finite intersections and is upward closed under inclusion. An ultrafilter is a maximal proper filter. Equivalently, for every $A\subseteq \mathbb{N}$ it contains exactly one of $A,A^c$. To see maximality implies this dichotomy, if $A$ is absent then adjoining it must make the generated filter improper; hence some filter member is disjoint from $A$, forcing $A^c$ into the filter. Conversely, a filter with this dichotomy cannot be properly enlarged without acquiring disjoint members.

Extend the cofinite filter to a maximal proper filter using Zorn's lemma. Every chain of proper extensions has its union as a proper filter upper bound: any finite collection of its members lies in one member of the chain, and the empty set never enters. The resulting ultrafilter contains no finite set, because it already contains that set's cofinite complement. It is therefore a free ultrafilter, or nonprincipal ultrafilter. This proves the required existence with the usual choice principle explicit.

Define the Stone-Čech compactification of the natural numbers as the set of all ultrafilters, with basic open setsThey form a basis because $\hat{\mathbb{N}}$ is the whole space and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Also $(\hat{A}{)}^c=\widehat{A^c}$, so each basic set is clopen. Distinct ultrafilters disagree on some $A$, putting them in the disjoint open sets $\hat{A}$ and $\widehat{A^c}$. Thus this space is Hausdorff.

To prove compactness, suppose an open cover has no finite subcover and refine it by basic sets $\widehat{A_i}$. Their complements $B_i=\mathbb{N}\setminus A_i$ have the finite intersection property: otherwise finitely many $\widehat{A_i}$ would cover every ultrafilter. Here a nonempty finite intersection of the $B_i$ has a principal ultrafilter containing it, whereas an empty intersection cannot belong to any proper filter. The $B_i$ therefore generate a proper filter, which extends to an ultrafilter by the same Zorn argument. That ultrafilter lies outside every $\widehat{A_i}$, contradicting the cover. Hence $\beta \mathbb{N}$ is compact and Hausdorff. Natural number $n$ is identified with its principal ultrafilter.

Hindman's theorem asserts that every finite colouring of the positive integers has an increasing sequence $x_1<x_2<\cdots$ for which all nonempty finite sums of distinct terms have one colour. Let $\mathcal{U}+\mathcal{U}=\mathcal{U}$ be the given idempotent ultrafilter. Since $\mathbb{N}$ is positive, a principal ultrafilter cannot be idempotent: its sum with itself is principal at $2n$, not $n$. Thus $\mathcal{U}$ is nonprincipal and contains every cofinite tail. In a convention including zero, one instead uses an idempotent in the nonprincipal part, excluding the trivial principal idempotent at zero.

For $A\subseteq \mathbb{N}$ define $A-n=\{m:n+m\in A\}$. Addition on the Stone-Čech compactification of the natural numbers is characterized byOne cell $A$ of the finite colour partition belongs to $\mathcal{U}$. PutIdempotence makes $A^{\ast }\in \mathcal{U}$. Moreover, if $n\in A^{\ast }$, then $A^{\ast }-n\in \mathcal{U}$. Indeed, write $B=\{y:A-y\in \mathcal{U}\}$ so $A^{\ast }=A\cap B$. We have $A-n\in \mathcal{U}$, and idempotence applied to that set givesTheir intersection is $A^{\ast }-n$. This is the idempotent-ultrafilter star-set lemma.

Choose $x_1\in A^{\ast }$. If the finite-sums set $F_k$ of the first $k$ choices lies in $A^{\ast }$, selectEvery factor belongs to $\mathcal{U}$, so this finite intersection is nonempty. Its choice preserves $F_{k+1}\subseteq A^{\ast }$. ThereforeThis proves the requested Idempotent-ultrafilter proof of Hindman's theorem, without assuming an idempotent-existence proof.

Finally, for the first logical assertion put $P=\{x:p(x)\}$ and $Q=\{x:q(x)\}$. A proper filter contains $P\cap Q$ if and only if it contains both $P$ and $Q$: one direction is finite-intersection closure and the other is upward closure. Thus (i) is always true. This is the conjunction law for filter quantifiers.

Membership of either truth set in a filter on a set implies membership of its union, by upward closure. The converse need not hold. For the cofinite filter, take $p(x)$ to mean that $x$ is even and $q(x)$ that $x$ is odd. The union of their truth sets is all of $\mathbb{N}$, while neither truth set is cofinite.

Thus the left side of the printed equivalence is true and its right side false: (ii) can be false. An ultrafilter does satisfy the equivalence, because its dichotomy forces one member of a finite union into the ultrafilter. General filters need not have that dichotomy. This is one aspect of the Boolean failure of the cofinite-filter quantifier.

If the complement of a truth set belongs to a proper filter on a set, the truth set itself cannot belong: their intersection is empty. Hence the right side always implies the left side.

The reverse implication can fail. In the cofinite filter, the set of even integers is absent, but its odd complement is absent as well. The filter-quantified evenness assertion is false, while the filter-quantified assertion of oddness is also false. Therefore (iii) can be false.

For an ultrafilter the equivalence is true, precisely because it contains exactly one of any set and its complement. The filter quantifier preserves conjunction for arbitrary proper filters, but its full classical Boolean behaviour requires the ultrafilter property.

Define $D_{\mathcal{G}}(A)=\{x:A-x\in \mathcal{G}\}$. The proposed addition of filters on the natural numbers isBecause addition of positive integers stays in $\mathbb{N}$, $D_{\mathcal{G}}(\mathbb{N})=\mathbb{N}$ and $D_{\mathcal{G}}(\varnothing )=\varnothing$. Thus the sum contains the whole set and excludes the empty set. If $A\subseteq B$, upward closure of $\mathcal{G}$ gives $D_{\mathcal{G}}(A)\subseteq D_{\mathcal{G}}(B)$, so upward closure of $\mathcal{F}$ gives upward closure of the sum.

Finally, for every $x$,The conjunction property for $\mathcal{G}$ proved in (i) consequently givesFinite-intersection closure of $\mathcal{F}$ proves the same closure for its sum. All proper-filter axioms hold, so (iv) is always true. No ultrafilter assumption is needed here.