An ultrafilter on a set is a collection of subsets of satisfying the axiom
This is the only axiom necessary; from this, you can prove that is a filter. Alternatively, if we start by requiring to be a filter, then we need add only the axiom
Or if we start by requiring to be a proper filter, then we need only the half of this latter axiom.
We may also define an ultrafilter to be maximal among the proper filters. This definition generalises from the power set of to any poset ; notice that we speak of an ultrafilter on but an ultrafilter in . In a distributive lattice, every ultrafilter is prime; the converse holds in a Boolean algebra.
Using excluded middle, it is equivalent to say that a filter on is an ultrafilter if, given any subset of , either or its complement belongs to ; this version generalises to any Boolean algebra. Another way to define an ultrafilter in a Boolean algebra is as a Boolean-algebra homomorphism from to the set of Boolean truth values.
Given an element of a set , the principal ultrafilter (on ) at consists of every subset of to which belongs. An ultrafilter is fixed if the intersection of its elements is inhabited, in which case that intersection must be a singleton and is the principal ultrafilter at .
In contrast, if this intersection empty, then we call a free ultrafilter. It is possible, if one denies the axiom of choice, that every ultrafilter of subsets is fixed. In contrast, the ultrafilter principle (a weak form of the axiom of choice) states that any proper filter (in any Boolean lattice) may be extended to an ultrafilter. Then any infinite set has a free proper filter (such as the filter of cofinite subset?s) and so a free ultrafilter.
There are in fact many interrelated ways of defining ultrafilters. We present a few here.
For any set , let be the set of ultrafilters on . Principal ultrafilters provide an inclusion , which turns out to be the unit of a monad on , as briefly touched upon above. The multiplication can be described fairly explicitly. First of all, if , define to be the set of all ultrafilters containing . Then given , i.e. an ultrafilter of ultrafilters, we let ; one can verify that this is an ultrafilter and makes into a monad. This monad is traditionally denoted .
The ultrafilter monad can also be described as follows. The 2-element set carries a unique structure of Boolean algebra internal to the category of sets. When thus cast in the role of dualizing object, it induces an adjoint pair of functors
whose corresponding monad is canonically identified with the ultrafilter monad . Another description (due to Kennison and Gildenhuys) is that it is the codensity monad induced from the full embedding of finite sets into . See Leinster for a full account, and some extensions.
Observe that the canonical map
is an isomorphism (for, each ultrafilter on must contain exactly one of ; if it contains , then it is generated by the ultrafilter on given by ).
The endofunctor is terminal among endofunctors that preserve finite coproducts.
A topological proof of this fact has been given by Richter (see references).
This gives one universal characterization of the ultrafilter endofunctor. This theorem implies that there is precisely one monad structure on , and that if is a monad which preserves finite coproducts, then the unique transformation is a morphism of monads.
Another known universal characterization of the ultrafilter monad is via the concept of codensity monads. (This fact was recently (June 2011) mentioned by Tom Leinster at the categories list, but it also appears sparsely in the literature; see for instance Algebraic Theories, exercise 3.2.12(e).)
taking a set contravariantly to the functor , has a right adjoint
(Note: this construction is dual to the familiar Kan construction?, which takes as input a functor from a small category to a cocomplete category, and produces as output an adjoint pair whose right adjoint is a functor ; see for instance nerve and realization.)
The composite of these functors gives a monad which in fact is just the ultrafilter monad:
One way of considering the codensity monad formulation is that the ultrafilter functor is terminal among endofunctors whose restriction to the category of finite sets is the identity functor. This likewise gives the uniqueness of the monad structure, as well as the fact that is the terminal monad that restricts to .
The codensity monad description is related to the traditional description in terms of Boolean algebras; to see this more clearly, it helps to pass to unbiased Boolean algebras, which are equivalent to Boolean algebras.
Recall that an unbiased Boolean algebra is a product-preserving functor
which may be called the unbiased power set. (Here denotes the standard inclusion.) We may denote this by for short. The inclusion functor is identified with , and corresponds to the Boolean algebra .
An ultrafilter on is a natural transformation in the category .
Of course this is the same as a natural transformation in the usual functor category . Such transformations are in bijection with transformations
in used in the codensity monad description of ultrafilters.
There are other descriptions of ultrafilters, based on -valued Post algebras. Recall the proposition there:
Let us take for example . Given a set , the functor takes the unbiased Boolean algebra to the set , regarded as a set equipped with the canonical (pointwise) action of . It takes an ultrafilter on , i.e., an unbiased Boolean algebra map
to a morphism of -sets
The proposition implies that the mapping
is a natural bijection, giving us another way of viewing ultrafilters on , this time involving only unary operations.
This is of course another codensity monad description in disguise; this time the codensity monad is induced by the full inclusion
of the category of endofunctions on the 3-element set into the category of sets. The results of this section say that the ultrafilter monad is the codensity monad for this particular inclusion.
In a post to the categories list (see references), Bill Lawvere remarks that large cardinal hypotheses can be formulated as obstructions to similar codensity monads being isomorphic to the identity. For example, the existence of infinite sets is equivalent (assuming the ultrafilter principle) to the fact that is not isomorphic to the identity. Or, for the full inclusion
the existence of an uncountable measurable cardinal is equivalent (in ZFC) to the fact that the induced codensity monad is not isomorphic to the identity (i.e., the first uncountable measurable cardinal is where the first “jump” takes place). Lawvere gives a couple more examples of a more geometric nature.
In one direction, if is a compact Hausdorff space, then the corresponding algebra structure
sends an ultrafilter on to the unique point in to which converges. ( converges to if the filter of neighborhoods of is contained in ; see convergence space.)
In the other direction, given an algebra structure , we define a topology by defining a set to be open if
The sense of this is that a set is open if it is a neighborhood of each of its points, and the neighborhood filter of is the intersection of all ultrafilters that converge to . (The unit condition is that
so that the neighborhood filter of is contained in , i.e., each neighborhood of contains .) It is not hard to verify that this condition indeed defines a topology. In fact, the topology is compact Hausdorff, essentially because compactness is equivalent to having every ultrafilter converge to some point, and Hausdorffness to having that point be unique.
The monad also extends to the bicategory of sets and binary relations. It was observed by Barr that the generalized multicategories defined relative to this extension can be identified with arbitrary topological spaces; see relational beta-module. Thus, compact Hausdorff spaces are to topological spaces as monoidal categories are to multicategories.
By exploiting the connection between monads and algebraic theories, it is possible to define a compact Hausdorff object in any category with small products, as a product-preserving functor
where is the Kleisli category (or the full category of compact Hausdorff spaces whose objects are of the form ).
If is a finite set, then all ultrafilters on are principal and the number of them is the cardinality of .
R. Börger, Coproducts and Ultrafilters , JPAA 46 (1987) pp.35-47.
E. Manes, Algebraic Theories , Graduate Texts in Mathematics 26, Springer-Verlag, 1976.
G. Richter, Axiomatizing the Category of Compact Hausdorff Spaces, Categories at Work (ed. Herrlich and Porst), Heldermann-Verlag (1991), 199-215. (link)
H. Volger, Ultrafilters, ultrapowers and finiteness in a topos , JPAA 6 (1975) pp.345-356.