Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 4 / 16H (Logic and Set Theory)

Zorn lemma states that if every chain in a nonempty partially ordered set has an upper bound in that set, then the set has a maximal element. It is equivalent, over the usual axioms of set theory, to the axiom of choice.

The set $P_x=\{y\in P:x\le y\}$ is nonempty because it contains $x$. Every nonempty chain $C\subseteq P_x$ has an upper bound $u$ in $P$ by hypothesis. Since every member of $C$ is at least $x$, one has $x\le u$, so $u\in P_x$. Zorn lemma therefore gives a maximal element $\sigma$ of $P_x$. If $\sigma \le z$ in $P$, then $z\in P_x$, and maximality in $P_x$ forces $z=\sigma$. Thus $\sigma$ is maximal in $P$ and satisfies $x\le \sigma$.

The family ${\mathcal{U}}_n=\{A\subseteq \mathbb{N}:n\in A\}$ is nonempty, excludes the empty set, is closed under finite intersections, and is upward closed. It is therefore a filter. For every $A\subseteq \mathbb{N}$, either $n\in A$ or $n\in A^c$, so either $A\in {\mathcal{U}}_n$ or $A^c\in {\mathcal{U}}_n$. Hence ${\mathcal{U}}_n$ is the principal ultrafilter at $n$.

The cofinite filter $\mathcal{F}$ is nonempty, because $\mathbb{N}\in \mathcal{F}$; finite unions of finite complements show closure under intersections, and taking a superset can only shrink the complement. The empty set is excluded because its complement is infinite. It is not an ultrafilter: the even numbers and the odd numbers both have infinite complements, so neither belongs to $\mathcal{F}$. Finally, $\mathbb{N}\setminus \{n\}$ is cofinite but does not belong to ${\mathcal{U}}_n$, proving $\mathcal{F}⊈{\mathcal{U}}_n$ for every $n$.

Yes. Order the proper filters containing the cofinite filter by inclusion. The union of every chain is again a proper filter containing $\mathcal{F}$: any finite collection of its members already lies in one filter in the chain. Zorn lemma gives a maximal proper filter $\mathcal{U}$.

A maximal proper filter is an ultrafilter. Indeed, if $A\notin \mathcal{U}$, adjoining $A$ cannot generate another proper filter, so some $U\in \mathcal{U}$ has $U\cap A=\varnothing$. Thus $U\subseteq A^c$, and upward closure gives $A^c\in \mathcal{U}$. Finally, $\mathcal{U}$ cannot equal any principal ultrafilter ${\mathcal{U}}_n$, because it contains the cofinite set $\mathbb{N}\setminus \{n\}$ whereas ${\mathcal{U}}_n$ does not. Thus $\mathcal{U}$ is a nonprincipal ultrafilter on $\mathbb{N}$.