Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Ultrafilter

An ultrafilter is a set theoretic structure.

Definition

An ultrafilter on a set $X$ is a non-empty filter $\mathcal{F}$ on $X$ with the following property:

  • For every set $A \subseteq X$, either $A$ or its complement is an element of $\mathcal{F}$.

An ultrafilter is a finest filter, that is, if $\mathcal{F}$ is an ultrafilter on $X$, then there is no filter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subsetneq \mathcal{F'}$. All finest filters are also ultrafilters; we will prove this later.

Types of Ultrafilters

An ultrafilter is said to be principle, or fixed, or trivial if it has a least element, i.e., an element which is a subset of all the others. Otherwise, an ultrafilter is said to be nontrivial, or free, or non-principle. Evidently, the only filters on finite sets are trivial.

Proposition 1. Let $\mathcal{F}$ be a trivial ultrafilter on $X$. Then there exists an element $a\in X$ such that $\mathcal{F}$ is the set of subsets of $X$ which contain $a$.

Proof. Let $A$ be a minimal element of $\mathcal{F}$. It suffices to show that $A$ contains a single element. Indeed, let $a$ be an element of $A$. Since $\mathcal{F}$ is an ultrafilter, one of the sets $\{ a\}$, $X \setminus \{a\}$ must be an element of $\mathcal{F}$. But $A \not\subseteq X \setminus \{a\}$, so $\{a\}$ must be an element of $\mathcal{F}$. Hence $A \subseteq \{a\}$, so $A = \{a\}$, as desired. $\blacksquare$

Proposition 2. An ultrafilter $\mathcal{F}$ is nontrivial if and only if it contains no finite element.

Proof. By Proposition 1, if $\mathcal{F}$ is trivial, it contains a finite element. Converesly, suppose $\mathcal{F}$ contains a finite element $A$. Then the set of subsets of $A$ which are elements of $\mathcal{F}$, ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of $\mathcal{F}$, so $\mathcal{F}$ is trivial. $\blacksquare$

Existence of Non-trivial Filters on Infinite Sets

We will now show that every infinite set has a non-trivial ultrafilter.

Lemma 3. Let $\mathcal{F}$ be a filter with no finite elements on an infinite set $X$, and let $A$ be a subset of $X$. Suppose that for every element $F$ of $\mathcal{F}$, $A \cap F$ is infinite. Then there exists a filter $\mathcal{F'}$ with no finite elements on $X$ such that $A \in \mathcal{F'}$ and $\mathcal{F} \subseteq \mathcal{F'}$.

Proof. Let $\mathcal{A}$ denote set of subsets of $X$ which have subsets of the form $F \cap A$, for $F \in \mathcal{F}$. By hypothesis, $\mathcal{A}$ contains no finite elements; it is therefore enough to show that $\mathcal{A} \cup \mathcal{F}$ is a filter on $X$.

Evidently, the empty set is not an element of $\mathcal{A} \cup \mathcal{F}$. If $B$ and $C$ are sets such that $B$ is a subset of $C$ and $B$ is an element of $\mathcal{A} \cup \mathcal{F}$, then either $B$ is an element of $\mathcal{F}$ and so is $C$; or $B$ has a subset of the form $A \cup F$, for some $F \in \mathcal{F}$, and so does $C$. Either way, $C$ is an element of $\mathcal{A} \cup \mathcal{F}$.

Finally, suppose $B$ and $C$ are elements of $\mathcal{A} \cup \mathcal{F}$. If they are both elements of $\mathcal{F}$, then $B\cap C$ is in $F$. Suppose one, say $B$, is an element of $\mathcal{F}$, and the other is an element of $\mathcal{A}$. Then $B \cap C$ has a subset of the form $A \cap (F \cap B)$, for some $F \in \mathcal{F}$; since $F \cap B$ is an element of $\mathcal{F}$, $B \cap C$ is an element of $\mathcal{A}$. If $B$ and $C$ are elements of $\mathcal{A}$, then $B \cap C$ has a subset of the form $(A \cap F_B) \cap (A \cap F_C) = A \cap (F_B \cap F_C)$; since $F_B \cap F_C$ is in $\mathcal{F}$, it follows that $B\cap C$ is in $\mathcal{A}$. In any case, $B \cap C$ is an element of $\mathcal{A} \cup \mathcal{F}$, so $\mathcal{A} \cup \mathcal{F}$ is a filter on $X$, as desired. $\blacksquare$


Lemma 4. Let $X$ be an infinite set, and let $\mathcal{F}$ be a filter on $X$ with no finite elements. Then there exists a nontrivial ultrafilter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subseteq \mathcal{F'}$.

Proof. Let $\mathfrak{F}$ be the family of filters on $X$ that contain $\mathcal{F}$ and have no finite elements. Evidently, every totally ordered subfamily of $\mathfrak{F}$ has an upper bound, so by Zorn's Lemma, $\mathfrak{F}$ has a maximal element $\mathcal{F'}$. Since $\mathcal{F'}$ is a filter on $X$ with no finite elements, it suffices to show that for any set $A \subset X$, either $A$ or $X \setminus A$ is an element of $\mathcal{F'}$.

We first prove that one of the sets $A, X \setminus A$ has infinite intersection with every element of $\mathcal{F'}$. Indeed, suppose this is not the case. Then there exist $B, C \in \mathcal{F'}$ such that $B \cup A$ and $C \cap (X \setminus A)$ are both finite. Evidently $B\cap C$ is an element of $\mathcal{F'}$, but \[B \cap C = (B \cap C) \cap \bigl( A \cap (X\setminus A) \bigr) = \bigl(C \cap (B \cap A) \bigr) \cup \bigl( B \cap C \cap (X \setminus A) \bigr)\] is finite, a contradiction.

Thus one of the sets, $A, X \setminus A$ has infinite intersection with every element of $\mathcal{F'}$. Without loss of generality, let this set be $A$. Then by Lemma 3, there exists a filter $\mathcal{F''}$ with no finite elements such that $A$ is an element of $\mathcal{F''}$ and $\mathcal{F'} \subseteq \mathcal{F''}$. But since $\mathcal{F'}$ is maximal, $\mathcal{F' = F''}$. It follows that $A \in \mathcal{F'}$.

Therefore for every set $A \subseteq X$, one of the sets $A$, $X \setminus A$ is an element of $\mathcal{F'}$. Therefore $\mathcal{F'}$ is a nontrivial ultrafilter on $X$ which contains $\mathcal{F}$, as desired. $\blacksquare$

Corollary 5. Every finest filter is an ultrafilter.

Note: The proof of Lemma 4 uses Zorn's Lemma, and it is indeed sufficient but not necessary. This is also known as the Ultrafilter lemma, which is implied by Zorn's Lemma but not equivalent to it. However, the Ultrafilter lemma cannot be proved in $\sf{ZF}$ alone.

Theorem 6. If $\mathcal{F}$ is a filter on a set $X$, then there exists an ultrafilter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subseteq \mathcal{F'}$.

Proof. If $\mathcal{F}$ contains a finite set $A$, then the subsets of this set which are elements of $\mathcal{F}$, ordered by inclusion, have a least element $B$, which is therefore a subset of every element of $\mathcal{F}$. Let $b$ be an element of $B$. Then the set of subsets of $X$ which contain $b$ constitute an ultrafilter $\mathcal{F'}$ finer than $\mathcal{F}$, as desired.

If $\mathcal{F}$ contains no finite set, then by Lemma 4, there is a nontrivial ultrafilter $\mathcal{F'}$ on $X$ that is finer than $\mathcal{F}$, as desired. $\blacksquare$

Theorem 7. Every infinite set has a nontrivial ultrafilter.

Proof. Let $X$ be an infinite set. Then the set $\{X\}$ is a filter on $X$ with no finite element, so by Lemma 4, there is a non-trivial ultrafilter on $X$ of which $\{X\}$ is a subset. $\blacksquare$

Examples and Applications

Ultrafilters are used in topology. They are also used to construct the hyperreals, which lie at the foundations of non-standard analysis.

Examples of non-trivial ultrafilters are difficult (if not impossible) to give, as the only known proof of their existance relies on the Axiom of Choice.


See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Ultrafilter&oldid=110289"