# Ultrafilter

In the mathematical field of set theory, an **ultrafilter** on a given partially ordered set (poset) *P* is a certain subset of *P,* namely a maximal filter on *P*, that is, a proper filter on *P* that cannot be enlarged to a bigger proper filter on *P*.

If *X* is an arbitrary set, its power set ℘(*X*), ordered by set inclusion, is always a Boolean algebra and hence a poset, and (ultra)filters on ℘(*X*) are usually called "(ultra)filters on *X*".^{[note 1]} An ultrafilter on a set *X* may be considered as a finitely additive measure on *X.* In this view, every subset of *X* is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0), depending on whether it belongs to the given ultrafilter or not.^{[citation needed]}

Ultrafilters have many applications in set theory, model theory, and topology.^{[1]}^{:186}

## Ultrafilters on partial orders[edit]

In order theory, an **ultrafilter** is a subset of a partially ordered set that is maximal among all proper filters. This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.

Formally, if *P* is a set, partially ordered by (≤), then

- a subset
*F*of*P*is called a**filter**on*P*if*F*is nonempty,- for every
*x*,*y*in*F*, there is some element*z*in*F*such that*z*≤*x*and*z*≤*y*, and - for every
*x*in*F*and*y*in*P*,*x*≤*y*implies that*y*is in*F*, too;

- a proper subset
*U*of*P*is called an**ultrafilter**on*P*if*U*is a filter on*P*, and- there is no proper filter
*F*on*P*that properly extends*U*(that is, such that*U*is a proper subset of*F*).

## Special case: ultrafilter on a Boolean algebra[edit]

An important special case of the concept occurs if the considered poset is a Boolean algebra. In this case, ultrafilters are characterized by containing, for each element *a* of the Boolean algebra, exactly one of the elements *a* and ¬*a* (the latter being the Boolean complement of *a*):

If *P* is a Boolean algebra and *F* is a proper filter on *P*, then the following statements are equivalent:

*F*is an ultrafilter on*P*,*F*is a prime filter on*P*,- for each
*a*in*P*, either*a*is in*F*or (¬*a*) is in*F*.^{[1]}^{:186}

A proof of 1. ⇔ 2. is also given in (Burris, Sankappanavar, 2012, Corollary 3.13, p.133).^{[2]}

Moreover, ultrafilters on a Boolean algebra can be related to maximal ideals and homomorphisms to the 2-element Boolean algebra {true, false} (also known as 2-valued morphisms) as follows:

- Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
- Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
- Given an ultrafilter on a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".
^{[citation needed]}

## Special case: ultrafilter on the powerset of a set[edit]

Given an arbitrary set *X*, its power set ℘(*X*), ordered by set inclusion, is always a Boolean algebra; hence the results of the above section *Special case: Boolean algebra* apply. An (ultra)filter on ℘(*X*) is often called just an "(ultra)filter on *X*".^{[note 1]} The above formal definitions can be particularized to the powerset case as follows:

Given an arbitrary set *X*, an ultrafilter on ℘(*X*) is a set *U* consisting of subsets of *X* such that:

- The empty set is not an element of
*U*. - If
*A*and*B*are subsets of*X*, the set*A*is a subset of*B*, and*A*is an element of*U*, then*B*is also an element of*U*. - If
*A*and*B*are elements of*U*, then so is the intersection of*A*and*B*. - If
*A*is a subset of*X*, then either^{[note 2]}*A*or its relative complement*X*\*A*is an element of*U*.

A characterization is given by the following theorem.
A proper filter *U* on ℘(*X*) is an ultrafilter if any of the following conditions are true:

- There is no proper filter
*F*on ℘(*X*) strictly finer than*U*, that is,*U*⊆*F*implies*U*=*F*. - If a union
*A*∪*B*is in*U*, then*A*is in*U*or*B*is. - For each subset
*A*of*X*, either^{[note 2]}*A*is in*U*or (*X*\*A*) is.

There are no ultrafilters on ℘(*∅*).

Another way of looking at ultrafilters on a power set ℘(*X*) is as follows: for a given ultrafilter *U* define a function *m* on ℘(*X*) by setting *m*(*A*) = 1 if *A* is an element of *U* and *m*(*A*) = 0 otherwise. Such a function is called a 2-valued morphism. Then *m* is finitely additive, and hence a *content* on ℘(*X*), and every property of elements of *X* is either true almost everywhere or false almost everywhere. However, *m* is usually not *countably additive*, and hence does not define a measure in the usual sense.

For a filter *F* that is not an ultrafilter, one would say *m*(*A*) = 1 if *A* ∈ *F* and *m*(*A*) = 0 if *X* \ *A* ∈ *F*, leaving *m* undefined elsewhere.^{[citation needed]}^{[clarification needed]}

## Types and existence of ultrafilters[edit]

There are two very different types of ultrafilter: principal and free. A **principal** (or **fixed**, or **trivial**) ultrafilter is a filter containing a least element. Consequently, principal ultrafilters are of the form *F*_{a} = {*x* | *a* ≤ *x*} for some (but not all) elements *a* of the given poset. In this case *a* is called the *principal element* of the ultrafilter. Any ultrafilter that is not principal is called a **free** (or **non-principal**) ultrafilter.

For ultrafilters on a powerset ℘(*S*), a principal ultrafilter consists of all subsets of *S* that contain a given element *s* of *S*. Each ultrafilter on ℘(*S*) that is also a principal filter is of this form.^{[1]}^{:187} Therefore, an ultrafilter *U* on ℘(*S*) is principal if and only if it contains a finite set.^{[note 3]} If *S* is infinite, an ultrafilter *U* on ℘(*S*) is hence non-principal if and only if it contains the Fréchet filter of cofinite subsets of *S*.^{[note 4]}^{[citation needed]} If *S* is finite, each ultrafilter is principal.^{[1]}^{:187}

One can show that every filter on a Boolean algebra (or more generally, any subset with the finite intersection property) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice (AC) in the form of Zorn's lemma. On the other hand, the statement that every filter is contained in an ultrafilter does not imply AC. Indeed, it is equivalent to the Boolean prime ideal theorem (BPIT), a well-known intermediate point between the axioms of Zermelo–Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). In general, proofs involving the axiom of choice do not produce explicit examples of free ultrafilters, though it is possible to find explicit examples in some models of ZFC; for example, Gödel showed that this can be done in the constructible universe where one can write down an explicit global choice function. In ZF without the axiom of choice, it is possible that every ultrafilter is principal.^{[3]}

## Applications[edit]

Ultrafilters on powersets are useful in topology, especially in relation to compact Hausdorff spaces, and in model theory in the construction of ultraproducts and ultrapowers. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on Boolean algebras play a central role in Stone's representation theorem.

The set *G* of all ultrafilters of a poset *P* can be topologized in a natural way, that is in fact closely related to the above-mentioned representation theorem. For any element *a* of *P*, let *D*_{a} = {*U* ∈ *G* | *a* ∈ *U*}. This is most useful when *P* is again a Boolean algebra, since in this situation the set of all *D*_{a} is a base for a compact Hausdorff topology on *G*. Especially, when considering the ultrafilters on a powerset ℘(*S*), the resulting topological space is the Stone–Čech compactification of a discrete space of cardinality |*S*|.

The ultraproduct construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal numbers as an ultraproduct of the real numbers, the domain of discourse is extended from real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead the functions and relations are defined "pointwise modulo *U*", where *U* is an ultrafilter on the index set of the sequences; by Łoś' theorem, this preserves all properties of the reals that can be stated in first-order logic. If *U* is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory, non-principal ultrafilters are used to define the asymptotic cone of a group. This construction yields a rigorous way to consider *looking at the group from infinity*, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimits of metric spaces.

Gödel's ontological proof of God's existence uses as an axiom that the set of all "positive properties" is an ultrafilter.

In social choice theory, non-principal ultrafilters are used to define a rule (called a *social welfare function*) for aggregating the preferences of *infinitely* many individuals. Contrary to Arrow's impossibility theorem for *finitely* many individuals, such a rule satisfies the conditions (properties) that Arrow proposes
(e.g., Kirman and Sondermann, 1972).^{[4]}
Mihara (1997,^{[5]} 1999)^{[6]}
shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.

## Completeness[edit]

The **completeness** of an ultrafilter *U* on a powerset is the smallest cardinal κ such that there are κ elements of *U* whose intersection is not in *U*. The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least . An ultrafilter whose completeness is *greater* than —that is, the intersection of any countable collection of elements of *U* is still in *U*—is called **countably complete** or **σ-complete**.

The completeness of a countably complete nonprincipal ultrafilter on a powerset is always a measurable cardinal.^{[citation needed]}

## Ordering on ultrafilters[edit]

The **Rudin–Keisler ordering** (named after Mary Ellen Rudin and Howard Jerome Keisler) is a preorder on the class of powerset ultrafilters defined as follows: if *U* is an ultrafilter on ℘(*X*), and *V* an ultrafilter on ℘(*Y*), then *V* ≤_{RK} *U* if there exists a function *f*: *X* → *Y* such that

*C*∈*V*⇔*f*^{ -1}[*C*] ∈*U*

for every subset *C* of *Y*.

Ultrafilters *U* and *V* are called **Rudin–Keisler equivalent**, denoted *U* ≡_{RK} *V*, if there exist sets *A* ∈ *U* and *B* ∈ *V*, and a bijection *f*: *A* → *B* that satisfies the condition above. (If *X* and *Y* have the same cardinality, the definition can be simplified by fixing *A* = *X*, *B* = *Y*.)

It is known that ≡_{RK} is the kernel of ≤_{RK}, i.e., that *U* ≡_{RK} *V* if and only if *U* ≤_{RK} *V* and *V* ≤_{RK} *U*.^{[7]}

## Ultrafilters on ℘(*ω*)[edit]

There are several special properties that an ultrafilter on ℘(*ω*) may possess, which prove useful in various areas of set theory and topology.

- A non-principal ultrafilter
*U*is called a**P-point**(or**weakly selective**) if for every partition {*C*_{n}|*n*<*ω*} of*ω*such that ∀*n*<*ω*:*C*_{n}∉*U*, there exists some*A*∈*U*such that*A*∩*C*_{n}is a finite set for each*n*. - A non-principal ultrafilter
*U*is called**Ramsey**(or**selective**) if for every partition {*C*_{n}|*n*<*ω*} of*ω*such that ∀*n*<*ω*:*C*_{n}∉*U*, there exists some*A*∈*U*such that*A*∩*C*_{n}is a singleton set for each*n*.

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin proved that the continuum hypothesis implies the existence of Ramsey ultrafilters.^{[8]}
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom. Saharon Shelah later showed that it is consistent that there are no P-point ultrafilters.^{[9]} Therefore, the existence of these types of ultrafilters is independent of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space βω \ ω of non-principal ultrafilters. The name Ramsey comes from Ramsey's theorem. To see why, one can prove that an ultrafilter is Ramsey if and only if for every 2-coloring of [*ω*]^{2} there exists an element of the ultrafilter that has a homogeneous color.

An ultrafilter on ℘(*ω*) is Ramsey if and only if it is minimal in the Rudin–Keisler ordering of non-principal powerset ultrafilters.^{[citation needed]}

## Monad structure[edit]

The functor associating to any set *X* the set of *U*(*X*) of all ultrafilters on *X* forms a monad called the ultrafilter monad. The unit map

sends any element *x* in *X* to the principal ultrafilter given by *x*.

This monad admits a conceptual explanation as the codensity monad of the inclusion of the category of finite sets into the category of all sets.^{[10]}

## See also[edit]

## Notes[edit]

- ^
^{a}^{b}If*X*happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on ℘(*X*) or an (ultra)filter just on*X*is meant; both kinds of (ultra)filters are quite different. Some authors^{[citation needed]}use "(ultra)filter"*of*a partial ordered set" vs. "*on*an arbitrary set"; i.e. they write "(ultra)filter on*X*" to abbreviate "(ultra)filter of ℘(*X*)". - ^
^{a}^{b}Properties 1 and 3 imply that*A*and*X*\*A*cannot*both*be elements of*U*. **^**To see the "if" direction: If {*s*_{1},...,*s*_{n}} ∈*U*, then {*s*_{1}} ∈*U*, or ..., or {*s*_{n}} ∈*U*by induction on*n*, using Nr.2 of the above characterization theorem. That is, some {*s*_{i}} is the principal element of*U*.**^***U*is non-principal iff it contains no finite set, i.e. (by Nr.3 of the above characterization theorem) iff it contains every cofinite set, i.e. every member of the Fréchet filter.

## References[edit]

- ^
^{a}^{b}^{c}^{d}B.A. Davey and H.A. Priestley (1990).*Introduction to Lattices and Order*. Cambridge Mathematical Textbooks. Cambridge University Press. **^**L.J. Halbeisen (2012).*Combinatorial Set Theory*. Springer Monographs in Mathematics. Springer.**^**Kirman, A.; Sondermann, D. (1972). "Arrow's theorem, many agents, and invisible dictators".*Journal of Economic Theory*.**5**(2): 267–277. doi:10.1016/0022-0531(72)90106-8.**^**Mihara, H. R. (1997). "Arrow's Theorem and Turing computability" (PDF).*Economic Theory*.**10**(2): 257–276. CiteSeerX 10.1.1.200.520. doi:10.1007/s001990050157. Archived from the original (PDF) on 2011-08-12Reprinted in K. V. Velupillai , S. Zambelli, and S. Kinsella, ed., Computable Economics, International Library of Critical Writings in Economics, Edward Elgar, 2011.**^**Mihara, H. R. (1999). "Arrow's theorem, countably many agents, and more visible invisible dictators".*Journal of Mathematical Economics*.**32**(3): 267–277. CiteSeerX 10.1.1.199.1970. doi:10.1016/S0304-4068(98)00061-5.**^**Comfort&Negrepontis (1974), Corollary 9.3.**^**Rudin, Walter (1956), "Homogeneity problems in the theory of Čech compactifications",*Duke Mathematical Journal*,**23**(3): 409–419, doi:10.1215/S0012-7094-56-02337-7, hdl:10338.dmlcz/101493**^**Wimmers, Edward (March 1982), "The Shelah P-point independence theorem",*Israel Journal of Mathematics*,**43**(1): 28–48, doi:10.1007/BF02761683**^**Leinster, Tom (2013), "Codensity and the ultrafilter monad",*Theory and Applications of Categories*,**28**: 332–370, arXiv:1209.3606, Bibcode:2012arXiv1209.3606L

## Further reading[edit]

- Comfort, W. W. (1977), "Ultrafilters: some old and some new results",
*Bulletin of the American Mathematical Society*,**83**(4): 417–455, doi:10.1090/S0002-9904-1977-14316-4, ISSN 0002-9904, MR 0454893 - Comfort, W. W.; Negrepontis, S. (1974),
*The theory of ultrafilters*, Berlin, New York: Springer-Verlag, MR 0396267 - Ultrafilter in
*nLab*