View source for Ultrafilter (set theory)

{{short description|Maximal proper filter}}
[[File:Filter vs ultrafilter.svg|thumb|The powerset lattice of the set {1,2,3,4}, with the [[Upper set|upper set]] ↑{1,4} colored dark green. It is a {{em|principal filter}}, but not an {{em|ultrafilter}}, as it can be extended to the larger nontrivial filter ↑{1}, by including also the light green elements. Since ↑{1} cannot be extended any further, it is an ultrafilter.]]
In the [[Mathematics|mathematical]] field of [[Set theory|set theory]], an '''ultrafilter''' is a ''maximal proper filter'': it is a [[Filter (mathematics)|filter]] <math>U</math> on a given non-empty [[Set (mathematics)|set]] <math>X</math> which is a certain type of non-empty [[Family of sets|family of subsets]] of <math>X,</math> that is not equal to the [[Power set|power set]] <math>\wp(X)</math> of <math>X</math> (such filters are called {{em|proper}}) and that is also "maximal" in that there does not exist any other proper filter on <math>X</math> that contains it as a proper subset. 
Said differently, a proper filter <math>U</math> is called an ultrafilter if there exists {{em|exactly one}} proper filter that contains it as a subset, that proper filter (necessarily) being <math>U</math> itself.

More formally, an ultrafilter <math>U</math> on <math>X</math> is a proper filter that is also a maximal [[Filter (mathematics)|filter]] on <math>X</math> with respect to set inclusion, meaning that there does not exist any proper filter on <math>X</math> that contains <math>U</math> as a proper subset. 
Ultrafilters on sets are an important special instance of [[Ultrafilter|ultrafilters on partially ordered sets]], where the [[Partially ordered set|partially ordered set]] consists of the [[Power set|power set]] <math>\wp(X)</math> and the partial order is subset inclusion <math>\,\subseteq.</math>

Ultrafilters have many applications in set theory, [[Model theory|model theory]], and [[Topology|topology]].<ref name="Davey.Priestley.1990">{{cite book|first1=B. A.|last1=Davey|first2=H. A.|last2=Priestley|title=Introduction to Lattices and Order|title-link=Introduction to Lattices and Order|publisher=Cambridge University Press|year=1990|series=Cambridge Mathematical Textbooks}}</ref>{{rp|186}}

==Definitions==


Given an arbitrary set <math>X,</math> an ultrafilter on <math>X</math> is a non-empty [[Family of sets|family]] <math>U</math> of subsets of <math>X</math> such that:
#{{em|{{visible anchor|Proper}}}} or {{em|{{visible anchor|non-degenerate}}}}: The empty set is not an element of <math>U.</math>
#{{em|{{visible anchor|Upward closed}} in <math>X</math>}}: If <math>A \in U</math> and if <math>B \subseteq X</math> is any superset of <math>A</math> (that is, if <math>A \subseteq B \subseteq X</math>) then <math>B \in U.</math>
#{{em|[[Pi-system|{{pi}}−system]]}}: If <math>A</math> and <math>B</math> are elements of <math>U</math> then so is their [[Intersection (set theory)|intersection]] <math>A \cap B.</math>
#If <math>A \subseteq X</math> then either<ref name="exclusive or" group=note>Properties 1 and 3 imply that <math>A</math> and <math>X \setminus A</math> cannot {{em|both}} be elements of <math>U.</math></ref> <math>A</math> or its relative complement <math>X \setminus A</math> is an element of <math>U.</math> 

Properties (1), (2), and (3) are the defining properties of a {{em|filter on <math>X.</math>}} 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. 

For a filter <math>F</math> that is not an ultrafilter, one would say <math>m(A) = 1</math> if <math>A \in F</math> and <math>m(A) = 0</math> if <math>X \setminus A \in F,</math> leaving <math>m</math> undefined elsewhere.{{citation needed|date=July 2016}}{{clarify|reason=A function m can certainly be defined in that way. However, this is pointless unless such an m can be shown to have some useful properties (e.g. being a 'content'). They should be stated here.|date=July 2016}}

A '''filter {{em|sub}}base''' is a non-empty family of sets that has the [[Finite intersection property|finite intersection property]] (i.e. all finite intersections are non-empty). Equivalently, a filter subbase is a non-empty family of sets that is contained in {{em|some}} (proper) filter. The smallest (relative to <math>\subseteq</math>) filter containing a given filter subbase is said to be '''generated''' by the filter subbase.

The '''upward closure''' in <math>X</math> of a family of sets <math>P</math> is the set 
:<math>P^{\uparrow X} := \{S : A \subseteq S \subseteq X \text{ for some } A \in P\}.</math>

A '''{{visible anchor|prefilter}}''' or '''{{visible anchor|filter base}}''' is a non-empty and proper (i.e. <math>\varnothing \not\in P</math>) family of sets <math>P</math> that is '''downward directed''', which means that if <math>B, C \in P</math> then there exists some <math>A \in P</math> such that <math>A \subseteq B \cap C.</math> Equivalently, a prefilter is any family of sets <math>P</math> whose upward closure <math>P^{\uparrow X}</math> is a filter, in which case this filter is called the '''filter generated by <math>P</math>''' and <math>P</math> is said to be '''a filter base {{em|for}} <math>P^{\uparrow X}.</math>''' 

The '''dual in <math>X</math>'''{{sfn|Narici|Beckenstein|2011|pp=2-7}} of a family of sets <math>P</math> is the set <math>X \setminus P := \{X \setminus B : B \in P\}.</math> For example, the dual of the [[Power set|power set]] <math>\wp(X)</math> is itself: <math>X \setminus \wp(X) = \wp(X).</math> 
A family of sets is a proper filter on <math>X</math> if and only if its dual is a proper [[Ideal (set theory)|ideal]] on <math>X</math> ("{{em|proper}}" means not equal to the power set). 

'''Interpretation as {{em|large}} sets'''

The elements of a proper filter <math>F</math> on <math>X</math> may be thought of as being "large sets (relative to <math>F</math>)" and the complements in <math>X</math> of a large sets can be thought of as being "small" sets{{sfn|Schechter|1996|pp=100-130}} (the "small sets" are exactly the elements in the [[Ideal (set theory)|ideal]] <math>X \setminus F</math>). 

To see why filters and ideals should respectively be associated with "large" and "small" sets (rather than vice versa), we begin by explaining why sets in an ideal should be interpreted as "small" by considering the notion of "bounded subsets" (such as in a [[Metric space|metric space]] or a normed space like <math>\R^3</math>). 
The following properties should be expected of any reasonable generalization of "bounded subsets": subsets of bounded sets should be bounded, the empty set should be bounded, the union of two bounded sets should be bounded, and every point (singleton subset) should be bounded. These are the defining properties of a {{em|[[Bornology|boundedness]]}} on <math>X,</math> although the term {{em|[[Bornology|bornology]]}} is more common, and elements of a given bornology are called {{em|bounded sets}}. Explicitly (and equivalently), a {{em|[[Bornology|bornology]]}} on <math>X</math> is an [[Ideal (set theory)|ideal]] <math>\mathcal{I}</math> that [[Cover (topology)|cover]]s <math>X.</math> Bounded sets, especially singleton and finite sets, are naturally interpreted as "small sets". Thus we are led to associate ideals with "small sets". Assuming that <math>X</math> is not a bounded/"small set" (that is, if <math>X \not\in \mathcal{I}</math> or said differently, if <math>\mathcal{I}</math> is a proper ideal) then it is reasonable to interpret complements of "small sets" as being "large sets". In other words, "large sets" are those belonging to the dual <math>X \setminus \mathcal{I} := \{X \setminus S : S \in \mathcal{I}\}</math> of the ideal <math>\mathcal{I}.</math> Recalling that a family of subsets of <math>X</math> is a proper ideal if and only if its dual is a filter on <math>X,</math>{{sfn|Narici|Beckenstein|2011|pp=2-7}} we are thus led to associate filters with "large sets".

In general, there may be subsets of <math>X</math> that are {{em|neither}} large nor small (e.g. a set not in <math>\mathcal{I}</math> nor its dual <math>X \setminus \mathcal{I}</math>), or possibly {{em|simultaneously}} large and small (e.g. <math>X</math> if <math>\mathcal{I}</math> is not a proper ideal). A dual ideal is a filter (i.e. proper) if there is no set that is both large and small, or equivalently, if the <math>\varnothing</math> is not large.{{sfn|Schechter|1996|pp=100-130}} A filter is ultra if and only if {{em|every}} subset of <math>X</math> 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) <math>X</math> is a large set (i.e. <math>F \neq \varnothing</math>), (4) the empty set is not large. Different dual ideals give different notions of "large" sets.

Another way of looking at ultrafilters on a power set <math>\wp(X)</math> is as follows: for a given ultrafilter <math>U</math> define a function <math>m</math> on <math>\wp(X)</math> by setting <math>m(A) = 1</math> if <math>A</math> is an element of <math>U</math> and <math>m(A) = 0</math> otherwise. Such a function is called a [[2-valued morphism|2-valued morphism]]. Then <math>m</math> is finitely additive, and hence a {{em|[[Content (measure theory)|content]]}} on <math>\wp(X),</math> and every property of elements of <math>X</math> is either true [[Almost everywhere|almost everywhere]] or false almost everywhere. However, <math>m</math> is usually not {{em|countably additive}}, and hence does not define a [[Measure (mathematics)|measure]] in the usual sense.

==Generalization to ultra prefilters==

A family <math>U \neq \varnothing</math> of subsets of <math>X</math> is called '''{{visible anchor|ultra}}''' if <math>\varnothing \not\in U</math> and any of the following equivalent conditions are satisfied:{{sfn|Narici|Beckenstein|2011|pp=2-7}}{{sfn|Dugundji|1966|pp=219-221}} 

<ol>
<li>For every set <math>S \subseteq X</math> there exists some set <math>B \in U</math> such that <math>B \subseteq S</math> or <math>B \subseteq X \setminus S</math> (or equivalently, such that <math>B \cap S</math> equals <math>B</math> or <math>\varnothing</math>).</li>
<li>For every set <math>S \subseteq {\textstyle\bigcup\limits_{B \in U}} B</math> there exists some set <math>B \in U</math> such that <math>B \cap S</math> equals <math>B</math> or <math>\varnothing.</math> 
* Here, <math> {\textstyle\bigcup\limits_{B \in U}} B</math> is defined to be the union of all sets in <math>U.</math>
* This characterization of "<math>U</math> is ultra" does not depend on the set <math>X,</math> so mentioning the set <math>X</math> is optional when using the term "ultra."</li>
<li>For {{em|every}} set <math>S</math> (not necessarily even a subset of <math>X</math>) there exists some set <math>B \in U</math> such that <math>B \cap S</math> equals <math>B</math> or <math>\varnothing.</math> 
* If <math>U</math> satisfies this condition then so does {{em|every}} superset <math>V \supseteq U.</math> In particular, a set <math>V</math> is ultra if and only if <math>\varnothing \not\in V</math> and <math>V</math> contains as a subset some ultra family of sets.</li>
</ol>

A filter subbase that is ultra is necessarily a prefilter.<ref group=proof>Suppose <math>\mathcal{B}</math> is filter subbase that is ultra. Let <math>C, D \in \mathcal{B}</math> and define <math>S = C \cap D.</math> Because <math>\mathcal{B}</math> is ultra, there exists some <math>B \in \mathcal{B}</math>  such that <math>B \cap S</math> equals <math>B</math> or <math>\varnothing.</math>  The finite intersection property implies that <math>B \cap S \neq \varnothing</math> so necessarily <math>B \cap S = B,</math> which is equivalent to <math>B \subseteq C \cap D.</math> <math>\blacksquare</math></ref> 

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

:An '''{{visible anchor|ultra prefilter}}'''{{sfn|Narici|Beckenstein|2011|pp=2-7}}{{sfn|Dugundji|1966|pp=219-221}} is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra.

:An '''{{visible anchor|ultrafilter}}'''{{sfn|Narici|Beckenstein|2011|pp=2-7}}{{sfn|Dugundji|1966|pp=219-221}} on <math>X</math> is a (proper) filter on <math>X</math> that is ultra. Equivalently, it is any filter on <math>X</math> 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 <math>M</math> and <math>N,</math> the family <math>M</math> is said to be '''coarser'''{{sfn|Bourbaki|1989|pp=57-68}}{{sfn|Schubert|1968|pp=48-71}} than <math>N,</math> and <math>N</math> is '''finer''' than and '''subordinate to''' <math>M,</math> written <math>M \leq N</math> or {{math|''N'' ⊢ ''M''}}, if for every <math>C \in M,</math> there is some <math>F \in N</math> such that <math>F \subseteq C.</math> The families <math>M</math> and <math>N</math> are called '''equivalent''' if <math>M \leq N</math> and <math>N \leq M.</math> The families <math>M</math> and <math>N</math> are '''comparable''' if one of these sets is finer than the other.{{sfn|Bourbaki|1989|pp=57-68}}

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

:A '''{{visible anchor|maximal prefilter}} on <math>X</math>'''{{sfn|Narici|Beckenstein|2011|pp=2-7}}{{sfn|Dugundji|1966|pp=219-221}} is a prefilter <math>U \subseteq \wp(X)</math> that satisfies any of the following equivalent conditions:
<ol>
<li><math>U</math> is ultra.</li>
<!----- the theorem states: A prefilter <math>U</math> on <math>X</math> is maximal if and only if for any <math>S \subseteq X</math> there exists some <math>B \in U</math> such that <math>B \subseteq S</math> or <math>B \subseteq X \setminus S.</math>{{sfn|Narici|Beckenstein|2011|pp=2-7}} ----->
<li><math>U</math> is '''maximal''' on <math>\operatorname{Prefilters}(X)</math> with respect to <math>\,\leq,</math> meaning that if <math>P \in \operatorname{Prefilters}(X)</math> satisfies <math>U \leq P</math> then <math>P \leq U.</math>{{sfn|Dugundji|1966|pp=219-221}}</li>
<li>There is no prefilter properly subordinate to <math>U.</math>{{sfn|Dugundji|1966|pp=219-221}}</li>
<li>If a (proper) filter <math>F</math> on <math>X</math> satisfies <math>U \leq F</math> then <math>F \leq U.</math></li>
<li>The filter on <math>X</math> generated by <math>U</math> is ultra.</li>
</ol>

==Characterizations==

There are no ultrafilters on the [[Empty set|empty set]], so it is henceforth assumed that <math>X</math> is nonempty.

A filter {{em|sub}}base <math>U</math> on <math>X</math> is an ultrafilter on <math>X</math> if and only if any of the following equivalent conditions hold:{{sfn|Narici|Beckenstein|2011|pp=2-7}}{{sfn|Dugundji|1966|pp=219-221}}
<ol>
<li>for any <math>S \subseteq X,</math> either <math>S \in U</math> or <math>X \setminus S \in U.</math></li>
<li><math>U</math> is a maximal filter subbase on <math>X,</math> meaning that if <math>F</math> is any filter subbase on <math>X</math> then <math>U \subseteq F</math> implies <math>U = F.</math>{{sfn|Schechter|1996|pp=100-130}}</li>
</ol>

A (proper) filter <math>U</math> on <math>X</math> is an ultrafilter on <math>X</math> if and only if any of the following equivalent conditions hold:
<ol>
<li><math>U</math> is ultra;</li>
<li><math>U</math> is generated by an ultra prefilter;</li>
<li>For any subset <math>S \subseteq X,</math> <math>S \in U</math> or <math>X \setminus S \in U.</math>{{sfn|Schechter|1996|pp=100-130}}
* So an ultrafilter <math>U</math> decides for every <math>S \subseteq X</math> whether <math>S</math> is "large" (i.e. <math>S \in U</math>) or "small" (i.e. <math>X \setminus S \in U</math>).<ref name="Higgins Ultrafilters in set theory">{{cite web|last=Higgins|first=Cecelia|title=Ultrafilters in set theory|website=math.uchicago.edu|url=https://math.uchicago.edu/~may/REU2018/REUPapers/Higgins.pdf|date=2018|access-date=August 16, 2020}}</ref></li>
<li>For each subset <math>A \subseteq X,</math> either<ref name="exclusive or" group=note/> <math>A</math> is in <math>U</math> or (<math>X \setminus A</math>) is.</li>
<li><math>U \cup (X \setminus U) = \wp(X).</math> This condition can be restated as: <math>\wp(X)</math> is partitioned by <math>U</math> and its dual <math>X \setminus U.</math>
* The sets <math>P</math> and <math>X \setminus P</math> are disjoint for all prefilters <math>P</math> on <math>X.</math></li>
<li><math>\wp(X) \setminus U = \left\{ S \in \wp(X) : S \not\in U \right\}</math> is an ideal on <math>X.</math>{{sfn|Schechter|1996|pp=100-130}}</li>
<li>For any finite family <math>S_1, \ldots, S_n</math> of subsets of <math>X</math> (where <math>n \geq 1</math>), if <math>S_1 \cup \cdots \cup S_n \in U</math> then <math>S_i \in U</math> for some index <math>i.</math>
* In words, a "large" set cannot be a finite union of sets that aren't large.<ref name="Kruckman Notes on Ultrafilters">{{cite web|last=Kruckman|first=Alex|title=Notes on Ultrafilters|website=math.berkeley.edu|url=https://math.berkeley.edu/~kruckman/ultrafilters.pdf|date=November 7, 2012|access-date=August 16, 2020}}</ref></li>
<li>For any <math>R, S \subseteq X,</math> if <math>R \cup S = X</math> then <math>R \in U</math> or <math>S \in U.</math></li>
<li>For any <math>R, S \subseteq X,</math> if <math>R \cup S \in U</math> then <math>R \in U</math> or <math>S \in U</math> (a filter with this property is called a '''{{em|{{visible anchor|prime filter}}}}''').</li>
<li>For any <math>R, S \subseteq X,</math> if <math>R \cup S \in U</math> and <math>R \cap S = \varnothing</math> then {{em|either}} <math>R \in U</math> or <math>S \in U.</math></li>
<li><math>U</math> is a maximal filter; that is, if <math>F</math> is a filter on <math>X</math> such that <math>U \subseteq F</math> then <math>U = F.</math> Equivalently, <math>U</math> is a maximal filter if there is no filter <math>F</math> on <math>X</math> that contains <math>U</math> as a proper subset (that is, no filter is strictly [[Filter (mathematics)#Filter on a set|finer]] than <math>U</math>).{{sfn|Schechter|1996|pp=100-130}}</li>
</ol>

===Grills and Filter-Grills===

If <math>\mathcal{B} \subseteq \wp(X)</math> then its {{em|grill on <math>X</math>}} is the family 
<math display=block>\mathcal{B}^{\# X} := \{S \subseteq X ~:~ S \cap B \neq \varnothing \text{ for all } B \in \mathcal{B}\}</math>
where <math>\mathcal{B}^{\#}</math> may be written if <math>X</math> is clear from context. 
For example, <math>\varnothing^{\#} = \wp(X)</math> and if <math>\varnothing \in \mathcal{B}</math> then <math>\mathcal{B}^{\#} = \varnothing.</math> 
If <math>\mathcal{A} \subseteq \mathcal{B}</math> then <math>\mathcal{B}^{\#} \subseteq \mathcal{A}^{\#}</math> and moreover, if <math>\mathcal{B}</math> is a filter subbase then <math>\mathcal{B} \subseteq \mathcal{B}^{\#}.</math>{{sfn|Dolecki|Mynard|2016|pp=27-54}} 
The grill <math>\mathcal{B}^{\# X}</math> is upward closed in <math>X</math> if and only if <math>\varnothing \not\in \mathcal{B},</math> which will henceforth be assumed.  Moreover, <math>\mathcal{B}^{\#\#} = \mathcal{B}^{\uparrow X}</math> so that <math>\mathcal{B}</math> is upward closed in <math>X</math> if and only if <math>\mathcal{B}^{\#\#} = \mathcal{B}.</math> 

The grill of a filter on <math>X</math> is called a {{em|filter-grill on <math>X.</math>}}{{sfn|Dolecki|Mynard|2016|pp=27-54}} For any <math>\varnothing \neq \mathcal{B} \subseteq \wp(X),</math> <math>\mathcal{B}</math> is a filter-grill on <math>X</math> if and only if (1) <math>\mathcal{B}</math> is upward closed in <math>X</math> and (2) for all sets <math>R</math> and <math>S,</math> if <math>R \cup S \in \mathcal{B}</math> then <math>R \in \mathcal{B}</math> or <math>S \in \mathcal{B}.</math> The grill operation <math>\mathcal{F} \mapsto \mathcal{F}^{\# X}</math> induces a bijection 
:<math>{\bull}^{\# X} ~:~ \operatorname{Filters}(X) \to \operatorname{FilterGrills}(X)</math>
whose inverse is also given by <math>\mathcal{F} \mapsto \mathcal{F}^{\# X}.</math>{{sfn|Dolecki|Mynard|2016|pp=27-54}} If <math>\mathcal{F} \in \operatorname{Filters}(X)</math> then <math>\mathcal{F}</math> is a filter-grill on <math>X</math> if and only if <math>\mathcal{F} = \mathcal{F}^{\# X},</math>{{sfn|Dolecki|Mynard|2016|pp=27-54}} or equivalently, if and only if <math>\mathcal{F}</math> is an ultrafilter on <math>X.</math>{{sfn|Dolecki|Mynard|2016|pp=27-54}} That is, a filter on <math>X</math> is a filter-grill if and only if it is ultra. For any non-empty <math>\mathcal{F} \subseteq \wp(X),</math> <math>\mathcal{F}</math> is both a filter on <math>X</math> and a filter-grill on <math>X</math> if and only if (1) <math>\varnothing \not\in \mathcal{F}</math> and (2) for all <math>R, S \subseteq X,</math> the following equivalences hold: 
:<math>R \cup S \in \mathcal{F}</math> if and only if <math>R, S \in \mathcal{F}</math> if and only if <math>R \cap S \in \mathcal{F}.</math>{{sfn|Dolecki|Mynard|2016|pp=27-54}}

===Free or principal{{anchor|free ultrafilter}}===

If <math>P</math> is any non-empty family of sets then the '''[[Kernel (set theory)|Kernel]] of <math>P</math>''' is the intersection of all sets in <math>P:</math>{{sfn|Dolecki|Mynard|2016|pp=33-35}}
<math display=block>\operatorname{ker} P := \bigcap_{B \in P} B.</math>

A non-empty family of sets <math>P</math> is called:

* '''{{visible anchor|free}}''' if <math>\operatorname{ker} P = \varnothing</math> and '''{{visible anchor|fixed}}''' otherwise (that is, if <math>\operatorname{ker} P \neq \varnothing</math>).
* '''{{visible anchor|principal}}''' if <math>\operatorname{ker} P \in P.</math>
* '''{{visible anchor|principal at a point}}''' if <math>\operatorname{ker} P \in P</math> and <math>\operatorname{ker} P</math> is a singleton set; in this case, if <math>\operatorname{ker} P = \{x\}</math> then <math>P</math> is said to be '''principal at <math>x.</math>''' 

If a family of sets <math>P</math> is fixed then <math>P</math> is ultra if and only if some element of <math>P</math> is a singleton set, in which case <math>P</math> will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter <math>P</math> is ultra if and only if <math>\operatorname{ker} P</math> 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. 

{{Math theorem|name=Proposition|math_statement=If <math>U</math> is an ultrafilter on <math>X</math> then the following are equivalent:
<ol>
<li><math>U</math> is fixed, or equivalently, not free.</li>
<li><math>U</math> is principal.</li>
<li>Some element of <math>U</math> is a finite set.</li>
<li>Some element of <math>U</math> is a singleton set.</li>
<li><math>U</math> is principal at some point of <math>X,</math> which means <math>\operatorname{ker} U = \{x\} \in U</math> for some <math>x \in X.</math></li>
<li><math>U</math> does {{em|not}} contain the Fréchet filter on <math>X</math> as a subset.</li>
<li><math>U</math> is sequential.{{sfn|Dolecki|Mynard|2016|pp=27-54}}</li>
</ol>
}}

Every filter on <math>X</math> that is principal at a single point is an ultrafilter, and if in addition <math>X</math> is finite, then there are no ultrafilters on <math>X</math> other than these.{{sfn|Dolecki|Mynard|2016|pp=33-35}} In particular, if a set <math>X</math> has finite cardinality <math>n < \infty,</math> then there are exactly <math>n</math> ultrafilters on <math>X</math> and those are the ultrafilters generated by each singleton subset of <math>X.</math> Consequently, free ultrafilters can only exist on an infinite set.

==Examples, properties, and sufficient conditions==

If <math>X</math> is an infinite set then there are as many ultrafilters over <math>X</math> as there are families of subsets of <math>X;</math> explicitly, if <math>X</math> has infinite cardinality <math>\kappa</math> then the set of ultrafilters over <math>X</math> has the same cardinality as <math>\wp(\wp(X));</math> that cardinality being <math>2^{2^{\kappa}}.</math><ref name="Pospisil 1937">{{cite journal|last=Pospíšil|first=Bedřich|title=Remark on Bicompact Spaces|journal=The Annals of Mathematics|volume=38|issue=4|year=1937|page=845-846}}</ref>

If <math>U</math> and <math>S</math> are families of sets such that <math>U</math> is ultra, <math>\varnothing \not\in S,</math> and <math>U \leq S,</math> then <math>S</math> is necessarily ultra. 
A filter subbase <math>U</math> that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by <math>U</math> to be ultra.

Suppose <math>U \subseteq \wp(X)</math> is ultra and <math>Y</math> is a set. 
The trace <math>U\vert_Y := \{B \cap Y : B \in U\}</math> is ultra if and only if it does not contain the empty set. 
Furthermore, at least one of the sets <math>U\vert_Y \setminus \{\varnothing\}</math> and <math>U\vert_{X \setminus Y} \setminus \{\varnothing\}</math> will be ultra (this result extends to any finite partition of <math>X</math>). 
If <math>F_1, \ldots, F_n</math> are filters on <math>X,</math> <math>U</math> is an ultrafilter on <math>X,</math> and <math>F_1 \cap \cdots \cap F_n \leq U,</math> then there is some <math>F_i</math> that satisfies <math>F_i \leq U.</math>{{sfn|Bourbaki|1989|pp=129-133}} 
This result is not necessarily true for an infinite family of filters.{{sfn|Bourbaki|1989|pp=129-133}}

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

The elementary filter induced by an infinite sequence, all of whose points are distinct, is {{em|not}} an ultrafilter.{{sfn|Bourbaki|1989|pp=129-133}} If <math>n = 2,</math> then <math>U_n</math> denotes the set consisting all subsets of <math>X</math> having cardinality <math>n,</math> and if <math>X</math>contains at least <math>2 n - 1</math> (<math>=3</math>) distinct points, then <math>U_n</math> is ultra but it is not contained in any prefilter. This example generalizes to any integer <math>n > 1</math> and also to <math>n = 1</math> if <math>X</math> contains more than one element. Ultra sets that are not also prefilters are rarely used.

For every <math>S \subseteq X \times X</math> and every <math>a \in X,</math> let <math>S\big\vert_{\{a\} \times X} := \{y \in X ~:~ (a, y) \in S\}.</math> If <math>\mathcal{U}</math> is an ultrafilter on <math>X</math> then the set of all <math>S \subseteq X \times X</math> such that <math>\left\{a \in X ~:~ S\big\vert_{\{a\} \times X} \in \mathcal{U}\right\} \in \mathcal{U}</math> is an ultrafilter on <math>X \times X.</math>{{sfn|Jech|2006|pp=73-89}}

===Monad structure===

The [[Functor|functor]] associating to any set <math>X</math> the set of <math>U(X)</math> of all ultrafilters on <math>X</math> forms a [[Monad (category theory)|monad]] called the {{visible anchor|Ultrafilter monad|text=ultrafilter monad}}. The unit map
<math display=block>X \to U(X)</math>
sends any element <math>x \in X</math> to the principal ultrafilter given by <math>x.</math>

This ultrafilter monad is the [[Codensity monad|codensity monad]] of the inclusion of the category of finite sets into the [[Category of sets|category of all sets]],<ref name="Leinster2013">{{cite journal|last=Leinster|first=Tom|year=2013|title=Codensity and the ultrafilter monad|journal=Theory and Applications of Categories|volume=28|pages=332–370|bibcode=2012arXiv1209.3606L|arxiv=1209.3606|url=http://www.tac.mta.ca/tac/volumes/28/13/28-13.pdf}}</ref> which gives a conceptual explanation of this monad.

Similarly, the ultraproduct monad is the codensity monad of the inclusion of the category of finite [[Family of sets|families of sets]] into the category of all families of set. So in this sense, [[Ultraproduct|ultraproduct]]s are categorically inevitable.<ref name="Leinster2013" />

==The ultrafilter lemma==

The ultrafilter lemma was first proved by [[Biography:Alfred Tarski|Alfred Tarski]] in 1930.{{sfn|Jech|2006|pp=73-89}}

{{Math theorem|name=The {{visible anchor|ultrafilter lemma|Ultrafilter lemma}}/principle/theorem{{sfn|Bourbaki|1989|pp=57-68}}|math_statement=Every proper filter on a set <math>X</math> is contained in some ultrafilter on <math>X.</math>
}}

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

# For every prefilter on a set <math>X,</math> there exists a maximal prefilter on <math>X</math> subordinate to it.{{sfn|Narici|Beckenstein|2011|pp=2-7}}
# Every proper filter subbase on a set <math>X</math> is contained in some ultrafilter on <math>X.</math>

A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.{{sfn|Bourbaki|1987|pp=57–68}}<ref group=note>Let <math>\mathcal{F}</math> be a filter on <math>X</math> that is not an ultrafilter. If <math>S \subseteq X</math> is such that <math>S \not\in \mathcal{F}</math> then <math>\{ X \setminus S \} \cup \mathcal{F}</math> has the finite intersection property (because if <math>F \in \mathcal{F}</math> then <math>F \cap (X \setminus S) = \varnothing</math> if and only if <math>F \subseteq S</math>) so that by the ultrafilter lemma, there exists some ultrafilter <math>\mathcal{U}_S</math> on <math>X</math> such that <math>\{X \setminus S\} \cup \mathcal{F} \subseteq \mathcal{U}_S</math> (so in particular <math>S \not\in \mathcal{U}_S</math>). It follows that <math>\mathcal{F} = \bigcap_{S \subseteq X, S \not\in \mathcal{F}} \mathcal{U}_S.</math> <math>\blacksquare</math></ref>

The following results can be proven using the ultrafilter lemma. 
A free ultrafilter exists on a set <math>X</math> if and only if <math>X</math> is infinite. Every proper filter is equal to the intersection of all ultrafilters containing it.{{sfn|Bourbaki|1989|pp=57-68}} 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 <math>\mathbb{F} \neq \varnothing</math> can be extended to a free ultrafilter if and only if the intersection of any finite family of elements of <math>\mathbb{F}</math> is infinite.

===Relationships to other statements under ZF===

Throughout this section, '''ZF''' refers to [[Zermelo–Fraenkel set theory]] and '''ZFC''' refers to '''ZF''' with the Axiom of Choice ('''AC'''). The ultrafilter lemma is independent of '''ZF'''. That is, there exist [[Model theory|models]] in which the axioms of '''ZF''' hold but the ultrafilter lemma does not. There also exist models of '''ZF''' in which every ultrafilter is necessarily principal.

Every filter that contains a singleton set is necessarily an ultrafilter and given <math>x \in X,</math> the definition of the discrete ultrafilter <math>\{S \subseteq X : x \in S\}</math> does not require more than '''ZF'''.  
If <math>X</math> is finite then every ultrafilter is a discrete filter at a point; consequently, free ultrafilters can only exist on infinite sets.  
In particular, if <math>X</math> 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|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, [[Axiom of choice#Equivalents|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 a basis), (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 is {{em|not}} possible to construct an explicit example of a free ultrafilter; that is, free ultrafilters are intangible.{{sfn|Schechter|1996|p=105}} 
[[Biography:Alfred Tarski|Alfred Tarski]] proved that under '''ZFC''', the cardinality of the set of all free ultrafilters on an infinite set <math>X</math> is equal to the cardinality of <math>\wp(\wp(X)),</math> where <math>\wp(X)</math> denotes the power set of <math>X.</math>{{sfn|Schechter|1996|pp=150-152}}
Other authors attribute this discovery to Bedřich Pospíšil (following a combinatorial argument from [[Biography:Grigorii Fichtenholz|Fichtenholz]], and [[Biography:Leonid Kantorovich|Kantorovitch]], improved by [[Biography:Felix Hausdorff|Hausdorff]]).{{sfn|Jech|2006|pp=75-76}}{{sfn|Comfort|1977|p=420}}

Under '''ZF''', the [[Axiom of choice|axiom of choice]] can be used to prove both the ultrafilter lemma and the [[Krein–Milman theorem]]; conversely, under '''ZF''', the ultrafilter lemma together with the Krein–Milman theorem can prove the axiom of choice.<ref>{{cite journal|last1=Bell|first1=J.|last2=Fremlin|first2=David|title=A geometric form of the axiom of choice|journal=Fundamenta Mathematicae|date=1972|volume=77|issue=2|pages=167–170|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm77/fm77116.pdf|access-date=11 June 2018|quote=Theorem 1.2. BPI [the Boolean Prime Ideal Theorem] & KM [Krein-Milman] <math>\implies</math> (*) [the unit ball of the dual of a normed vector space has an extreme point]....  Theorem 2.1. (*) <math>\implies</math> AC [the Axiom of Choice].}}</ref>

====Statements that cannot be deduced====

The ultrafilter lemma is a relatively weak axiom. For example, each of the statements in the following list can {{em|not}} be deduced from '''ZF''' together with {{em|only}} the ultrafilter lemma:

<ol>
<li>A countable union of [[Countable set|countable set]]s is a countable set.</li>
<li>The [[Axiom of countable choice|axiom of countable choice]] ('''ACC''').</li>
<li>The [[Axiom of dependent choice|axiom of dependent choice]] ('''ADC''').</li>
</ol>

====Equivalent statements====

Under '''ZF''', the ultrafilter lemma is equivalent to each of the following statements:{{sfn|Schechter|1996|pp=105,150-160,166,237,317-315,338-340,344-346,386-393,401-402,455-456,463,474,506,766-767}}

<ol>
<li>The [[Boolean prime ideal theorem]] ('''BPIT''').
* This equivalence is provable in '''ZF''' set theory without the Axiom of Choice ('''AC''').</li>
<li>[[Stone's representation theorem for Boolean algebras]].</li>
<li>Any product of Boolean spaces is a Boolean space.{{sfn|Schechter|1996|p=463}}</li>
<li>Boolean Prime Ideal Existence Theorem: Every nondegenerate [[Boolean algebra]] has a prime ideal.{{sfn|Schechter|1996|p=339}}</li>
<li>[[Tychonoff's theorem]] for [[Hausdorff space]]s: Any [[Product topology|product]] of [[Compact space|compact]] [[Hausdorff space]]s is compact.{{sfn|Schechter|1996|p=463}}</li>
<li>If <math>\{ 0, 1 \}</math> is endowed with the discrete topology then for any set <math>I,</math> the product space <math>\{0, 1\}^I</math> is [[Compact space|compact]].{{sfn|Schechter|1996|p=463}}</li>
<li>Each of the following versions of the Banach-Alaoglu theorem is equivalent to the ultrafilter lemma:
<ol style="list-style-type: lower-latin;">
<li>Any equicontinuous set of scalar-valued maps on a [[Topological vector space|topological vector space]] (TVS) is relatively compact in the weak-* topology (that is, it is contained in some weak-* compact set).{{sfn|Schechter|1996|pp=766-767}}</li>
<li>The [[Polar set|polar]] of any neighborhood of the origin in a TVS <math>X</math> is a weak-* compact subset of its continuous dual space.{{sfn|Schechter|1996|pp=766-767}}</li>
<li>The closed unit ball in the continuous dual space of any normed space is weak-* compact.{{sfn|Schechter|1996|pp=766-767}}
* If the normed space is separable then the ultrafilter lemma is sufficient but not necessary to prove this statement.</li>
</ol>
</li>
<li>A topological space <math>X</math> is compact if every ultrafilter on <math>X</math> converges to some limit.{{sfn|Schechter|1996|p=455}}</li>
<li>A topological space <math>X</math> is compact if {{em|and only if}} every ultrafilter on <math>X</math> converges to some limit.{{sfn|Schechter|1996|p=455}}
* The addition of the words "and only if" is the only difference between this statement and the one immediately above it.</li>
<li>The Ultranet lemma: Every [[Net (mathematics)|net]] has a universal subnet.<ref name="Muger2020" />
* By definition, a [[Net (mathematics)|net]] in <math>X</math> is called an {{em|ultranet}} or an {{em|universal net}} if for every subset <math>S \subseteq X,</math> the net is eventually in <math>S</math> or in <math>X \setminus S.</math></li>
<li>A topological space <math>X</math> is compact if and only if every ultranet on <math>X</math> converges to some limit.{{sfn|Schechter|1996|p=455}}
* If the words "and only if" are removed then the resulting statement remains equivalent to the ultrafilter lemma.{{sfn|Schechter|1996|p=455}}</li>
<li>A [[Convergence space|convergence space]] <math>X</math> is compact if every ultrafilter on <math>X</math> converges.{{sfn|Schechter|1996|p=455}}</li>
<li>A [[Uniform space|uniform space]] is compact if it is complete and totally bounded.{{sfn|Schechter|1996|p=455}}</li>
<li>The Stone–Čech compactification Theorem.{{sfn|Schechter|1996|p=463}}</li>
<li>Each of the following versions of the [[Compactness theorem|compactness theorem]] is equivalent to the ultrafilter lemma: 
<ol style="list-style-type: lower-latin;">
<li>If <math>\Sigma</math> is a set of first-order [[Philosophy:Sentence (mathematical logic)|sentences]] such that every finite subset of <math>\Sigma</math> has a [[Model theory|model]], then <math>\Sigma</math> has a model.{{sfn|Schechter|1996|pp=391-392}}</li>
<li>If <math>\Sigma</math> is a set of [[Propositional calculus|zero-order]] sentences such that every finite subset of <math>\Sigma</math> has a model, then <math>\Sigma</math> has a model.{{sfn|Schechter|1996|pp=391-392}}</li>
</ol>
<li>The completeness theorem: If <math>\Sigma</math> is a set of [[Propositional calculus|zero-order]] sentences that is syntactically consistent, then it has a model (that is, it is semantically consistent).</li>
<li></li>
</ol>

====Weaker statements====

Any statement that can be deduced from the ultrafilter lemma (together with '''ZF''') is said to be {{em|weaker}} than the ultrafilter lemma. 
A weaker statement is said to be {{em|strictly weaker}} if under '''ZF''', it is not equivalent to the ultrafilter lemma. 
Under '''ZF''', the ultrafilter lemma implies each of the following statements:

<ol>
<li>The Axiom of Choice for Finite sets ('''ACF'''): Given <math>I \neq \varnothing</math> and a family <math>\left(X_i\right)_{i \in I}</math> of non-empty {{em|finite}} sets, their product <math>{\textstyle\prod\limits_{i \in I}} X_i</math> is not empty.<ref name="Muger2020">{{cite book|last=Muger|first= Michael|title=Topology for the Working Mathematician|year=2020}}</ref> </li>
<li>A [[Countable set|countable]] union of finite sets is a countable set.
* However, '''ZF''' with the ultrafilter lemma is too weak to prove that a countable union of {{em|countable}} sets is a countable set.</li>
<li>The [[Hahn–Banach theorem]].<ref name="Muger2020" />
* In '''ZF''', the Hahn–Banach theorem is strictly weaker than the ultrafilter lemma.</li>
<li>The [[Banach–Tarski paradox]].
* In fact, under '''ZF''', the Banach–Tarski paradox [[Banach–Tarski paradox#Banach–Tarski and Hahn–Banach|can be deduced]] from the [[Hahn–Banach theorem]],<ref>{{cite journal|first1=M.|last1=Foreman|first2=F.|last2=Wehrung|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm138/fm13812.pdf|title=The Hahn–Banach theorem implies the existence of a non-Lebesgue measurable set|journal=Fundamenta Mathematicae|volume=138|year=1991|pages=13–19|doi=10.4064/fm-138-1-13-19 |doi-access=free}}</ref><ref>{{cite journal|last=Pawlikowski|first=Janusz|url=http://matwbn.icm.edu.pl/ksiazki/fm/fm138/fm13813.pdf|title=The Hahn–Banach theorem implies the Banach–Tarski paradox|journal=Fundamenta Mathematicae|volume=138|year=1991|pages=21–22|doi=10.4064/fm-138-1-21-22|doi-access=free}}</ref> which is strictly weaker than the Ultrafilter Lemma.</li>
<li>Every set can be linearly ordered.</li>
<li>Every [[Field (mathematics)|field]] has a unique algebraic closure.</li>
<li>The Alexander subbase theorem.<ref name="Muger2020" /></li>
<li>Non-trivial ultraproducts exist.</li>
<li>The weak ultrafilter theorem: A free ultrafilter exists on <math>\N.</math>
* Under '''ZF''', the weak ultrafilter theorem does not imply the ultrafilter lemma; that is, it is strictly weaker than the ultrafilter lemma.</li>
<li>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 on {{em|some}} set. 
</li>
</ol>

==Completeness==<!-- This section is linked from [[Martin measure]] -->

The '''completeness''' of an ultrafilter <math>U</math> on a powerset is the smallest [[Cardinal number|cardinal]] κ such that there are κ elements of <math>U</math> whose intersection is not in <math>U.</math> The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least <math>\aleph 0</math>. An ultrafilter whose completeness is {{em|greater}} than <math>\aleph_0</math>—that is, the intersection of any countable collection of elements of <math>U</math> is still in <math>U</math>—is called '''countably complete''' or '''σ-complete'''.

The completeness of a countably complete nonprincipal ultrafilter on a powerset is always a [[Measurable cardinal|measurable cardinal]].{{citation needed|date=July 2016}}

=={{vanchor|Ordering on ultrafilters|Ordering}}==
The '''{{visible anchor|Rudin–Keisler ordering}}''' (named after [[Biography:Mary Ellen Rudin|Mary Ellen Rudin]] and Howard Jerome Keisler) is a [[Preorder|preorder]] on the class of powerset ultrafilters defined as follows: if <math>U</math> is an ultrafilter on <math>\wp(X),</math> and <math>V</math> an ultrafilter on <math>\wp(Y),</math> then <math>V \leq {}_{RK} U</math> if there exists a function <math>f : X \to Y</math> such that
:<math>C \in V</math> if and only if <math>f^{-1}[C] \in U</math>
for every subset <math>C \subseteq Y.</math>

Ultrafilters <math>U</math> and <math>V</math> are called '''{{visible anchor|Rudin–Keisler equivalent}}''', denoted {{math|''U'' ≡<sub>RK</sub> ''V''}}, if there exist sets <math>A \in U</math> and <math>B \in V</math> and a [[Bijection|bijection]] <math>f : A \to B</math> that satisfies the condition above. (If <math>X</math> and <math>Y</math> have the same cardinality, the definition can be simplified by fixing <math>A = X,</math> <math>B = Y.</math>)

It is known that ≡<sub>RK</sub> is the [[Kernel (set theory)|kernel]] of ≤<sub>RK</sub>, i.e., that {{math|''U'' ≡<sub>RK</sub> ''V''}} if and only if <math>U \leq {}_{RK} V</math> and <math>V \leq {}_{RK} U.</math><ref>{{cite book|last1=Comfort|first1=W. W.|last2=Negrepontis|first2=S.|title=The theory of ultrafilters|publisher=[[Physics:Springer-Verlag|Springer-Verlag]]|location=Berlin, New York|mr=0396267|year=1974}} Corollary 9.3.</ref>

==Ultrafilters on ℘(ω)== 
{{anchor|Ramsey}}

There are several special properties that an ultrafilter on <math>\wp(\omega),</math> where <math>\omega</math> [[Ordinal number#Ordinals extend the natural numbers|extends the natural numbers]], may possess, which prove useful in various areas of set theory and topology.
* A non-principal ultrafilter <math>U</math> is called a '''P-point''' (or '''{{visible anchor|weakly selective}}''') if for every [[Partition of a set|partition]] <math>\left\{ C_n : n < \omega \right\}</math> of <math>\omega</math> such that for all <math>n < \omega,</math> <math>C_n \not\in U,</math> there exists some <math>A \in U</math> such that <math>A \cap C_n</math> is a finite set for each <math>n.</math> 
* A non-principal ultrafilter <math>U</math> is called '''Ramsey''' (or '''selective''') if for every partition <math>\left\{ C_n : n < \omega \right\}</math> of <math>\omega</math> such that for all <math>n < \omega,</math> <math>C_n \not\in U,</math> there exists some <math>A \in U</math> such that <math>A \cap C_n</math> is a singleton set for each <math>n.</math>

It is a trivial observation that all Ramsey ultrafilters are P-points. [[Biography:Walter Rudin|Walter Rudin]] proved that the [[Continuum hypothesis|continuum hypothesis]] implies the existence of Ramsey ultrafilters.<ref>{{Citation|last = Rudin|first =Walter|title = Homogeneity problems in the theory of Čech compactifications|journal = Duke Mathematical Journal|volume = 23|issue = 3|pages = 409–419|year = 1956|doi = 10.1215/S0012-7094-56-02337-7|hdl = 10338.dmlcz/101493|hdl-access = free}}</ref>
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including [[Martin's axiom]]. [[Biography:Saharon Shelah|Saharon Shelah]] later showed that it is consistent that there are no P-point ultrafilters.<ref>{{Citation|last = Wimmers|first = Edward|title = The Shelah P-point independence theorem|journal = [[Israel Journal of Mathematics]]|volume = 43|issue = 1|pages = 28–48|date = March 1982|doi = 10.1007/BF02761683|doi-access=free|s2cid = 122393776}}</ref> Therefore, the existence of these types of ultrafilters is [[Independence (mathematical logic)|independent]] of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space [[Stone–Čech compactification|{{nowrap|βω \ ω}}]] 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 <math>[\omega]^2</math> there exists an element of the ultrafilter that has a homogeneous color.

An ultrafilter on <math>\wp(\omega)</math> is Ramsey if and only if it is minimal in the Rudin–Keisler ordering of non-principal powerset ultrafilters.{{sfn|Jech|2006|p=91|ps= (Left as exercise '''7.12''')}}

==See also==

* {{annotated link|Extender (set theory)}}
* {{annotated link|Filter (mathematics)}}
* {{annotated link|Filter (set theory)}}
* {{annotated link|Filters in topology}}
* {{annotated link|Ultrafilter}}

==Notes==

{{reflist|group=note}}

'''Proofs'''

{{reflist|group=proof}}

==References==

{{reflist}}

==Bibliography==

* {{Arkhangel'skii Ponomarev Fundamentals of General Topology Problems and Exercises|edition=2}} <!-- {{sfn|Arkhangelʹskiĭ|Ponomarev|1984|p=}} -->
* {{Bourbaki General Topology Part I Chapters 1-4}} <!-- {{sfn|Bourbaki|1998|p=}} -->
* {{Dixmier General Topology}} <!-- {{sfn|Dixmier|1984|p=}} -->
* {{Dolecki Mynard Convergence Foundations Of Topology}} <!-- {{sfn|Dolecki|Mynard|2016|p=}} -->
* {{Dugundji Topology}} <!-- {{sfn|Dugundji|1966|p=}} -->
* {{Császár General Topology}} <!-- {{sfn|Császár|1978|p=}} -->
* {{cite book|last=Jech|first=Thomas|title = Set Theory: The Third Millennium Edition, Revised and Expanded|publisher=Springer Science & Business Media|publication-place=Berlin New York|year=2006|isbn=978-3-540-44085-7|oclc=50422939}} <!-- {{sfn|Jech|2006|p=}} -->
* {{Joshi Introduction to General Topology}} <!-- {{sfn|Joshi|1983|p=}} -->
* {{Narici Beckenstein Topological Vector Spaces|edition=2}} <!-- {{sfn|Narici|Beckenstein|2011|p=}} -->
* {{Schechter Handbook of Analysis and Its Foundations}} <!-- {{sfn|Schechter|1996|p=}} -->
* {{Schubert Topology}} <!-- {{sfn|Schubert|1968|p=}} -->

==Further reading==

* {{cite journal|last1=Comfort|first1=W. W.|title=Ultrafilters: some old and some new results|doi=10.1090/S0002-9904-1977-14316-4|mr=0454893|year=1977|journal=[[Organization:Bulletin of the American Mathematical Society|Bulletin of the American Mathematical Society]]|issn=0002-9904|volume=83|issue=4|pages=417–455|doi-access=free }}
* {{Citation|last1=Comfort|first1=W. W.|last2=Negrepontis|first2=S.|title=The theory of ultrafilters|publisher=[[Physics:Springer-Verlag|Springer-Verlag]]|location=Berlin, New York|mr=0396267|year=1974}}
* {{nlab|title=Ultrafilter|id=ultrafilter}}

{{Mathematical logic}}

[[Category:Nonstandard analysis]]
[[Category:Order theory]]

{{Sourceattribution|Ultrafilter (set theory)|1}}