An ultrafilter is a set theoretic structure.
An ultrafilter on a set is a non-empty filter on with the following property:
- For every set , either or its complement is an element of .
An ultrafilter is a finest filter, that is, if is an ultrafilter on , then there is no filter on such that . 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 be a trivial ultrafilter on . Then there exists an element such that is the set of subsets of which contain .
Proof. Let be a minimal element of . It suffices to show that contains a single element. Indeed, let be an element of . Since is an ultrafilter, one of the sets , must be an element of . But , so must be an element of . Hence , so , as desired.
Proposition 2. An ultrafilter is nontrivial if and only if it contains no finite element.
Proof. By Proposition 1, if is trivial, it contains a finite element. Converesly, suppose contains a finite element . Then the set of subsets of which are elements of , ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of , so is trivial.
Existence of Non-trivial Filters on Infinite Sets
We will now show that every infinite set has a non-trivial ultrafilter.
Lemma 3. Let be a filter with no finite elements on an infinite set , and let be a subset of . Suppose that for every element of , is infinite. Then there exists a filter with no finite elements on such that and .
Proof. Let denote set of subsets of which have subsets of the form , for . By hypothesis, contains no finite elements; it is therefore enough to show that is a filter on .
Evidently, the empty set is not an element of . If and are sets such that is a subset of and is an element of , then either is an element of and so is ; or has a subset of the form , for some , and so does . Either way, is an element of .
Finally, suppose and are elements of . If they are both elements of , then is in . Suppose one, say , is an element of , and the other is an element of . Then has a subset of the form , for some ; since is an element of , is an element of . If and are elements of , then has a subset of the form ; since is in , it follows that is in . In any case, is an element of , so is a filter on , as desired.
Lemma 4. Let be an infinite set, and let be a filter on with no finite elements. Then there exists a nontrivial ultrafilter on such that .
Proof. Let be the family of filters on that contain and have no finite elements. Evidently, every totally ordered subfamily of has an upper bound, so by Zorn's Lemma, has a maximal element . Since is a filter on with no finite elements, it suffices to show that for any set , either or is an element of .
We first prove that one of the sets has infinite intersection with every element of . Indeed, suppose this is not the case. Then there exist such that and are both finite. Evidently is an element of , but is finite, a contradiction.
Thus one of the sets, has infinite intersection with every element of . Without loss of generality, let this set be . Then by Lemma 3, there exists a filter with no finite elements such that is an element of and . But since is maximal, . It follows that .
Therefore for every set , one of the sets , is an element of . Therefore is a nontrivial ultrafilter on which contains , as desired.
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 alone.
Theorem 6. If is a filter on a set , then there exists an ultrafilter on such that .
Proof. If contains a finite set , then the subsets of this set which are elements of , ordered by inclusion, have a least element , which is therefore a subset of every element of . Let be an element of . Then the set of subsets of which contain constitute an ultrafilter finer than , as desired.
If contains no finite set, then by Lemma 4, there is a nontrivial ultrafilter on that is finer than , as desired.
Theorem 7. Every infinite set has a nontrivial ultrafilter.
Proof. Let be an infinite set. Then the set is a filter on with no finite element, so by Lemma 4, there is a non-trivial ultrafilter on of which is a subset.
Examples and Applications
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.