nLab
ultrafilter

Ultrafilters

Definitions

An ultrafilter on a set SS is a collection FF of subsets of SS satisfying the axiom

AF(B 1,,B nF),(xAB 1B n). A \in F \;\Leftrightarrow\; \forall (B_1, \ldots, B_n \in F),\; \exists (x \in A \cap B_1 \cap \cdots \cap B_n) .

This is the only axiom necessary; from this, you can prove that FF is a filter. Alternatively, if we start by requiring FF to be a filter, then we need add only the axiom

AFBF,xAB. A \in F \;\Leftrightarrow\; \forall B \in F,\; \exists x \in A \cap B .

Or if we start by requiring FF to be a proper filter, then we need only the \Leftarrow 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 SS to any poset LL; notice that we speak of an ultrafilter on SS but an ultrafilter in LL. 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 FF on SS is an ultrafilter if, given any subset AA of SS, either AA or its complement belongs to FF; this version generalises to any Boolean algebra. Another way to define an ultrafilter in a Boolean algebra LL is as a Boolean-algebra homomorphism from LL to the set {,}\{\bot,\top\} of Boolean truth values.

Given an element xx of a set SS, the principal ultrafilter (on SS) at xx consists of every subset of SS to which xx belongs. An ultrafilter FF is fixed if the intersection of its elements is inhabited, in which case that intersection must be a singleton {x}\{x\} and FF is the principal ultrafilter at xx.

In contrast, if this intersection empty, then we call FF 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.

Free ultrafilters are important in nonstandard analysis and model theory, where the ultrafilter principle seems to be a necessity.

Category-theoretic interpretations

There are in fact many interrelated ways of defining ultrafilters. We present a few here.

Ultrafilters form a monad

For any set XX, let UXU X be the set of ultrafilters on XX. Principal ultrafilters provide an inclusion η:XUX\eta\colon X\to U X, which turns out to be the unit of a monad on SetSet, as briefly touched upon above. The multiplication can be described fairly explicitly. First of all, if AXA\subseteq X, define [A]UX[A]\subseteq U X to be the set of all ultrafilters containing AA. Then given UUX\mathcal{F} \in U U X, i.e. an ultrafilter of ultrafilters, we let μ()={A|[A]}\mu(\mathcal{F}) = \{ A | [A] \in \mathcal{F} \}; one can verify that this is an ultrafilter and makes UU into a monad. This monad is traditionally denoted β\beta.

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

(SetP=Set(,2) opBool op)(Bool opBool(,2)Set)(Set \stackrel{P = Set(-, \mathbf{2})^{op}}{\to} Bool^{op}) \; \; \dashv \; \; (Bool^{op} \stackrel{Bool(-, \mathbf{2})}{\to} Set)

whose corresponding monad Bool(P,2)Bool(P -, \mathbf{2}) is canonically identified with the ultrafilter monad β\beta. Another description (due to Kennison and Gildenhuys) is that it is the codensity monad induced from the full embedding FinSetFin \hookrightarrow Set of finite sets into SetSet. See Leinster for a full account, and some extensions.

Ultrafilters and coproducts

Observe that the canonical map

β(X)+β(Y)β(X+Y)\beta(X) + \beta(Y) \to \beta(X + Y)

is an isomorphism (for, each ultrafilter UU on X+YX + Y must contain exactly one of X,YX, Y; if it contains XX, then it is generated by the ultrafilter on XX given by {XA:AU}\{X \cap A: A \in U\}).

Theorem (R. Börger)

The endofunctor β\beta is terminal among endofunctors SetSetSet \to Set 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 β\beta, and that if F:SetSetF\colon Set \to Set is a monad which preserves finite coproducts, then the unique transformation FβF \to \beta is a morphism of monads.

Ultrafilters and codensity

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

Let i:FinSeti: Fin \to Set be the usual full inclusion of finite sets into sets. The restricted co-Yoneda embedding?

Sety op(Set Set) op(Set i) op(Set Fin) op,Set \stackrel{y^{op}}{\to} (Set^{Set})^{op} \stackrel{(Set^i)^{op}}{\to} (Set^{Fin})^{op},

taking a set XX contravariantly to the functor Set(X,i)Set(X, i-), has a right adjoint

Set Fin(,i):(Set Fin) opSetSet^{Fin}(-, i): (Set^{Fin})^{op} \to Set

(Note: this construction is dual to the familiar Kan construction?, which takes as input a functor F:ACF: A \to C from a small category to a cocomplete category, and produces as output an adjoint pair whose right adjoint is a functor CSet A opC \to Set^{A^{op}}; see for instance nerve and realization.)

The composite of these functors gives a monad SetSetSet \to Set which in fact is just the ultrafilter monad:

βSet Fin(Set(X,i),Set(1,i))\beta \cong Set^{Fin}(Set(X, i-), Set(1, i-))

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 β\beta is the terminal monad that restricts to 1 Fin1_{Fin}.

Ultrafilters and unbiased Boolean algebras

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

Fin +SetFin_+ \to Set

where Fin +Fin_+ is the category of inhabited finite sets. If XX is any set, there is an unbiased Boolean algebra

Set(X,i +):Fin +SetSet(X, i_+ -): Fin_+ \to Set

which may be called the unbiased power set. (Here i +:Fin +Seti_+: Fin_+ \to Set denotes the standard inclusion.) We may denote this by () X(-)^X for short. The inclusion functor i +i_+ is identified with () 1(-)^1, and corresponds to the Boolean algebra 22.

Definition

An ultrafilter on XX is a natural transformation () X() 1(-)^X \to (-)^1 in the category Prod(Fin +,Set)Prod(Fin_+, Set).

Of course this is the same as a natural transformation () X() 1(-)^X \to (-)^1 in the usual functor category Set Fin +Set^{Fin_+}. Such transformations are in bijection with transformations

Set(X,i)Set(1,i)Set(X, i-) \to Set(1, i-)

in Set FinSet^{Fin} used in the codensity monad description of ultrafilters.

Ultrafilters via other algebraic theories

There are other descriptions of ultrafilters, based on kk-valued Post algebras. Recall the proposition there:

  • Let M kM_k be the monoid of endofunctions on a kk-element set, for a finite set of cardinality k3k \geq 3. The forgetful functor U k:BoolAlgM k-SetU_k: BoolAlg \to M_k\text{-}Set is full and faithful.

Let us take for example k=3k = 3. Given a set XX, the functor U 3U_3 takes the unbiased Boolean algebra Set(X,i +)Set(X, i_+ -) to the set Set(X,3)=3 XSet(X, 3) = 3^X, regarded as a set equipped with the canonical (pointwise) action of Set(3,3)=M 3Set(3, 3) = M_3. It takes an ultrafilter on XX, i.e., an unbiased Boolean algebra map

Set(X,i +)Set(1,i +),Set(X, i_+ -) \to Set(1, i_+ -),

to a morphism of M 3M_3-sets

Set(X,3)3.Set(X, 3) \to 3.

The proposition implies that the mapping

β(X)M 3-Set(3 X,3)\beta(X) \to M_3\text{-}Set(3^X, 3)

is a natural bijection, giving us another way of viewing ultrafilters on XX, 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

BM 3SetB M_3 \to Set

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 β\beta is not isomorphic to the identity. Or, for the full inclusion

M SetM_{\mathbb{N}} \to Set

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.

Algebras of the ultrafilter monad

A theorem due to Ernest Manes is that the Eilenberg-Moore category of ultrafilter monad is the category of compact Hausdorff spaces with its obvious forgetful functor to SetSet.

  • In one direction, if XX is a compact Hausdorff space, then the corresponding algebra structure

    ξ:βXX\xi: \beta X \to X

    sends an ultrafilter FF on XX to the unique point in XX to which FF converges. (FF converges to xx if the filter of neighborhoods of xx is contained in FF; see convergence space.)

  • In the other direction, given an algebra structure ξ:βXX\xi\colon \beta X \to X, we define a topology by defining a set UXU \subseteq X to be open if

    ( xX FβXUFandξ(F)=x)xU(\forall_{x \in X} \forall_{F \in \beta X} U \in F \: and \: \xi(F) = x) \Rightarrow x \in U

    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 xx is the intersection of all ultrafilters that converge to xx. (The unit condition is that

    ξ(prin(x))=x\xi (prin(x)) = x

    so that the neighborhood filter of xx is contained in prin(x)prin(x), i.e., each neighborhood of xx contains xx.) 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.

In particular, βX\beta X can be equipped with a compact Hausdorff topology which is the free compact Hausdorff space generated by XX, or equivalently the Stone-Čech compactification of the discrete topology on XX.

The monad β\beta also extends to the bicategory RelRel 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 CC with small products, as a product-preserving functor

Kl(β) opCKl(\beta)^{op} \to C

where Kl(β)Kl(\beta) is the Kleisli category (or the full category of compact Hausdorff spaces whose objects are of the form βS\beta S).

References

  • R. Börger, Coproducts and Ultrafilters, J. Pure Appl. Alg. 46 (1987), 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)

  • Tom Leinster, Post to the categories list. (link)

  • Todd Trimble, Post to A Dialogue on Infinity. (link)

  • Bill Lawvere, Post to the categories list (link)

  • Tom Leinster, Definition of ultrafilter (blog post)

Revised on October 12, 2013 22:10:39 by Toby Bartels (98.19.41.253)