Ultrafilter Lemma

Theorem

Let $S$ be a set.

Every filter on $S$ is contained in an ultrafilter on $S$.

Corollary

Let $S$ be a non-empty set.

Let $\AA$ be a set of subsets of $S$.

Suppose that $\AA$ has the finite intersection property.

Then there is an ultrafilter $\UU$ on $S$ such that $\AA \subseteq \UU$.

Proof using Axiom of Choice

Let $\Omega$ be the set of filters on $S$.

From Subset Relation is Ordering, the subset relation makes $\struct {\Omega, \subseteq}$ a partially ordered set.

Let $C \subseteq \Omega$ be a non-empty chain.

Then $\bigcup C$ is again a filter on $S$.

Thus $\bigcup C$ is an upper bound of $C$.

Indeed, if $A, B \in \bigcup C$ then there there are filters $\FF, \FF' \in C$ with $A \in \FF$ and $B \in \FF'$.

We have that $C$ is a chain.

Without loss of generality, let $\FF \subset \FF'$.

Thus $A \in \FF'$.

Hence:

$A \cap B \in \FF'$

In particular:

$A, B \in \bigcup C$

For any $\FF \in \Omega$ there is therefore by Zorn's Lemma a maximal element $\FF'$ such that:

$\FF \subseteq \FF'$

The maximality of $\FF'$ is in this context equivalent to $\FF'$ being an ultrafilter.

$\blacksquare$

Proof using Boolean Prime Ideal Theorem

Let $\FF$ be a filter on $S$.

Let the power set of $S$ be ordered by inclusion.

Then, by Filter on Set is Proper Filter, $\FF$ is a proper filter on $\powerset S$.

By Filter is Ideal in Dual Ordered Set, $\FF$ is an ideal in the dual of $\powerset S$.

By Singleton of Bottom is Ideal, $\set \empty$ is an ideal in $\powerset S$.

By Ideal is Filter in Dual Ordered Set, $\set \empty$ is a filter on the dual of $\powerset S$.

By the definition of Filter on Set, $\empty \notin \FF$, so $\FF$ and $\set \empty$ are disjoint.

Therefore, by the Boolean Prime Ideal Theorem, there is a prime ideal $\GG \supseteq \FF$ that is disjoint from $\set \empty$.

By Prime Ideal is Prime Filter in Dual Lattice, $\GG$ is a prime filter on the dual of the dual of $\powerset S$.

Thus, $\GG$ is a prime filter on $\powerset S$ by Dual of Dual Ordering.

But $\GG$ is disjoint from $\set \empty$, which implies that $\empty \notin \GG$.

Therefore, $\GG$ is a proper filter.

Thus, by Proper and Prime iff Ultrafilter in Boolean Lattice, $\GG$ is an ultrafilter on $\powerset S$.

But by comparing the definitions, $\GG$ is thus an ultrafilter on $S$.

$\blacksquare$

Also known as

The Ultrafilter Lemma can also be referred to as:

the ultrafilter principle

the ultrafilter theorem

and abbreviated UL or UF.