Ultrafilter

A family U ≠ ∅ of subsets of X is called ultra if ∅ ∉ U and any of the following equivalent conditions are satisfied:[7][8]

1. For every set S ⊆ X there exists some set B ∈ U such that B ⊆ S or B ⊆ X ∖ S (or equivalently, such that B ∩ S equals B or ∅).
2. For every set S ⊆ ∪B ∈ U B there exists some set B ∈ U such that B ∩ S equals B or ∅.
   • Here, ∪B ∈ U B is defined to be the union of all sets in U.
   • This characterization of "U is ultra" does not depend on the set X, so mentioning the set X is optional when using the term "ultra."
3. For every set S (not necessarily even a subset of X ) there exists some set B ∈ U such that B ∩ S equals B or ∅.
   • If U satisfies this condition then so does every superset V ⊇ U. In particular, a set V is ultra if and only if ∅ ∉ V and V contains as a subset some ultra family of sets.

A filter subbase that is ultra is necessarily a prefilter.

An ultra prefilter[7][8] is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra.

An ultrafilter[7][8] on X is a proper filter on X that is ultra. Equivalently, it is any proper filter on X that is generated by an ultra prefilter.

Interpretation as large sets

The elements of a proper filter F on X may be thought of as being "large sets (relative to F)" and the complements in X of a large sets can be thought of as being "small" sets[9] (the "small sets" are exactly the elements in the ideal X ∖ F). In general, there may be subsets of X that are neither large nor small, or possibly simultaneously large and small. A dual ideal is a filter (i.e. proper) if there is no set that is both large and small, or equivalently, if the ∅ is not large.[9] A filter is ultra if and only if every subset of X is either large or else small. With this terminology, the defining properties of a filter can be restarted as: (1) any superset of a large set is large set, (2) the intersection of any two (or finitely many) large sets is large, (3) X is a large set (i.e. F ≠ ∅), (4) the empty set is not large. Different dual ideals give different notions of "large" sets.

Ultra prefilters as maximal prefilters

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

Given two families of sets M and N, the family M is said to be coarser[10][11] than N, and N is finer than and subordinate to M, written M ≤ N or N ⊢ M, if for every C ∈ M, there is some F ∈ N such that F ⊆ C. The families M and N are called equivalent if M ≤ N and N ≤ M. The families M and N are comparable if one of these sets is finer than the other.[10]

The subordination relationship, i.e.   ≤ , is a preorder so the above definition of "equivalent" does form an equivalence relation. If M ⊆ N then M ≤ N but the converse does not hold in general. However, if N is upward closed, such as a filter, then M ≤ N if and only if M ⊆ 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 M and N are equivalent then either both M and 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 is not equivalent to the filter or prefilter that it generates. If M and N are both filters on X then M and N are equivalent if and only if M = N. If a proper filter (resp. ultrafilter) is equivalent to a family of sets M then 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:

A family of sets is a prefilter (resp. an ultra prefilter) if and only it is equivalent to a proper filter (resp. an ultrafilter).

A maximal prefilter on X[7][8] is a prefilter U ⊆ ℘(X) that satisfies any of the following equivalent conditions:

1. U is ultra.
2. U is maximal on Prefilters(X) (with respect to ≤ ), meaning that if P ∈ Prefilters(X) satisfies U ≤ P then P ≤ U.[8]
3. There is no prefilter properly subordinate to U.[8]
4. If a proper filter F on X satisfies U ≤ F then F ≤ U.
5. The filter on X generated by U is ultra.

There are no ultrafilters on ℘(∅) so it is henceforth assumed that X ≠ ∅.

A filter subbase U on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:[7][8]

1. for any S ⊆ X, either S ∈ U or X ∖ S ∈ U.
2. U is a maximal filter subbase on X, meaning that if F is any filter subbase on X then U ⊆ F implies U = F.[9]

A proper filter U on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:

1. U is ultra;
2. U is generated an ultra prefilter;
3. For any subset S ⊆ X, S ∈ U or X ∖ S ∈ U.[9]
   • So an ultrafilter U decides for every S ⊆ X whether S is "large" (i.e. S ∈ U) or "small" (i.e. X ∖ S ∈ U).[12]
4. For each subset A of X, either[note 2] A is in U or (X \ A) is.
5. U ∪ (X ∖ U) = ℘(X). This condition can be restated as: ℘(X) is partitioned by U and its dual X ∖ U.
   • The sets P and X ∖ P are disjoint for all prefilters P on X.
6. ℘(X) ∖ U = { S ∈ ℘(X) : S ∉ U } is an ideal on X.[9]
7. For any finite family S₁, ..., S_n of subsets of X (where n ≥ 1), if S₁ ∪ ⋅⋅⋅ ∪ S_n ∈ U then S_i ∈ U for some index i.
   • In words, a "large" set cannot be a finite union of sets that aren't large.[13]
8. For any R, S ⊆ X, if R ∪ S = X then R ∈ U or S ∈ U.
9. For any R, S ⊆ X, if R ∪ S ∈ U then R ∈ U or S ∈ U (a filter with this property is called a prime filter).
10. For any R, S ⊆ X, if R ∪ S ∈ U and R ∩ S = ∅ then either R ∈ U or S ∈ U.
11. U is a maximal filter; that is, if F is a filter on X such that U ⊆ F then U = F. Equivalently, U is a maximal filter if there is no filter F on X that contains U as a proper subset (i.e. that is strictly finer than U).[9]

If ${\displaystyle {\mathcal {B}}\subseteq \wp (X)}$ then its grill on ${\displaystyle X}$ is the family ${\displaystyle {\mathcal {B}}^{\#X}:={\mathcal {B}}^{\#}:=\{S\subseteq X~:~S\cap B\neq \varnothing {\text{ for all }}B\in {\mathcal {B}}\},}$ which is upward closed in ${\displaystyle X}$ and moreover, ${\displaystyle {\mathcal {B}}^{\#\#}={\mathcal {B}}^{\uparrow X}}$ so that ${\displaystyle {\mathcal {B}}}$ is upward closed in ${\displaystyle X}$ if and only if ${\displaystyle {\mathcal {B}}^{\#\#}={\mathcal {B}}.}$ If ${\displaystyle {\mathcal {B}}}$ is a filter subbase then ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {B}}^{\#}.}$[14] Moreover, ${\displaystyle (\wp (X))^{\#}=\varnothing }$ and ${\displaystyle \varnothing ^{\#}=\wp (X).}$ The grill of a filter on ${\displaystyle X}$ is called a filter-grill on ${\displaystyle X.}$[14] For any ${\displaystyle \varnothing \neq {\mathcal {B}}\subseteq \wp (X),}$ ${\displaystyle {\mathcal {B}}}$ is the grill of a filter 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 {\bullet }^{\#X}~:~\operatorname {Filters} (X)\to \operatorname {FilterGrills} (X),}$ defined by ${\displaystyle {\mathcal {F}}\mapsto {\mathcal {F}}^{\#X},}$ is a bijection whose inverse is also given by ${\displaystyle {\mathcal {F}}\mapsto {\mathcal {F}}^{\#X}.}$[14] If ${\displaystyle {\mathcal {F}}\in \operatorname {Filters} (X)}$ then ${\displaystyle {\mathcal {F}}}$ is a filter-grill on ${\displaystyle X}$ if and only if ${\displaystyle {\mathcal {F}}={\mathcal {F}}^{\#X},}$[14] or equivalently, if and only if ${\displaystyle {\mathcal {F}}}$ is an ultrafilter on ${\displaystyle X.}$[14] Filter-grills on ${\displaystyle X}$ are thus the same as ultrafilters on ${\displaystyle X.}$ For any non-empty ${\displaystyle {\mathcal {F}}\subseteq \wp (X),}$ ${\displaystyle {\mathcal {F}}}$ is a filter-grill on ${\displaystyle X}$ if and only if ${\displaystyle \varnothing \not \in {\mathcal {F}}}$ and for all subsets ${\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}}.}$[14]

If P is any non-empty family of sets then the Kernel of P is the intersection of all set in P:

ker P  :=  ∩B ∈ P B[15]

A non-empty family of sets P is called:

• free if ker P = ∅ and fixed otherwise (i.e. if ker P ≠ ∅),
• principal if ker P ∈ P,
• principal at a point if ker P ∈ P and ker P is a singleton set; in this case, if ker P = { x } then P is said to be principal at x.

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

Every filter on X that is principal at a single point is an ultrafilter, and if in addition X is finite, then there are no ultrafilters on X other than these.[15] If there exists a free ultrafilter (or even filter subbase) on a set X then X must be infinite.

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.

If U and S are families of sets such that U is ultra, ∅ ∉ S, and U ≤ S, then S is necessarily ultra. A filter subbase U that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by U to be ultra.

Suppose U ⊆ ℘(X) is ultra and Y is a set. The trace U ∩ Y := { B ∩ Y  :  B ∈ U } is ultra if and only if it does not contain the empty set. Furthermore, at least one of the sets [U ∩ Y] ∖ { ∅ } and [U ∩ (X ∖ Y)] ∖ { ∅ } will be ultra (this result extends to any finite partition of X). If F₁, ..., F_n are filters on X, U is an ultrafilter on X, and F₁ ∩ ⋅⋅⋅ ∩ F_n ≤ U, then there is some F_i that satisfies F_i ≤ U.[16] This result is not necessarily true for an infinite family of filters.[16]

The image under a map f : X → Y of an ultra set U ⊆ ℘(X) is again ultra and if U is an ultra prefilter then so is 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 X has more than one point and if the range of f : X → Y consists of a single point { y } then { { y } } is an ultra prefilter on Y but its preimage is not ultra. Alternatively, if U is a principal filter generated by a point in Y ∖ f (X) then the preimage of U contains the empty set and so is not ultra.

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

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

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

${\displaystyle X\to U(X)}$

sends any element x ∈ 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.[18]

The ultrafilter lemma was first proved by Alfred Tarski in 1930.[17]

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.[7]
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.[19][note 5]

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.[10] 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} \neq \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, Zermelo–Fraenkel set theory (ZF) is assumed. The ultrafilter lemma is equivalent to the Boolean prime ideal theorem, with the equivalence provable in ZF set theory without the axiom of choice. Assuming ZF, the ultrafilter lemma is equivalent to the ultranet lemma: every net has a universal subnet.[20] By definition, a net in ${\displaystyle X}$ is an ultranet or an universal net if for every subset ${\displaystyle S\subseteq X,}$ the net is eventually in ${\displaystyle S}$ or ${\displaystyle X\setminus S.}$

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 than ZF. If ${\displaystyle X}$ is finite, then every ultrafilter is discrete at a point so free ultrafilters can only exist on infinite sets. In particular, if ${\displaystyle X}$ is finite then the ultrafilter lemma can be proven from the axioms ZF.

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 the axiom of choice, which in brief states that any Cartesian product of non-empty sets is non-empty. Under ZF, the axiom of choice is, in particular, equivalent to (a) Zorn's lemma, (b) Tychonoff's theorem, (c) every vector space has a basis, and other statements. However, the ultrafilter lemma is strictly weaker than the axiom of choice.

The ultrafilter lemma has many applications in topology. The ultrafilter lemma can be used to prove the Hahn-Banach theorem, the Alexander subbase theorem, and that any product of compact Hausdorff spaces is compact (which is a special case of Tychonoff's theorem).[20] The ultrafilter lemma can be used to prove the Axiom of choice for finite sets; explicitly, this is the statement: Given ${\displaystyle I\neq \varnothing }$ and a family ${\displaystyle \left(X_{i}\right)_{i\in I}}$ of non-empty finite sets, their product ${\displaystyle \prod _{i\in I}X_{i}}$ is not empty.[20]

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 ${\displaystyle \aleph _{0}}$. An ultrafilter whose completeness is greater than ${\displaystyle \aleph _{0}}$—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.

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.[21]

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.[22] 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.[23] 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 [ω]² 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.