# Proof of Ultrafilter lemma with two propositions and Zorn lemma

I would like to prove the following:

Let $X$ be any set, then every filter $\mathcal{F}$ on $X$ is contained in an ultrafilter $F$

Using two propositions and Zorn Lemma. I am required to come up with the propositions and the proof. Can someone check if everything looks okay.

Recall definitions:

A filter $\mathcal{F} \subset \mathcal{P}(X)$ is a collection of sets satisfying:

1. $\varnothing \not\in \mathcal{F}$
2. $A \in \mathcal{F} , A \subseteq B \implies B \in \mathcal{F}$
3. $A, B \in \mathcal{F} \implies A \cap B \in \mathcal{F}$

and

$F$ is an ultrafilter if for all $\mathcal{F}$ a filter on $X$, $F \not\subset \mathcal{F}$

Proposition 1: If $F$ is a maximal element of $(\mathbb{F}, \subseteq)$, where $\mathbb{F} = \{\mathcal{F} | \mathcal{F} \text{ is a filter on } X\}$, then $\mathcal{F} \subset F, \forall \mathcal{F} \in \mathbb{F}$ (Read: Maximal element of poset $(\mathbb{F}, \subseteq)$ contains all filters)

Proposition 2: Every chain in $\mathbb{F}$ given above has an upperbound given by $G = \bigcup \mathcal{C}$, $\mathcal{C}$ is a chain of filters.

Zorn Lemma (Adapted to this scenario): Given $(\mathbb{F}, \subseteq)$ a poset, $\subseteq$ is ordering by inclusion, if every chain in $\mathbb{F}$ has an upperbound, then $\mathbb{F}$ contains a maximal element.

proof:

Proof of proposition 1: Let $F$ be the maximal element on $(\mathbb{F}, \subseteq)$, take a filter $\mathcal{F} \in \mathbb{F}$, we wish to show that $\mathcal{F} \subseteq F$. By contradiction, suppose $\mathcal{F} \not\subseteq F$, then either $F \subset \mathcal{F}$ or $F \cap \mathcal{F} = \varnothing$.

We eliminate the former case because it contradictions the definition of being maximal. Suppose $F \cap \mathcal{F} = \varnothing$, take $A \in \mathcal{F}$, then by definition of being maximal, $A \in F$ or $X \backslash A \in F$. By assumption, $A$ cannot be in $F$, therefore for all $A \in \mathcal{F}, X \backslash A \in F$. Then suppose $A = X$, then $X \backslash X = \varnothing \in F \implies$ contradicts definition of being a filter.

Therefore, $F$ contains all $\mathcal{F}$ a filter on $X$.

Proof of proposition 2: Let $\mathcal{C}$ be a chain on $\mathbb{F}$, then $\mathcal{C} = \{\mathcal{F}_\alpha | \alpha \in I\}$ for some index set $I$. Take $G = \bigcup \mathcal{C}$ and we claim this is the upperbound of $\mathcal{C}$. Indeed, $\forall \mathcal{F}_\alpha \in \mathcal{C}, \mathcal{F}_\alpha \subset G$. We wish to show that $G$ is a filter. Suppose not, then there exists $A \in G$ such that $A \subset B$, $B \subset \mathcal{P}(X)$ and $B \notin G$. Since $A$ is contained in some $\mathcal{F}_i \subset G$, then by definition of a chain, $\exists k > i$, such that $\mathcal{F}_i \subset \mathcal{F}_k$ and $A \in \mathcal{F}_k, k > i$. Then $\forall B$, $B \subset \mathcal{P}(X)$ $A \subset B, \implies B \in \mathcal{F}_k$. But since $G = \bigcup \mathcal{C}$, $B \in G$. Contradiction. So $G = \bigcup \mathcal{C}$ is a filter.

Conclusion by Zorn Lemma: We know that given $(\mathbb{F}, \subseteq)$ a poset, $\subseteq$ is ordering by inclusion, if every chain in $\mathbb{F}$ has an upperbound, then $\mathbb{F}$ contains a maximal element. By (proposition 2), every chain has an upperbound, then $\mathbb{F}$ contains a maximal element $F$ which is an ultrafilter on $X$ and by (proposition 1) contains every filter on $X$. So every set $X$ has an ultrafilter that contains every filter on $X$

Can someone check the above is sound. Please let me know if there is need for corrections. Thank you.

• You did not check closure of $G$ under intersection. – André Nicolas Jul 11 '16 at 13:54
• Proposition $1$ is false. If it were true, there could only be one ultrafilter on any set. Moreover, your final argument, even if it were correct, would only establish the existence of some ultrafilter on $X$, not one containing a given filter $\mathscr{F}$. – Brian M. Scott Jul 11 '16 at 14:01
• The definition of ultrafilter I am accustomed to builds in for all $A$, $A$ is in the ultrafilter $D$ or $X\setminus A$ is. Extensions of filter to ultrafilter are often highly non-unique, so one should not say or assume that there is the maximal element. – André Nicolas Jul 11 '16 at 14:19
• @AndréNicolas Hi from the feedbacks I am not certain what I should change. That being said, I could add in closure of $G$ under intersection and also check for $\varnothing$ case. But I am not sure how to fix proposition 1. – Shamisen Expert Jul 11 '16 at 14:27
• (More) So suppose neither is. Show that we can add $B$ to $U$ to obtain a filter $U'$ that properly extends $U$. We define $U'$ as the collection of all supersets of sets $B\cap Y$, where $Y$ ranges over $U$. The only way this can fail to be a filter is if it contains the empty set, but then $X\setminus B$ is in $U$. – André Nicolas Jul 11 '16 at 14:51

You’re given a filter $\mathscr{F}$ on $X$, and you want to show that there’s an ultrafilter $\mathscr{U}$ on $X$ such that $\mathscr{F}\subseteq\mathscr{U}$. Since you’re going to be using Zorn’s lemma, it’s certainly reasonable to suppose that $\mathscr{U}$ will be a maximal element some partial order, but you need to make sure that this maximal element contains $\mathscr{F}$. The easiest way to do that is to start with a partial order of objects that contain $\mathscr{F}$: let
$$\Bbb P=\{\mathscr{G}\subseteq\wp(X):\mathscr{F}\subseteq\mathscr{G}\text{ and }\mathscr{G}\text{ is a filter on }X\}\;,$$
and consider the partial order $\langle\Bbb P,\subseteq\rangle$. Any maximal element of $\Bbb P$ will at least be a filter on $X$ containing $X$.
In order to apply Zorn’s lemma, you’ll have to show that $\langle\Bbb P,\subseteq\rangle$ satisfies its hypothesis, i.e., that every chain in the partial order has an upper bound in $\Bbb P$; this is essentially your Proposition 2 with a slightly different partial order.
In order for Zorn’s lemma to give you the desired result, you need to prove that a maximal element of $\Bbb P$ is an ultrafilter on $X$. With your definition of ultrafilter there’s nothing to prove, and I have no idea what second proposition you’re expected to come up with. If you were using the other common definition, mentioned by André Nicolas in the comments, that a filter $\mathscr{U}$ on $X$ is an ultrafilter if and only if for each $A\subseteq X$, exactly one of $A$ and $X\setminus A$ belongs to $\mathscr{U}$, you would need a second proposition:
Proposition. If $\mathscr{U}$ is a filter on $X$ that is maximal with respect to $\subseteq$, then $\mathscr{U}$ is an ultrafilter.