From a Proper Filter to an Ultrafilter
Filters collect subsets that are regarded as large, while an ultrafilter makes a definite choice between every subset and its complement. A useful way to obtain such a decisive family is to enlarge a given proper filter as far as possible without allowing the empty set into it. Zorn’s lemma supplies the maximal enlargement; the main work is verifying that its hypothesis really holds.
A proper filter can exist only when \(X\ne\varnothing\), since it must contain \(X\) and exclude \(\varnothing\). The extension result below is therefore stated for a proper filter already given; if \(X=\varnothing\), there is no such filter and the conditional statement has no instance.
Constructing the Partially Ordered Set
Consider all proper filters on \(X\) that contain the given \(\mathcal{F}\), ordered by inclusion. This is a set: it is a subcollection of \(\mathcal{P}(\mathcal{P}(X))\). It is nonempty because \(\mathcal{F}\) itself belongs to it. To use Zorn’s lemma, we must show that every chain has an upper bound in this partially ordered set. A chain here means a collection of filters linearly ordered by inclusion.
Proof. Since \(\mathcal{C}\) is nonempty, choose \(\mathcal{H}\in\mathcal{C}\). Each member of \(\mathcal{H}\) belongs to \(\mathcal{G}\), so \(X\in\mathcal{G}\). No member of \(\mathcal{C}\) contains \(\varnothing\), so \(\varnothing\notin\mathcal{G}\). If \(A\in\mathcal{G}\), then \(A\in\mathcal{H}\) for some \(\mathcal{H}\in\mathcal{C}\). For any \(B\) with \(A\subseteq B\subseteq X\), upward closure in \(\mathcal{H}\) gives \(B\in\mathcal{H}\subseteq\mathcal{G}\).
It remains to check intersections. Suppose \(A,B\in\mathcal{G}\). There are \(\mathcal{H}_1,\mathcal{H}_2\in\mathcal{C}\) with \(A\in\mathcal{H}_1\) and \(B\in\mathcal{H}_2\). Because \(\mathcal{C}\) is a chain, either \(\mathcal{H}_1\subseteq\mathcal{H}_2\) or \(\mathcal{H}_2\subseteq\mathcal{H}_1\). In the first case both \(A\) and \(B\) belong to \(\mathcal{H}_2\); in the second they both belong to \(\mathcal{H}_1\). That filter contains \(A\cap B\), so \(A\cap B\in\mathcal{G}\). Finally, each \(\mathcal{H}\in\mathcal{C}\) is contained in \(\mathcal{G}\), making \(\mathcal{G}\) an upper bound. \(\square\)
The empty chain also has an upper bound in the partially ordered set: the given filter \(\mathcal{F}\). Thus every chain has an upper bound. Zorn’s lemma gives a maximal member \(\mathcal{U}\) of the partially ordered set. If a proper filter strictly contained \(\mathcal{U}\) as a subset in the wrong direction—that is, if a proper filter strictly extended \(\mathcal{U}\)—then it would still contain \(\mathcal{F}\), contradicting maximality in this partially ordered set. Therefore \(\mathcal{U}\) is maximal among all proper filters on \(X\), and hence is an ultrafilter. This proves the theorem.
Why Maximality Gives the Ultrafilter Dichotomy
The maximal-filter definition has a useful equivalent form: for every \(A\subseteq X\), an ultrafilter contains either \(A\) or \(X\setminus A\). We prove this criterion here, so the meaning of the maximal extension is explicit.
Proof. First suppose \(\mathcal{U}\) is maximal, and fix \(A\subseteq X\) with \(A\notin\mathcal{U}\). We show that some \(G\in\mathcal{U}\) has \(G\cap A=\varnothing\). If instead every \(G\in\mathcal{U}\) met \(A\), define \[ \mathcal{H}=\{B\subseteq X:\text{ there is }G\in\mathcal{U}\text{ such that }G\cap A\subseteq B\}. \] Every \(G\in\mathcal{U}\) belongs to \(\mathcal{H}\), since \(G\cap A\subseteq G\), and \(A\in\mathcal{H}\), using \(G=X\). Also \(X\in\mathcal{H}\). The assumed nonempty intersections \(G\cap A\ne\varnothing\) show \(\varnothing\notin\mathcal{H}\). Upward closure follows directly from the definition. If \(B_1,B_2\in\mathcal{H}\), choose \(G_1,G_2\in\mathcal{U}\) with \(G_1\cap A\subseteq B_1\) and \(G_2\cap A\subseteq B_2\). Then \(G_1\cap G_2\in\mathcal{U}\), and \[ (G_1\cap G_2)\cap A\subseteq B_1\cap B_2. \] Thus \(B_1\cap B_2\in\mathcal{H}\). So \(\mathcal{H}\) is a proper filter containing \(\mathcal{U}\) and \(A\), contradicting maximality because \(A\notin\mathcal{U}\). Hence such a \(G\) exists. Since \(G\subseteq X\setminus A\), upward closure gives \(X\setminus A\in\mathcal{U}\).
Conversely, suppose the stated dichotomy holds and that a proper filter \(\mathcal{V}\) contains \(\mathcal{U}\). If there were \(A\in\mathcal{V}\setminus\mathcal{U}\), the dichotomy would give \(X\setminus A\in\mathcal{U}\subseteq\mathcal{V}\). Then \(\varnothing=A\cap(X\setminus A)\in\mathcal{V}\), contradicting that \(\mathcal{V}\) is proper. No such \(A\) exists, so \(\mathcal{V}=\mathcal{U}\). Therefore \(\mathcal{U}\) is maximal and is an ultrafilter. \(\square\)
The two alternatives in the dichotomy cannot both hold: their intersection is empty, and a proper filter is closed under intersections but cannot contain the empty set.
Worked Examples
Worked Example: Extending a Filter on a Two-Point Set
Let \(X=\{a,b\}\) and start with \(\mathcal{F}=\{X\}\). This is a proper filter: it contains \(X\), excludes \(\varnothing\), and its only intersection and upward-closure requirements within \(\mathcal{P}(X)\) are satisfied.
Two extensions are \[ \mathcal{U}_a=\{\{a\},X\},\qquad \mathcal{U}_b=\{\{b\},X\}. \] For \(\mathcal{U}_a\), intersections of its members are either \(\{a\}\) or \(X\), and every subset of \(X\) containing one of its members is again one of its members. It excludes \(\varnothing\), so it is a proper filter. The same checks apply to \(\mathcal{U}_b\). The only subsets of \(X\) are \(\varnothing,\{a\},\{b\},X\). Any proper filter strictly extending \(\mathcal{U}_a\) would have to include \(\{b\}\), and then would include \(\{a\}\cap\{b\}=\varnothing\), which is impossible. Thus \(\mathcal{U}_a\) is maximal; the same argument proves \(\mathcal{U}_b\) is maximal. Both extend \(\mathcal{F}\), so the extension need not be unique.
Check: \(\mathcal{U}_a\) contains \(\{a\}\) and its complement \(\{b\}\) is not in \(\mathcal{U}_a\); \(\mathcal{U}_b\) makes the opposite choice. Each satisfies the dichotomy for every subset in the displayed list.
Worked Example: Extending the Cofinite Filter on the Natural Numbers
On \(X=\mathbb{N}\), let \(\mathcal{F}\) consist of all subsets whose complements in \(\mathbb{N}\) are finite. This is a proper filter. The complement of \(\mathbb{N}\) is empty, so \(\mathbb{N}\in\mathcal{F}\); the complement of \(\varnothing\) is infinite, so \(\varnothing\notin\mathcal{F}\). If \(A,B\in\mathcal{F}\), then \[ \mathbb{N}\setminus(A\cap B) =(\mathbb{N}\setminus A)\cup(\mathbb{N}\setminus B), \] which is a union of two finite sets and is finite. Upward closure follows because \(A\subseteq B\) implies \(\mathbb{N}\setminus B\subseteq\mathbb{N}\setminus A\). The extension principle gives an ultrafilter \(\mathcal{U}\) containing \(\mathcal{F}\).
This extension contains no finite set \(E\subseteq\mathbb{N}\). Indeed, \(\mathbb{N}\setminus E\) is cofinite, so it belongs to \(\mathcal{F}\subseteq\mathcal{U}\). If \(E\) also belonged to \(\mathcal{U}\), closure under intersections would put \(E\cap(\mathbb{N}\setminus E)=\varnothing\) in \(\mathcal{U}\), contradicting properness. In particular, \(\mathcal{U}\) is not a principal ultrafilter generated by a point \(n\), since such an ultrafilter contains the finite set \(\{n\}\).
Check: for each finite \(E\), the two sets \(E\) and \(\mathbb{N}\setminus E\) are disjoint, and the latter belongs to the original filter. The contradiction uses only the defining filter conditions.
Worked Example: A Filter Generated by Tails
For each \(n\in\mathbb{N}\), let \(E_n=\{m\in\mathbb{N}:m\ge n\}\). Finite intersections of these sets are nonempty: for indices \(n_1,\ldots,n_k\), their intersection is \(E_r\), where \(r\) is the largest of those indices. The empty finite intersection is understood to be \(\mathbb{N}\).
Define \(\mathcal{F}\) to be the family of all subsets \(B\subseteq\mathbb{N}\) that contain some finite intersection of the \(E_n\). Equivalently, \(B\in\mathcal{F}\) exactly when it contains \(E_n\) for some \(n\). This family contains \(\mathbb{N}\), excludes \(\varnothing\) because every \(E_n\) is nonempty, and is upward closed. If \(B\) contains \(E_n\) and \(C\) contains \(E_m\), then \(B\cap C\) contains \(E_{\max(n,m)}=E_n\cap E_m\), so \(B\cap C\in\mathcal{F}\). Thus \(\mathcal{F}\) is a proper filter and has an ultrafilter extension.
For a concrete distinction from the cofinite filter, the set of even natural numbers does not belong to \(\mathcal{F}\): for every \(n\), the tail \(E_n\) contains an odd number, so \(E_n\) is not a subset of the even numbers. This example shows how a family with the finite intersection property can generate a proper filter before the extension principle is applied.
Where Choice Enters—and a Common Pitfall
The existence proof uses Zorn’s lemma at one specific point: after showing that every chain of proper filters containing \(\mathcal{F}\) has an upper bound, we invoke Zorn to obtain a maximal member. Zorn’s lemma is a standard form of the axiom of choice; in the usual foundations of set theory it is equivalent to the axiom of choice. That foundational equivalence is not proved here. The filter calculations themselves do not select an element from each set in a family; the choice principle enters through the maximality argument.
Common pitfall. The union of a chain is a filter, but the union of arbitrary filters need not be one. On \(X=\{1,2\}\), let \(\mathcal{U}_1=\{A\subseteq X:1\in A\}\) and \(\mathcal{U}_2=\{A\subseteq X:2\in A\}\). Both are proper filters. Their union contains \(\{1\}\) and \(\{2\}\), but it does not contain \(\{1\}\cap\{2\}=\varnothing\). Thus \(\mathcal{U}_1\cup\mathcal{U}_2\) is not a filter. The chain hypothesis matters because it ensures that any two sets in the union occur together in one of the filters.
It is also not enough to say “keep enlarging the filter until it is maximal.” In an infinite setting, this phrase gives neither a finite stopping point nor a construction that proves a maximal object exists. The chain-upper-bound verification is what makes Zorn’s lemma applicable and turns the maximality claim into a proof.
Check Your Understanding
For each question, use the filter axioms and distinguish carefully between a chain and an arbitrary collection.
- Why does the union of a nonempty chain of proper filters exclude the empty set?
- In the two-point example, why can no proper filter extend \(\mathcal{U}_a\) by adding \(\{b\}\)?
- Show that the cofinite subsets of any infinite set form a proper filter.
- Explain why the finite-intersection condition is used when proving that a generated filter excludes \(\varnothing\).
- Identify the exact step in the extension proof where Zorn’s lemma is invoked, and state what has to be verified before that invocation.