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.

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=24651"