Filters

Muhammad Haris Rao

Let $X$ be a set. Roughly speaking, we will later want to define what it means for a subset of $X$ to be 'large'. This will be useful to define what it means for some property to be true for 'most' of the elements of $X$. There are some properties we would like such a definition of large to satisfy. For example, we would like any subset containing a large subset of $X$ to also be large. Further, we would like the intersection of two large sets to be large well. Thus, we have the following definition.

Definition: Let $X$ be a set. A filter $\mathcal{F}$ on $X$ is a collection of subsets of $X$ such that

1. $X \in \mathcal{F}$
2. If $A, B \in \mathcal{F}$, then also $A \cap B \in \mathcal{F}$
3. If $A \in \mathcal{F}$ and $A \subseteq B \subseteq X$ then also $B \in \mathcal{F}$

We say that $\mathcal{F}$ is a proper filter on $X$ if $\mathcal{F} \ne \mathcal{P}(X)$, or equivalently, $\emptyset \notin \mathcal{F}$.

Some examples of filters on a set $X$ are as follows.

• The set $\{ X \} \subseteq \mathcal{P}(X)$ and the set $\mathcal{P}(X)$ are filters on $X$. They are the trivial filters
• Let $A \subseteq X$. The filter on $X$ generated by $A$ is \begin{align*} \mathcal{A} &= \left\{ B \in \mathcal{P}(X) \mid A \subseteq B \right\} \end{align*} A filter on $X$ generated by an element of $\mathcal{P}(X)$ is called a principal filter.
• If $X$ is a set, then the Fréchet filter on $X$ is the collection of subsets whose relative complement with respect to $X$ is finite. That is, \begin{align*} \mathcal{F} = \left\{ A \in \mathcal{P}(X) \mid X - A \text{ is a finite set} \right\} \end{align*} Indeed, we have $X \in \mathcal{F}$ since the empty set is trivially finite. The intersection of two element from $\mathcal{F}$ has complement no larger than the complements of either element, so this intersection will also be in $\mathcal{F}$. Lastly, making a subset bigger makes its complement smaller so $\mathcal{F}$ is also closed upwards. Thus, the Fréchet filter on $X$ really is a filter. Furthermore, the Fréchet filter on $X$ is proper if and only if $X$ is infinite.

We will want to allow for as many subsets of $X$ to be deemed as large as we possibly can, without calling every subset of $X$ large. In other words, we define

Definition: An ultrafitler $\mathcal{F}$ on a set $X$ is a proper filter not strictly contained in any other proper filter on $X$. That is, $\mathcal{G}$ is a filter on $X$ such that $\mathcal{F} \subseteq \mathcal{G}$, then $\mathcal{F} = \mathcal{G}$ or $\mathcal{G} = \mathcal{P}(X)$.

A non-empty collection of subsets $S \subseteq \mathcal{P}(X)$ is said to possess the finite intersection property if the intersection of any finite number of elements from $S$ is non-empty.

Proposition: Suppose $S \subseteq \mathcal{P}(X)$ has the finite intsersection property. Then $S$ is contained in a proper filter on $X$.

Proof. Define $\mathcal{F} \subseteq \mathcal{P}(X)$ to be the collection \begin{align*} \mathcal{F} &= \bigcup_{n \in \mathbb{Z}_{> 0}} \left\{ A \in \mathcal{P}(X) \mid \text{there exist $B_1, B_2, \cdots, B_n \in S$ such that $B_1 \cap B_2 \cap \cdots \cap B_n \subseteq A$} \right\} \end{align*} Due to the finite intersection property of $S$, we have $\emptyset \notin \mathcal{F}$. So if $S$ is a filter, it is a proper filter. The fact that $\mathcal{F}$ is closed upwards is obvious, and if $A_1, A_1 \in \mathbb{F}$ then $A_1 \supseteq B_1 \cap B_2 \cap \cdots \cap B_n$ and $A_2 \supseteq C_1 \cap C_2 \cap \cdots \cap C_m$ for some $n, m \in \mathbb{Z}_{> 0}$, $A_1, A_2, \cdots, A_n, C_1, C_2, \cdots, C_m \in S$. But then \begin{align*} A_1 \cap A_2 \supseteq B_1 \cap B_2 \cap \cdots \cap B_n \cap C_1 \cap C_2 \cap \cdots C_m \end{align*} so $A_1 \cap A_2 \in \mathcal{F}$ as well. Thus, $\mathcal{F}$ is a proper filter on $X$ containing $S$. $\blacksquare$

Ultrafilters can also be characterised as follows.

Theorem: Let $X$ be a set, and $\mathcal{F} \subseteq \mathcal{P}(X)$ a filter on $X$. Then $\mathcal{F}$ is an ultrafilter if and only if for every $A \subseteq X$, either $A \in \mathcal{F}$ or $X - A \in \mathcal{F}$ and not both. Moreover, if $\mathfrak{F}$ is an ultrafilter with $A \cup B \in \mathfrak{F}$, then either $A \in \mathfrak{F}$ or $B \in \mathfrak{F}$.

Proof. Let $\mathcal{F}$ be a filter on $X$. If both $A, X - A \in \mathcal{F}$ then $\emptyset \in \mathcal{F}$ so $\mathcal{F}$ is not an ultrafilter.

Now suppose both $A, X - A \notin \mathcal{F}$ and consider the set $\mathcal{G} = \mathcal{F} \cup \{ A \}$. Since $X - A \notin \mathcal{F}$ and filters are upwards closed, every element of $\mathcal{F}$ must have $X - A$ as a subset. Therefore, the intersection of any element of $\mathcal{F}$ with $A$ is non-empty. Since $\mathcal{F}$ is closed under taking finite intersections, this implies that $\mathcal{F} \cup \{ A \}$ has the finite intersection property, so extends to a proper filter strictly larger than $\mathcal{F}$. So $\mathcal{F}$ is not an ultrafilter.

Thus, we have shown that if $\mathcal{F}$ is an ultrafilter, then for any $A \in \mathcal{P}(X)$ exactly one of $A \in \mathcal{F}$ and $X - A \in \mathcal{F}$ is true. The converse is easier to prove and the proof for it has been omitted.

Now to prove that if a union of two sets is in $\mathfrak{F}$, then so is one of the disjunct. So suppose $A \cup B \in \mathfrak{A}$. Then, $X - (A \cup B) = (X - A) \cap (X - B) \notin \mathfrak{F}$. So then either $X - A \notin \mathfrak{F}$, or $X - B \notin \mathfrak{F}$. So $A \in \mathfrak{F}$ or $B \in \mathfrak{F}$. $\blacksquare$

Theorem (Ultrafilter Lemma): Let $X$ be a set, and $\mathcal{F} \subseteq \mathcal{P}(X)$ a proper filter on $X$. Then there exists an ultrafilter $\mathcal{G} \subseteq \mathcal{P}(X)$ on $X$ such that $\mathcal{F} \subseteq \mathcal{G}$.

Proof. Consider the collection of proper filters on $X$ containing $\mathcal{F}$ \begin{align*} \mathfrak{F} = \left\{ \mathcal{G} \subset \mathcal{P}(X) \mid \mathcal{F} \subseteq \mathcal{G}, \text{ and $\mathcal{G}$ is a filter on $X$} \right\} \end{align*} partially orered by inclusion. If $\mathfrak{C} \subseteq \mathfrak{F}$ is a chain, then \begin{align*} \bigcup \mathfrak{C} \in \mathfrak{F} \end{align*} is an upper bound of $\mathfrak{C}$ in $\mathfrak{F}$. Thus, every chain in $\mathfrak{F}$ has an upper bound in $\mathfrak{F}$. Then by Zorn's lemma, there is a maximal element, that is, there is some $\mathcal{G} \in \mathfrak{F}$ which is not contained in any other filter in $\mathfrak{F}$. In other words, $\mathcal{G}$ is an ultrafilter. By definition of $\mathfrak{F}$, we have $\mathcal{F} \subseteq \mathcal{G}$ as well, so $\mathcal{G}$ is the desired ultrafilter containing $\mathcal{F}$.$\blacksquare$