proof that every filter is contained in an ultrafilter

Let $Y$ be the set of all non-empty subsets of $X$ which are not contained in $ℱ$. By Zermelo’s well-orderding theorem, there exists a relation ‘$\succ$’ which well-orders $Y$. Define $Y^{\prime }=\{0\}\cup Y$ and extend the relation ‘$\succ$’ to $Y^{\prime }$ by decreeing that $0\prec y$ for all $y\in Y$.

We shall construct a family of filters $S_i$ indexed by $Y^{\prime }$ using transfinite induction. First, set $S_0=ℱ$. Next, suppose that, for some $j\in Y$, $S_i$ has already been defined when $i\prec j$. Consider the set ${\bigcup }_{i\prec j}{S}_i$; if $A$ and $B$ are elements of this set, there must exist an $i\prec j$ such that $A\in S_i$ and $B\in S_i$; hence, $A\cap B$ cannot be empty. If, for some $i\prec j$ there exists an element $f\in S_i$ such that $f\cap j$ is empty, let $S_j$ be the filter generated by the filter subbasis ${\bigcup }_{i\prec j}{S}_i$. Otherwise $\{j\}\cup {\bigcup }_{i\prec j}{S}_i$ is a filter subbasis; let $S_j$ be the filter it generates.

Note that, by this definition, whenever $i\prec j$, it follows that $S_i\subseteq S_j$; in particular, for all $i\in Y^{\prime }$ we have $ℱ\subseteq S_i$. Let $𝒰={\bigcup }_{i\prec j}{S}_i$. It is clear that $\mathrm{\varnothing }\notin ℱ$ and that $ℱ\subseteq 𝒰$.

It is easy to see that $𝒰$ is a filter. Suppose that $A\cap B\in 𝒰$. Then there must exist an $i\in Y^{\prime }$ such that $A\cap B\in S_i$. Since $S_i$ is a filter, $A\in S_i$ and $B\in S_i$, hence $A\in 𝒰$ and $B\in 𝒰$. Conversely, if $A\in 𝒰$ and $B\in 𝒰$, then there exists an $i\in Y^{\prime }$ such that $A\in S_i$ and $B\in S_i$. Since $S_i$ is a filter, $A\cap B\in S_i$, hence $A\cap B\in 𝒰$. By the alternative characterization of a filter, $𝒰$ is a filter.

Moreover, $𝒰$ is an ultrafilter. Suppose that $A\in 𝒰$ and $B\in 𝒰$ are disjoint and $A\cup B=X$. If either $A\in ℱ$ or $B\in ℱ$, then either $A\in 𝒰$ or $B\in 𝒰$ because $ℱ\subset 𝒰$. If $A\in Y$ and $A\in S_A$, then $A\in 𝒰$ because $S_A\subset 𝒰$. If $A\in Y$ and $A\notin S_A$, there must exist $x\in 𝒰$ such that $A\cap x$ is empty. Because $B$ is the complement of $A$, this means that $x\subset B$ and, hence $B\in 𝒰$.

This completes the proof that $𝒰$ is an ultrafilter — we have shown that $𝒰$ meets the criteria given in the alternative characterization of ultrafilters.