(a) State Zorn's lemma.

[Throughout the remainder of this question, assume Zorn's lemma.]

(b) Let $P$ be a poset in which every non-empty chain has an upper bound and let $x \in P$. By considering the poset $P_{x}=\{y \in P \mid x \leqslant y\}$, show that $P$ has a maximal element $\sigma$ with $x \leqslant \sigma$.

(c) A filter is a non-empty subset $\mathcal{F} \subset \mathcal{P}(\mathbb{N})$ satisfying the following three conditions:

• if $A, B \in \mathcal{F}$ then $A \cap B \in \mathcal{F}$

• if $A \in \mathcal{F}$ and $A \subset B$ then $B \in \mathcal{F}$

• $\emptyset \notin \mathcal{F} .$

An ultrafilter is a filter $\mathcal{U}$ such that for all $A \subset \mathbb{N}$ we have either $A \in \mathcal{U}$ or $A^{c} \in \mathcal{U}$, where $A^{c}=\mathbb{N} \backslash A$.

(i) For each $n \in \mathbb{N}$, show that $\mathcal{U}_{n}=\{A \subset \mathbb{N} \mid n \in A\}$ is an ultrafilter.

(ii) Show that $\mathcal{F}=\left\{A \subset \mathbb{N} \mid A^{c}\right.$ is finite $\}$ is a filter but not an ultrafilter, and that for all $n \in \mathbb{N}$ we have $\mathcal{F} \not \subset \mathcal{U}_{n}$.

(iii) Does there exist an ultrafilter $\mathcal{U}$ such that $\mathcal{U} \neq \mathcal{U}_{n}$ for any $n \in \mathbb{N}$ ? Justify your answer.