Ultrafilters and Maximal Filters

From Filters to Maximal Filters

Filters record collections of subsets that are treated as large: they are closed under finite intersections and under passing to larger sets. Maximal proper filters have a stronger feature. For every subset, they choose that subset or its complement, but never both. This decision property is useful because it replaces a maximality condition with a test involving each individual subset.

Let \(X\) be a set. A filter on \(X\) must contain \(X\), so there is no proper filter when \(X=\varnothing\). In what follows, unless stated otherwise, \(X\) is nonempty. A filter is proper when it does not contain the empty set.

Here maximality is relative to proper filters: a larger collection containing the empty set is not a proper filter and therefore does not contradict maximality. The distinction matters when we prove the decision property.

The Decision Property

Proof. First suppose that \(\mathcal{U}\) is an ultrafilter, and fix \(A\subseteq X\). A proper filter cannot contain both \(A\) and \(X\setminus A\), since it would then contain their intersection \(\varnothing\). Thus at most one belongs to \(\mathcal{U}\). We show that at least one belongs.

Suppose, to the contrary, that \(A\notin\mathcal{U}\) and \(X\setminus A\notin\mathcal{U}\). Consider the collection \[ \mathcal{G}=\{B\subseteq X:\text{there is some }F\in\mathcal{U}\text{ with }F\cap A\subseteq B\}. \] We verify that \(\mathcal{G}\) is a proper filter. Since \(X\in\mathcal{U}\) and \(X\cap A=A\subseteq X\), we have \(X\in\mathcal{G}\). If \(\varnothing\in\mathcal{G}\), there would be \(F\in\mathcal{U}\) with \(F\cap A\subseteq\varnothing\), hence \(F\cap A=\varnothing\). This implies \(F\subseteq X\setminus A\), so upward closure of \(\mathcal{U}\) gives \(X\setminus A\in\mathcal{U}\), contrary to the assumption. Therefore \(\varnothing\notin\mathcal{G}\).

If \(B\in\mathcal{G}\) and \(B\subseteq C\subseteq X\), the same filter member witnessing \(B\in\mathcal{G}\) also witnesses \(C\in\mathcal{G}\). If \(B,C\in\mathcal{G}\), choose \(F,G\in\mathcal{U}\) with \(F\cap A\subseteq B\) and \(G\cap A\subseteq C\). Since \(F\cap G\in\mathcal{U}\), we have \[ (F\cap G)\cap A\subseteq B\cap C, \] so \(B\cap C\in\mathcal{G}\). These facts verify all the filter conditions.

Every \(H\in\mathcal{U}\) belongs to \(\mathcal{G}\), because \(H\cap A\subseteq H\). Also \(A\in\mathcal{G}\), witnessed by \(F=X\). Since \(A\notin\mathcal{U}\), this is a proper filter strictly containing \(\mathcal{U}\), contradicting maximality. Therefore at least one of \(A\) and \(X\setminus A\) belongs to \(\mathcal{U}\).

Conversely, suppose \(\mathcal{U}\) has the stated decision property. If a proper filter \(\mathcal{V}\) strictly contains \(\mathcal{U}\), choose \(A\in\mathcal{V}\setminus\mathcal{U}\). By the decision property, \(X\setminus A\in\mathcal{U}\subseteq\mathcal{V}\). But \(A\in\mathcal{V}\) as well, so closure under intersections gives \(\varnothing=A\cap(X\setminus A)\in\mathcal{V}\), contradicting that \(\mathcal{V}\) is proper. No proper filter strictly contains \(\mathcal{U}\), so \(\mathcal{U}\) is an ultrafilter. \(\square\)

The theorem proves both directions. In the forward direction, failure to decide a subset would allow us to build a larger proper filter. In the reverse direction, a proper extension would have to add a subset whose complement is already in the original filter, forcing the extension to contain the empty set.

Ultrafilters on Finite Sets

Proof. Let \(\mathcal{U}\) be an ultrafilter on the finite, nonempty set \(X\). If no singleton \(\{x\}\) belonged to \(\mathcal{U}\), then the decision property would give \(X\setminus\{x\}\in\mathcal{U}\) for every \(x\in X\). Taking the intersection of these finitely many filter members would put \[ \bigcap_{x\in X}(X\setminus\{x\})=\varnothing \] in \(\mathcal{U}\), which is impossible. Thus \(\{x\}\in\mathcal{U}\) for some \(x\in X\).

Every subset \(B\subseteq X\) containing \(x\) belongs to \(\mathcal{U}\), since \(\{x\}\subseteq B\) and filters are upward closed. If \(B\in\mathcal{U}\), it must contain \(x\): otherwise \(B\cap\{x\}=\varnothing\), contradicting closure under intersections and properness. Hence \(\mathcal{U}\) consists exactly of the subsets containing \(x\). Conversely, the collection of all subsets containing \(x\) is a proper filter and satisfies the decision property: if \(x\in B\), then \(B\) belongs; if \(x\notin B\), then \(x\in X\setminus B\), so the complement belongs. The decision theorem makes it an ultrafilter. \(\square\)

The Cofinite Filter on an Infinite Set

For an infinite set \(X\), the cofinite filter consists of the subsets \(A\subseteq X\) whose complements \(X\setminus A\) are finite. It is proper: \(X\) has finite complement \(\varnothing\), whereas \(\varnothing\) does not have finite complement because \(X\) is infinite. Intersections remain cofinite because \[ X\setminus(A\cap B)=(X\setminus A)\cup(X\setminus B), \] and a union of two finite sets is finite. A superset of a cofinite set is also cofinite, since its complement is a subset of a finite set.

Common pitfall. One might argue that the cofinite filter on \(\mathbb{N}\) is maximal because it contains every subset with finite complement. That does not establish maximality: the decision property must hold for every subset, including \(E\). The explicit calculation above shows that both \(E\) and \(\mathbb{N}\setminus E=O\) have infinite complements, so neither is in the filter. The decision criterion therefore rules out maximality.

There is a related finite-set trap. On a finite set \(X\), every subset has finite complement, including \(\varnothing\), since \(X\setminus\varnothing=X\) is finite. Consequently the collection of all subsets with finite complement contains \(\varnothing\), so it is not a proper filter. The cofinite-filter example requires an infinite underlying set.

Why the Decision Property Is Useful

Maximality is a comparison with every proper filter that might contain a given one. The decision property turns that global comparison into a subset-by-subset test. On finite sets, it forces an ultrafilter to concentrate on a single point. On an infinite set, the cofinite filter demonstrates that being a proper filter is not enough: a subset and its complement can both fail to be cofinite. The key distinction is therefore not just closure under intersections and supersets, but the additional requirement that maximal proper filters make a consistent choice between every subset and its complement.