Ultrafilter

From AoPSWiki

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 ...$ 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.

Personal tools

Navigation

Search

Toolbox