In themathematical field ofset theory, anultrafilter on aset${\displaystyle X}$ is amaximal filter on the set${\displaystyle X.}$ In other words, it is a collection of subsets of${\displaystyle X}$ that satisfies the definition of afilter on${\displaystyle X}$ and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of${\displaystyle X}$ that is also a filter. (In the above, by definition a filter on a set does not contain the empty set.) Equivalently, an ultrafilter on the set${\displaystyle X}$ can also be characterized as a filter on${\displaystyle X}$ with the property that for everysubset${\displaystyle A}$ of${\displaystyle X}$ either${\displaystyle A}$ or its complement${\displaystyle X\setminus A}$ belongs to the ultrafilter.

Ultrafilters on sets are an important special instance ofultrafilters on partially ordered sets, where thepartially ordered set consists of thepower set${\displaystyle \mathcal{P}(X)}$ and the partial order issubset inclusion${\displaystyle \subseteq .}$ This article deals specifically with ultrafilters on a set and does not cover the more general notion.

There are two types of ultrafilter on a set. Aprincipal ultrafilter on${\displaystyle X}$ is the collection of all subsets of${\displaystyle X}$ that contain a fixed element${\displaystyle x\in X}$. The ultrafilters that are not principal are thefree ultrafilters. The existence of free ultrafilters on any infinite set is implied by theultrafilter lemma, which can be proven inZFC. On the other hand, there exist models ofZF where every ultrafilter on a set is principal.

Ultrafilters have many applications in set theory,model theory, andtopology.^[1]: 186 Usually, only free ultrafilters lead to non-trivial constructions. For example, anultraproduct modulo a principal ultrafilter is always isomorphic to one of the factors, while an ultraproduct modulo a free ultrafilter usually has a more complex structure.

Given an arbitrary set${\displaystyle X,}$ anultrafilter on${\displaystyle X}$ is a non-emptyfamily${\displaystyle U}$ of subsets of${\displaystyle X}$ such that:

1. Proper ornon-degenerate: The empty set is not an element of${\displaystyle U.}$
2. Upward closed in${\displaystyle X}$: If${\displaystyle A\in U}$ and if${\displaystyle B\subseteq X}$ is any superset of${\displaystyle A}$ (that is, if${\displaystyle A\subseteq B\subseteq X}$) then${\displaystyle B\in U.}$
3. π−system: If${\displaystyle A}$ and${\displaystyle B}$ are elements of${\displaystyle U}$ then so is theirintersection${\displaystyle A\cap B.}$
4. If${\displaystyle A\subseteq X}$ then either${\displaystyle A}$ or its complement${\displaystyle X\setminus A}$ is an element of${\displaystyle U.}$^{[note 1]}

Properties (1), (2), and (3) are the defining properties of afilter on${\displaystyle X.}$ Some authors do not include non-degeneracy (which is property (1) above) in their definition of "filter". However, the definition of "ultrafilter" (and also of "prefilter" and "filter subbase") always includes non-degeneracy as a defining condition. This article requires that all filters be proper although a filter might be described as "proper" for emphasis.

Afiltersubbase is a non-empty family of sets that has thefinite intersection property (i.e. all finite intersections are non-empty). Equivalently, a filter subbase is a non-empty family of sets that is contained insome (proper) filter. The smallest (relative to${\displaystyle \subseteq }$) filter containing a given filter subbase is said to begenerated by the filter subbase.

Theupward closure in${\displaystyle X}$ of a family of sets${\displaystyle P}$ is the set

${\displaystyle P^{\uparrow X}:=\{S:A\subseteq S\subseteq X\text{ for some }A\in P\}.}$

Aprefilter orfilter base is a non-empty and proper (i.e.${\displaystyle \varnothing \notin P}$) family of sets${\displaystyle P}$ that isdownward directed, which means that if${\displaystyle B,C\in P}$ then there exists some${\displaystyle A\in P}$ such that${\displaystyle A\subseteq B\cap C.}$ Equivalently, a prefilter is any family of sets${\displaystyle P}$ whose upward closure${\displaystyle P^{\uparrow X}}$ is a filter, in which case this filter is called thefilter generated by${\displaystyle P}$ and${\displaystyle P}$ is said to bea filter basefor${\displaystyle P^{\uparrow X}.}$

Thedual in${\displaystyle X}$^[2] of a family of sets${\displaystyle P}$ is the set${\displaystyle X\setminus P:=\{X\setminus B:B\in P\}.}$ For example, the dual of thepower set${\displaystyle \mathcal{P}(X)}$ is itself:${\displaystyle X\setminus \mathcal{P}(X)=\mathcal{P}(X).}$ A family of sets is a proper filter on${\displaystyle X}$ if and only if its dual is a properideal on${\displaystyle X}$ ("proper" means not equal to the power set).

A family${\displaystyle U\ne \varnothing }$ of subsets of${\displaystyle X}$ is calledultra if${\displaystyle \varnothing \notin U}$ and any of the following equivalent conditions are satisfied:^[2][3]

1. For every set${\displaystyle S\subseteq X}$ there exists some set${\displaystyle B\in U}$ such that${\displaystyle B\subseteq S}$ or${\displaystyle B\subseteq X\setminus S}$ (or equivalently, such that${\displaystyle B\cap S}$ equals${\displaystyle B}$ or${\displaystyle \varnothing }$).
2. For every set${\displaystyle S\subseteq \bigcup _{B\in U}B}$ there exists some set${\displaystyle B\in U}$ such that${\displaystyle B\cap S}$ equals${\displaystyle B}$ or${\displaystyle \varnothing .}$
   • Here,${\displaystyle \bigcup _{B\in U}B}$ is defined to be the union of all sets in${\displaystyle U.}$
   • This characterization of "${\displaystyle U}$ is ultra" does not depend on the set${\displaystyle X,}$ so mentioning the set${\displaystyle X}$ is optional when using the term "ultra."
3. Forevery set${\displaystyle S}$ (not necessarily even a subset of${\displaystyle X}$) there exists some set${\displaystyle B\in U}$ such that${\displaystyle B\cap S}$ equals${\displaystyle B}$ or${\displaystyle \varnothing .}$
   • If${\displaystyle U}$ satisfies this condition then so doesevery superset${\displaystyle V\supseteq U.}$ In particular, a set${\displaystyle V}$ is ultra if and only if${\displaystyle \varnothing \notin V}$ and${\displaystyle V}$ contains as a subset some ultra family of sets.

A filter subbase that is ultra is necessarily a prefilter.^{[proof 1]}

The ultra property can now be used to define both ultrafilters and ultra prefilters:

Anultra prefilter^[2][3] is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra.

Anultrafilter^[2][3] on${\displaystyle X}$ is a (proper) filter on${\displaystyle X}$ that is ultra. Equivalently, it is any filter on${\displaystyle X}$ that is generated by an ultra prefilter.

Ultra prefilters as maximal prefilters

To characterize ultra prefilters in terms of "maximality," the following relation is needed.

Given two families of sets${\displaystyle M}$ and${\displaystyle N,}$ the family${\displaystyle M}$ is said to becoarser^[4][5] than${\displaystyle N,}$ and${\displaystyle N}$ isfiner than andsubordinate to${\displaystyle M,}$ written${\displaystyle M\le N}$ orN ⊢M, if for every${\displaystyle C\in M,}$ there is some${\displaystyle F\in N}$ such that${\displaystyle F\subseteq C.}$ The families${\displaystyle M}$ and${\displaystyle N}$ are calledequivalent if${\displaystyle M\le N}$ and${\displaystyle N\le M.}$ The families${\displaystyle M}$ and${\displaystyle N}$ arecomparable if one of these sets is finer than the other.^[4]

The subordination relationship, i.e.${\displaystyle \ge ,}$ is apreorder so the above definition of "equivalent" does form anequivalence relation. If${\displaystyle M\subseteq N}$ then${\displaystyle M\le N}$ but the converse does not hold in general. However, if${\displaystyle N}$ is upward closed, such as a filter, then${\displaystyle M\le N}$ if and only if${\displaystyle M\subseteq N.}$ Every prefilter is equivalent to the filter that it generates. This shows that it is possible for filters to be equivalent to sets that are not filters.

If two families of sets${\displaystyle M}$ and${\displaystyle N}$ are equivalent then either both${\displaystyle M}$ and${\displaystyle N}$ are ultra (resp. prefilters, filter subbases) or otherwise neither one of them is ultra (resp. a prefilter, a filter subbase). In particular, if a filter subbase is not also a prefilter, then it isnot equivalent to the filter or prefilter that it generates. If${\displaystyle M}$ and${\displaystyle N}$ are both filters on${\displaystyle X}$ then${\displaystyle M}$ and${\displaystyle N}$ are equivalent if and only if${\displaystyle M=N.}$ If a proper filter (resp. ultrafilter) is equivalent to a family of sets${\displaystyle M}$ then${\displaystyle M}$ is necessarily a prefilter (resp. ultra prefilter). Using the following characterization, it is possible to define prefilters (resp. ultra prefilters) using only the concept of filters (resp. ultrafilters) and subordination:

An arbitrary family of sets is a prefilter if and only it is equivalent to a (proper) filter.

An arbitrary family of sets is an ultra prefilter if and only it is equivalent to an ultrafilter.

Amaximal prefilter on${\displaystyle X}$^[2][3] is a prefilter${\displaystyle U\subseteq \mathcal{P}(X)}$ that satisfies any of the following equivalent conditions:

1. ${\displaystyle U}$ is ultra.
2. ${\displaystyle U}$ ismaximal on${\displaystyle \mathrm{Prefilters}(X)}$ with respect to${\displaystyle \le ,}$ meaning that if${\displaystyle P\in \mathrm{Prefilters}(X)}$ satisfies${\displaystyle U\le P}$ then${\displaystyle P\le U.}$^[3]
3. There is no prefilter properly subordinate to${\displaystyle U.}$^[3]
4. If a (proper) filter${\displaystyle F}$ on${\displaystyle X}$ satisfies${\displaystyle U\le F}$ then${\displaystyle F\le U.}$
5. The filter on${\displaystyle X}$ generated by${\displaystyle U}$ is ultra.

There are no ultrafilters on theempty set, so it is henceforth assumed that${\displaystyle X}$ is nonempty.

A filtersubbase${\displaystyle U}$ on${\displaystyle X}$ is an ultrafilter on${\displaystyle X}$ if and only if any of the following equivalent conditions hold:^[2][3]

1. for any${\displaystyle S\subseteq X,}$ either${\displaystyle S\in U}$ or${\displaystyle X\setminus S\in U.}$
2. ${\displaystyle U}$ is a maximal filter subbase on${\displaystyle X,}$ meaning that if${\displaystyle F}$ is any filter subbase on${\displaystyle X}$ then${\displaystyle U\subseteq F}$ implies${\displaystyle U=F.}$^[6]

A (proper) filter${\displaystyle U}$ on${\displaystyle X}$ is an ultrafilter on${\displaystyle X}$ if and only if any of the following equivalent conditions hold:

1. ${\displaystyle U}$ is ultra;
2. ${\displaystyle U}$ is generated by an ultra prefilter;
3. For any subset${\displaystyle S\subseteq X,}$${\displaystyle S\in U}$ or${\displaystyle X\setminus S\in U.}$^[6]
   • So an ultrafilter${\displaystyle U}$ decides for every${\displaystyle S\subseteq X}$ whether${\displaystyle S}$ is "large" (i.e.${\displaystyle S\in U}$) or "small" (i.e.${\displaystyle X\setminus S\in U}$).^[7]
4. For each subset${\displaystyle A\subseteq X,}$ either^{[note 1]}${\displaystyle A}$ is in${\displaystyle U}$ or (${\displaystyle X\setminus A}$) is.
5. ${\displaystyle U\cup (X\setminus U)=\mathcal{P}(X).}$ This condition can be restated as:${\displaystyle \mathcal{P}(X)}$ is partitioned by${\displaystyle U}$ and its dual${\displaystyle X\setminus U.}$
   • The sets${\displaystyle P}$ and${\displaystyle X\setminus P}$ are disjoint for all prefilters${\displaystyle P}$ on${\displaystyle X.}$
6. ${\displaystyle \mathcal{P}(X)\setminus U=\left\{S\in \mathcal{P}(X):S\notin U\right\}}$ is an ideal on${\displaystyle X.}$^[6]
7. For any finite family${\displaystyle S_1,\dots ,S_n}$ of subsets of${\displaystyle X}$ (where${\displaystyle n\ge 1}$), if${\displaystyle S_1\cup \cdots \cup S_n\in U}$ then${\displaystyle S_i\in U}$ for some index${\displaystyle i.}$
   • In words, a "large" set cannot be a finite union of sets none of which is large.^[8]
8. For any${\displaystyle R,S\subseteq X,}$ if${\displaystyle R\cup S=X}$ then${\displaystyle R\in U}$ or${\displaystyle S\in U.}$
9. For any${\displaystyle R,S\subseteq X,}$ if${\displaystyle R\cup S\in U}$ then${\displaystyle R\in U}$ or${\displaystyle S\in U}$ (a filter with this property is called aprime filter).
10. For any${\displaystyle R,S\subseteq X,}$ if${\displaystyle R\cup S\in U}$ and${\displaystyle R\cap S=\varnothing }$ theneither${\displaystyle R\in U}$ or${\displaystyle S\in U.}$
11. ${\displaystyle U}$ is a maximal filter; that is, if${\displaystyle F}$ is a filter on${\displaystyle X}$ such that${\displaystyle U\subseteq F}$ then${\displaystyle U=F.}$ Equivalently,${\displaystyle U}$ is a maximal filter if there is no filter${\displaystyle F}$ on${\displaystyle X}$ that contains${\displaystyle U}$ as aproper subset (that is, no filter is strictlyfiner than${\displaystyle U}$).^[6]

If${\displaystyle \mathcal{B}\subseteq \mathcal{P}(X)}$ then itsgrill on${\displaystyle X}$ is the family$${\displaystyle {\mathcal{B}}^{\mathrm{\#}X}:=\{S\subseteq X:S\cap B\ne \varnothing \text{ for all }B\in \mathcal{B}\}}$$where${\displaystyle {\mathcal{B}}^{\mathrm{\#}}}$ may be written if${\displaystyle X}$ is clear from context.If${\displaystyle \mathcal{F}}$ is a filter then${\displaystyle {\mathcal{F}}^{\mathrm{\#}}}$ is the set of positive sets with respect to${\displaystyle \mathcal{F}}$ and is usually written as${\displaystyle {\mathcal{F}}^{+}}$.For example,${\displaystyle {\varnothing }^{\mathrm{\#}}=\mathcal{P}(X)}$ and if${\displaystyle \varnothing \in \mathcal{B}}$ then${\displaystyle {\mathcal{B}}^{\mathrm{\#}}=\varnothing .}$ If${\displaystyle \mathcal{A}\subseteq \mathcal{B}}$ then${\displaystyle {\mathcal{B}}^{\mathrm{\#}}\subseteq {\mathcal{A}}^{\mathrm{\#}}}$ and moreover, if${\displaystyle \mathcal{B}}$ is a filter subbase then${\displaystyle \mathcal{B}\subseteq {\mathcal{B}}^{\mathrm{\#}}.}$^[9] The grill${\displaystyle {\mathcal{B}}^{\mathrm{\#}X}}$ is upward closed in${\displaystyle X}$ if and only if${\displaystyle \varnothing \notin \mathcal{B},}$ which will henceforth be assumed. Moreover,${\displaystyle {\mathcal{B}}^{\mathrm{\#}\mathrm{\#}}={\mathcal{B}}^{\uparrow X}}$ so that${\displaystyle \mathcal{B}}$ is upward closed in${\displaystyle X}$ if and only if${\displaystyle {\mathcal{B}}^{\mathrm{\#}\mathrm{\#}}=\mathcal{B}.}$

The grill of a filter on${\displaystyle X}$ is called afilter-grill on${\displaystyle X.}$^[9] For any${\displaystyle \varnothing \ne \mathcal{B}\subseteq \mathcal{P}(X),}$${\displaystyle \mathcal{B}}$ is a filter-grill on${\displaystyle X}$ if and only if (1)${\displaystyle \mathcal{B}}$ is upward closed in${\displaystyle X}$ and (2) for all sets${\displaystyle R}$ and${\displaystyle S,}$ if${\displaystyle R\cup S\in \mathcal{B}}$ then${\displaystyle R\in \mathcal{B}}$ or${\displaystyle S\in \mathcal{B}.}$ The grill operation${\displaystyle \mathcal{F}\mapsto {\mathcal{F}}^{\mathrm{\#}X}}$ induces a bijection

${\displaystyle {\bullet }^{\mathrm{\#}X}:\mathrm{Filters}(X)\to \mathrm{FilterGrills}(X)}$

whose inverse is also given by${\displaystyle \mathcal{F}\mapsto {\mathcal{F}}^{\mathrm{\#}X}.}$^[9] If${\displaystyle \mathcal{F}\in \mathrm{Filters}(X)}$ then${\displaystyle \mathcal{F}}$ is a filter-grill on${\displaystyle X}$ if and only if${\displaystyle \mathcal{F}={\mathcal{F}}^{\mathrm{\#}X},}$^[9] or equivalently, if and only if${\displaystyle \mathcal{F}}$ is an ultrafilter on${\displaystyle X.}$^[9] That is, a filter on${\displaystyle X}$ is a filter-grill if and only if it is ultra. For any non-empty${\displaystyle \mathcal{F}\subseteq \mathcal{P}(X),}$${\displaystyle \mathcal{F}}$ is both a filter on${\displaystyle X}$ and a filter-grill on${\displaystyle X}$ if and only if (1)${\displaystyle \varnothing \notin \mathcal{F}}$ and (2) for all${\displaystyle R,S\subseteq X,}$ the following equivalences hold:

${\displaystyle R\cup S\in \mathcal{F}}$ if and only if${\displaystyle R,S\in \mathcal{F}}$ if and only if${\displaystyle R\cap S\in \mathcal{F}.}$^[9]

If${\displaystyle P}$ is any non-empty family of sets then theKernel of${\displaystyle P}$ is the intersection of all sets in${\displaystyle P:}$^[10]$${\displaystyle \ker P:=\bigcap _{B\in P}B.}$$

A non-empty family of sets${\displaystyle P}$ is called:

• free if${\displaystyle \ker P=\varnothing }$ andfixed otherwise (that is, if${\displaystyle \ker P\ne \varnothing }$).
• principal if${\displaystyle \ker P\in P.}$
• principal at a point if${\displaystyle \ker P\in P}$ and${\displaystyle \ker P}$ is a singleton set; in this case, if${\displaystyle \ker P=\{x\}}$ then${\displaystyle P}$ is said to beprincipal at${\displaystyle x.}$

If a family of sets${\displaystyle P}$ is fixed then${\displaystyle P}$ is ultra if and only if some element of${\displaystyle P}$ is a singleton set, in which case${\displaystyle P}$ will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter${\displaystyle P}$ is ultra if and only if${\displaystyle \ker P}$ is a singleton set. A singleton set is ultra if and only if its sole element is also a singleton set.

The next theorem shows that every ultrafilter falls into one of two categories: either it is free or else it is a principal filter generated by a single point.

Every filter on${\displaystyle X}$ that is principal at a single point is an ultrafilter, and if in addition${\displaystyle X}$ is finite, then there are no ultrafilters on${\displaystyle X}$ other than these.^[10] In particular, if a set${\displaystyle X}$ has finite cardinality then there are exactly${\displaystyle n}$ ultrafilters on${\displaystyle X}$ and those are the ultrafilters generated by each singleton subset of${\displaystyle X.}$ Consequently, free ultrafilters can only exist on an infinite set.

If${\displaystyle X}$ is an infinite set then there are as many ultrafilters over${\displaystyle X}$ as there are families of subsets of${\displaystyle X;}$ explicitly, if${\displaystyle X}$ has infinite cardinality${\displaystyle \kappa }$ then the set of ultrafilters over${\displaystyle X}$ has the same cardinality as${\displaystyle \mathcal{P}(\mathcal{P}(X));}$ that cardinality being${\displaystyle 2^{2^{\kappa }}.}$^[11]

If${\displaystyle U}$ and${\displaystyle S}$ are families of sets such that${\displaystyle U}$ is ultra,${\displaystyle \varnothing \notin S,}$ and${\displaystyle U\le S,}$ then${\displaystyle S}$ is necessarily ultra. A filter subbase${\displaystyle U}$ that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by${\displaystyle U}$ to be ultra.

Suppose${\displaystyle U\subseteq \mathcal{P}(X)}$ is ultra and${\displaystyle Y}$ is a set. The trace${\displaystyle U{|}_Y:=\{B\cap Y:B\in U\}}$ is ultra if and only if it does not contain the empty set. Furthermore, at least one of the sets${\displaystyle U{|}_Y\setminus \{\varnothing \}}$ and${\displaystyle U{|}_{X\setminus Y}\setminus \{\varnothing \}}$ will be ultra (this result extends to any finite partition of${\displaystyle X}$). If${\displaystyle F_1,\dots ,F_n}$ are filters on${\displaystyle X,}$${\displaystyle U}$ is an ultrafilter on${\displaystyle X,}$ and${\displaystyle F_1\cap \cdots \cap F_n\le U,}$ then there is some${\displaystyle F_i}$ that satisfies${\displaystyle F_i\le U.}$^[12] This result is not necessarily true for an infinite family of filters.^[12]

The image under a map${\displaystyle f:X\to Y}$ of an ultra set${\displaystyle U\subseteq \mathcal{P}(X)}$ is again ultra and if${\displaystyle U}$ is an ultra prefilter then so is${\displaystyle f(U).}$ The property of being ultra is preserved under bijections. However, the preimage of an ultrafilter is not necessarily ultra, not even if the map is surjective. For example, if${\displaystyle X}$ has more than one point and if the range of${\displaystyle f:X\to Y}$ consists of a single point${\displaystyle \{y\}}$ then${\displaystyle \{y\}}$ is an ultra prefilter on${\displaystyle Y}$ but its preimage is not ultra. Alternatively, if${\displaystyle U}$ is a principal filter generated by a point in${\displaystyle Y\setminus f(X)}$ then the preimage of${\displaystyle U}$ contains the empty set and so is not ultra.

The elementary filter induced by an infinite sequence, all of whose points are distinct, isnot an ultrafilter.^[12] If${\displaystyle n=2,}$ then${\displaystyle U_n}$ denotes the set consisting all subsets of${\displaystyle X}$ having cardinality${\displaystyle n,}$ and if${\displaystyle X}$ contains at least${\displaystyle 2n-1}$ (${\displaystyle =3}$) distinct points, then${\displaystyle U_n}$ is ultra but it is not contained in any prefilter. This example generalizes to any integer${\displaystyle n>1}$ and also to${\displaystyle n=1}$ if${\displaystyle X}$ contains more than one element. Ultra sets that are not also prefilters are rarely used.

For every${\displaystyle S\subseteq X\times X}$ and every${\displaystyle a\in X,}$ let${\displaystyle S{|}_{\{a\}\times X}:=\{y\in X:(a,y)\in S\}.}$ If${\displaystyle \mathcal{U}}$ is an ultrafilter on${\displaystyle X}$ then the set of all${\displaystyle S\subseteq X\times X}$ such that${\displaystyle \left\{a\in X:S{|}_{\{a\}\times X}\in \mathcal{U}\right\}\in \mathcal{U}}$ is an ultrafilter on${\displaystyle X\times X.}$^[13]

Thefunctor associating to any set${\displaystyle X}$ the set of${\displaystyle U(X)}$ of all ultrafilters on${\displaystyle X}$ forms amonad called theultrafilter monad. The unit map$${\displaystyle X\to U(X)}$$sends any element${\displaystyle x\in X}$ to the principal ultrafilter given by${\displaystyle x.}$

Thisultrafilter monad is thecodensity monad of the inclusion of thecategory of finite sets into thecategory of all sets,^[14] which gives a conceptual explanation of this monad.

Similarly, theultraproduct monad is the codensity monad of the inclusion of the category of finitefamilies of sets into the category of all families of set. So in this sense,ultraproducts are categorically inevitable.^[14]

The ultrafilter lemma was first proved byAlfred Tarski in 1930.^[13]

The ultrafilter lemma is equivalent to each of the following statements:

1. For every prefilter on a set${\displaystyle X,}$ there exists a maximal prefilter on${\displaystyle X}$ subordinate to it.^[2]
2. Every proper filter subbase on a set${\displaystyle X}$ is contained in some ultrafilter on${\displaystyle X.}$

A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.^{[4][note 2]}

The following results can be proven using the ultrafilter lemma. A free ultrafilter exists on a set${\displaystyle X}$ if and only if${\displaystyle X}$ is infinite. Every proper filter is equal to the intersection of all ultrafilters containing it.^[4] Since there are filters that are not ultra, this shows that the intersection of a family of ultrafilters need not be ultra. A family of sets${\displaystyle \mathbb{F}\ne \varnothing }$ can be extended to a free ultrafilter if and only if the intersection of any finite family of elements of${\displaystyle \mathbb{F}}$ is infinite.

Throughout this section,ZF refers toZermelo–Fraenkel set theory andZFC refers toZF with theAxiom of Choice (AC). The ultrafilter lemma is independent ofZF. That is, there existmodels in which the axioms ofZF hold but the ultrafilter lemma does not. There also exist models ofZF in which every ultrafilter is necessarily principal.

Every filter that contains a singleton set is necessarily an ultrafilter and given${\displaystyle x\in X,}$ the definition of the discrete ultrafilter${\displaystyle \{S\subseteq X:x\in S\}}$ does not require more thanZF. If${\displaystyle X}$ is finite then every ultrafilter is a discrete filter at a point; consequently, free ultrafilters can only exist on infinite sets. In particular, if${\displaystyle X}$ is finite then the ultrafilter lemma can be proven from the axiomsZF. The existence of free ultrafilter on infinite sets can be proven if the axiom of choice is assumed. More generally, the ultrafilter lemma can be proven by using theaxiom of choice, which in brief states that anyCartesian product of non-empty sets is non-empty. UnderZF, the axiom of choice is, in particular,equivalent to (a)Zorn's lemma, (b)Tychonoff's theorem, (c) the weak form of the vector basis theorem (which states that every vector space has abasis), (d) the strong form of the vector basis theorem, and other statements. However, the ultrafilter lemma is strictly weaker than the axiom of choice. While free ultrafilters can be proven to exist, it isnot possible to construct an explicit example of a free ultrafilter (using onlyZF and the ultrafilter lemma); that is, free ultrafilters are intangible.^[15]Alfred Tarski proved that underZFC, the cardinality of the set of all free ultrafilters on an infinite set${\displaystyle X}$ is equal to the cardinality of${\displaystyle \mathcal{P}(\mathcal{P}(X)),}$ where${\displaystyle \mathcal{P}(X)}$ denotes the power set of${\displaystyle X.}$^[16]Other authors attribute this discovery to Bedřich Pospíšil (following a combinatorial argument fromFichtenholz, andKantorovitch, improved byHausdorff).^[17][18]

UnderZF, theaxiom of choice can be used to prove both the ultrafilter lemma and theKrein–Milman theorem; conversely, underZF, the ultrafilter lemma together with the Krein–Milman theorem can prove the axiom of choice.^[19]

The ultrafilter lemma is a relatively weak axiom. For example, each of the statements in the following list cannot be deduced fromZF together withonly the ultrafilter lemma:

1. A countable union ofcountable sets is a countable set.
2. Theaxiom of countable choice (ACC).
3. Theaxiom of dependent choice (ADC).

UnderZF, the ultrafilter lemma is equivalent to each of the following statements:^[20]

1. TheBoolean prime ideal theorem (BPIT).
2. Stone's representation theorem for Boolean algebras.
3. Any product ofBoolean spaces is a Boolean space.^[21]
4. Boolean Prime Ideal Existence Theorem: Every nondegenerateBoolean algebra has a prime ideal.^[22]
5. Tychonoff's theorem forHausdorff spaces: Anyproduct ofcompactHausdorff spaces is compact.^[21]
6. If${\displaystyle \{0,1\}}$ is endowed with thediscrete topology then for any set${\displaystyle I,}$ theproduct space${\displaystyle \{0,1{\}}^I}$ iscompact.^[21]
7. Each of the following versions of theBanach-Alaoglu theorem is equivalent to the ultrafilter lemma:
   1. Anyequicontinuous set of scalar-valued maps on atopological vector space (TVS) is relatively compact in theweak-* topology (that is, it is contained in some weak-* compact set).^[23]
   2. Thepolar of any neighborhood of the origin in a TVS${\displaystyle X}$ is a weak-* compact subset of itscontinuous dual space.^[23]
   3. The closed unit ball in thecontinuous dual space of anynormed space is weak-* compact.^[23]
      • If the normed space is separable then the ultrafilter lemma is sufficient but not necessary to prove this statement.
8. A topological space${\displaystyle X}$ is compact if every ultrafilter on${\displaystyle X}$ converges to some limit.^[24]
9. A topological space${\displaystyle X}$ is compact ifand only if every ultrafilter on${\displaystyle X}$ converges to some limit.^[24]
   • The addition of the words "and only if" is the only difference between this statement and the one immediately above it.
10. TheAlexander subbase theorem.^[25][26]
11. The Ultranet lemma: Everynet has a universal subnet.^[26]
    • By definition, anet in${\displaystyle X}$ is called anultranet or anuniversal net if for every subset${\displaystyle S\subseteq X,}$ the net is eventually in${\displaystyle S}$ or in${\displaystyle X\setminus S.}$
12. A topological space${\displaystyle X}$ is compact if and only if every ultranet on${\displaystyle X}$ converges to some limit.^[24]
    • If the words "and only if" are removed then the resulting statement remains equivalent to the ultrafilter lemma.^[24]
13. Aconvergence space${\displaystyle X}$ is compact if every ultrafilter on${\displaystyle X}$ converges.^[24]
14. Auniform space is compact if it iscomplete andtotally bounded.^[24]
15. TheStone–Čech compactification Theorem.^[21]
16. Each of the following versions of thecompactness theorem is equivalent to the ultrafilter lemma:
    1. If${\displaystyle \mathrm{\Sigma }}$ is a set offirst-ordersentences such that every finite subset of${\displaystyle \mathrm{\Sigma }}$ has amodel, then${\displaystyle \mathrm{\Sigma }}$ has a model.^[27]
    2. If${\displaystyle \mathrm{\Sigma }}$ is a set ofzero-order sentences such that every finite subset of${\displaystyle \mathrm{\Sigma }}$ has a model, then${\displaystyle \mathrm{\Sigma }}$ has a model.^[27]
17. Thecompleteness theorem: If${\displaystyle \mathrm{\Sigma }}$ is a set ofzero-order sentences that is syntactically consistent, then it has a model (that is, it is semantically consistent).

Any statement that can be deduced from the ultrafilter lemma (together withZF) is said to beweaker than the ultrafilter lemma. A weaker statement is said to bestrictly weaker if underZF, it is not equivalent to the ultrafilter lemma. UnderZF, the ultrafilter lemma implies each of the following statements:

1. The Axiom of Choice for Finite sets (ACF): Given${\displaystyle I\ne \varnothing }$ and a family${\displaystyle {\left(X_i\right)}_{i\in I}}$ of non-emptyfinite sets, their product${\displaystyle \prod _{i\in I}{X}_i}$ is not empty.^[26]
2. Acountable union of finite sets is a countable set.
   • However,ZF with the ultrafilter lemma is too weak to prove that a countable union ofcountable sets is a countable set.
3. TheHahn–Banach theorem.^[26]
   • InZF, the Hahn–Banach theorem is strictly weaker than the ultrafilter lemma.
4. TheBanach–Tarski paradox.
   • In fact, underZF, the Banach–Tarski paradoxcan be deduced from theHahn–Banach theorem,^[28][29] which is strictly weaker than the Ultrafilter Lemma.
5. Every set can belinearly ordered.
6. Everyfield has a uniquealgebraic closure.
7. Non-trivialultraproducts exist.
8. The weak ultrafilter theorem: A free ultrafilter exists on${\displaystyle \mathbb{N}.}$
   • UnderZF, the weak ultrafilter theorem does not imply the ultrafilter lemma; that is, it is strictly weaker than the ultrafilter lemma.
9. There exists a free ultrafilter on every infinite set;
   • This statement is actually strictly weaker than the ultrafilter lemma.
   • ZF alone does not even imply that there exists a non-principal ultrafilter onsome set.

Thecompleteness of an ultrafilter${\displaystyle U}$ on a powerset is the smallestcardinal κ such that there are κ elements of${\displaystyle U}$ whose intersection is not in${\displaystyle U.}$ The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least${\displaystyle {\mathrm{\aleph }}_0}$. An ultrafilter whose completeness isgreater than${\displaystyle {\mathrm{\aleph }}_0}$—that is, the intersection of any countable collection of elements of${\displaystyle U}$ is still in${\displaystyle U}$—is calledcountably complete orσ-complete.

The completeness of a countably completenonprincipal ultrafilter on a powerset is always ameasurable cardinal.^{[citation needed]}

TheRudin–Keisler ordering (named afterMary Ellen Rudin andHoward Jerome Keisler) is apreorder on the class of powerset ultrafilters defined as follows: if${\displaystyle U}$ is an ultrafilter on${\displaystyle \mathcal{P}(X),}$ and${\displaystyle V}$ an ultrafilter on${\displaystyle \mathcal{P}(Y),}$ then${\displaystyle V\le {}_{RK}U}$ if there exists a function${\displaystyle f:X\to Y}$ such that

${\displaystyle C\in V}$ if and only if${\displaystyle f^{-1}[C]\in U}$

for every subset${\displaystyle C\subseteq Y.}$

Ultrafilters${\displaystyle U}$ and${\displaystyle V}$ are calledRudin–Keisler equivalent, denotedU ≡_RKV, if there exist sets${\displaystyle A\in U}$ and${\displaystyle B\in V}$ and abijection${\displaystyle f:A\to B}$ that satisfies the condition above. (If${\displaystyle X}$ and${\displaystyle Y}$ have the same cardinality, the definition can be simplified by fixing${\displaystyle A=X,}$${\displaystyle B=Y.}$)

It is known that ≡_RK is thekernel of ≤_RK, i.e., thatU ≡_RKV if and only if${\displaystyle U\le {}_{RK}V}$ and${\displaystyle V\le {}_{RK}U.}$^[30]

There are several special properties that an ultrafilter on${\displaystyle \mathcal{P}(\omega ),}$ where${\displaystyle \omega }$extends the natural numbers, may possess, which prove useful in various areas of set theory and topology.

• A non-principal ultrafilter${\displaystyle U}$ is called aP-point (orweakly selective) if for everypartition of${\displaystyle \omega }$ such that for all${\displaystyle C_n\notin U,}$ there exists some${\displaystyle A\in U}$ such that${\displaystyle A\cap C_n}$ is a finite set for each${\displaystyle n.}$
• A non-principal ultrafilter${\displaystyle U}$ is calledRamsey (orselective) if for every partition of${\displaystyle \omega }$ such that for all${\displaystyle C_n\notin U,}$ there exists some${\displaystyle A\in U}$ such that${\displaystyle A\cap C_n}$ is asingleton set for each${\displaystyle n.}$

It is a trivial observation that all Ramsey ultrafilters are P-points.Walter Rudin proved that thecontinuum hypothesis implies the existence of Ramsey ultrafilters.^[31]In fact, many hypotheses imply the existence of Ramsey ultrafilters, includingMartin's axiom.Saharon Shelah later showed that it is consistent that there are no P-point ultrafilters.^[32] Therefore, the existence of these types of ultrafilters isindependent ofZFC.

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

An ultrafilter on${\displaystyle \mathcal{P}(\omega )}$ is Ramsey if and only if it isminimal in the Rudin–Keisler ordering of non-principal powerset ultrafilters.^[33]

• Extender (set theory)
• Filter (mathematics) – Special subset of a partially ordered set
• Filter on a set – Family of subsets representing "large" sets
• Filters in topology – Use of filters to describe and characterize all basic topological notions and results
• Łoś's theorem – Mathematical constructionPages displaying short descriptions of redirect targets
• Ultrafilter – Maximal proper filter
• Universal net – Generalization of a sequence of pointsPages displaying short descriptions of redirect targets

Proofs

• Arkhangel'skii, Alexander Vladimirovich;Ponomarev, V.I. (1984).Fundamentals of General Topology: Problems and Exercises. Mathematics and Its Applications. Vol. 13. Dordrecht Boston:D. Reidel.ISBN 978-90-277-1355-1.OCLC 9944489.
• Bourbaki, Nicolas (1989) [1966].General Topology: Chapters 1–4 [Topologie Générale].Éléments de mathématique. Berlin New York: Springer Science & Business Media.ISBN 978-3-540-64241-1.OCLC 18588129.
• Dixmier, Jacques (1984).General Topology. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York:Springer-Verlag.ISBN 978-0-387-90972-1.OCLC 10277303.
• Dolecki, Szymon; Mynard, Frédéric (2016).Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company.ISBN 978-981-4571-52-4.OCLC 945169917.
• Dugundji, James (1966).Topology. Boston: Allyn and Bacon.ISBN 978-0-697-06889-7.OCLC 395340485.
• Császár, Ákos (1978).General topology. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd.ISBN 0-85274-275-4.OCLC 4146011.
• Jech, Thomas (2006).Set Theory: The Third Millennium Edition, Revised and Expanded. Berlin New York: Springer Science & Business Media.ISBN 978-3-540-44085-7.OCLC 50422939.
• Joshi, K. D. (1983).Introduction to General Topology. New York: John Wiley and Sons Ltd.ISBN 978-0-85226-444-7.OCLC 9218750.
• Narici, Lawrence; Beckenstein, Edward (2011).Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press.ISBN 978-1584888666.OCLC 144216834.
• Schechter, Eric (1996).Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press.ISBN 978-0-12-622760-4.OCLC 175294365.
• Schubert, Horst (1968).Topology. London: Macdonald & Co.ISBN 978-0-356-02077-8.OCLC 463753.

• Comfort, W. W. (1977)."Ultrafilters: some old and some new results"(PDF).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 at thenLab

• Families of sets
• Nonstandard analysis
• Order theory

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from July 2016
• Pages displaying short descriptions of redirect targets via Module:Annotated link