View source for Ultrafilter

{{short description|Maximal proper filter}}
{{About|the mathematical concept in [[order theory]]|ultrafilters on [[Set (mathematics)|sets]] specifically|Ultrafilter on a set|the physical device|ultrafiltration}}
[[File:Filter vs ultrafilter_210div.svg|thumb|[[Hasse diagram]] of the [[divisor]]s of 210, ordered by the relation ''is divisor of'', with the [[upper set]] ↑14 colored dark green. It is a {{em|principal filter}}, but not an {{em|ultrafilter}}, as it can be extended to the larger nontrivial filter ↑2, by including also the light green elements. Since ↑2 cannot be extended any further, it is an ultrafilter.]]
In the [[Mathematics|mathematical]] field of [[order theory]], an '''ultrafilter''' on a given [[partially ordered set]] (or "poset") <math display="inline">P</math> is a certain subset of <math>P,</math> namely a [[Maximal element|maximal]] [[Filter (mathematics)|filter]] on <math>P;</math> that is, a [[proper filter]] on <math display="inline">P</math> that cannot be enlarged to a bigger proper filter on <math>P.</math>

If <math>X</math> is an arbitrary set, its [[power set]] <math>{\mathcal P}(X),</math> ordered by [[set inclusion]], is always a [[Boolean algebra (structure)|Boolean algebra]] and hence a poset, and ultrafilters on <math>{\mathcal P}(X)</math> are usually called {{em|[[Ultrafilter on a set|ultrafilters on the set]]}} <math>X</math>.<ref name="notation warning" group="note">If <math>X</math> happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on <math>{\mathcal P}(X)</math> or an (ultra)filter just on <math>X</math> is meant; both kinds of (ultra)filters are quite different. Some authors{{cn|date=July 2016}} use "(ultra)filter ''of'' a partial ordered set" vs. "''on'' an arbitrary set"; i.e. they write "(ultra)filter on <math>X</math>" to abbreviate "(ultra)filter of <math>{\mathcal P}(X)</math>".<!---guessed from a sentence in section "Types and existence of ultrafilters" which is now commented-out---></ref> An ultrafilter on a set <math>X</math> may be considered as a [[finitely additive]] 0-1-valued [[measure (mathematics)|measure]] on <math>{\mathcal P}(X)</math>. In this view, every subset of <math>X</math> is either considered "[[Almost everywhere|almost everything]]" (has measure 1) or "almost nothing" (has measure 0), depending on whether it belongs to the given ultrafilter or not.{{r|Kruckman.2012|at=§4}}

Ultrafilters have many applications in set theory, [[model theory]], [[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}} and combinatorics.<ref>{{Cite journal|last=Goldbring|first=Isaac|date=2021|others=Marta Maggioni, Sophia Jahns|title=Ultrafilter methods in combinatorics|url=http://publications.mfo.de/handle/mfo/3870|journal=Snapshots of Modern Mathematics from Oberwolfach |language=en|doi=10.14760/SNAP-2021-006-EN}}</ref>

==Ultrafilters on partial orders==

In [[order theory]], an '''ultrafilter''' is a [[subset]] of a [[partially ordered set]] that is [[Maximal element|maximal]] among all [[proper filter]]s.  This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.

Formally, if <math display="inline">P</math> is a set, partially ordered by <math>\,\leq\,</math> then 
* a subset <math>F \subseteq P</math> is called a '''filter''' on <math display="inline">P</math> if
** <math>F</math> is nonempty,
** for every <math>x, y \in F,</math> there exists some element <math>z \in F</math> such that <math>z \leq x</math> and <math>z \leq y,</math> and
** for every <math>x \in F</math> and <math>y \in P,</math> <math>x \leq y</math> implies that <math>y</math> is in <math>F</math> too;
* a [[proper subset]] <math>U</math> of <math display="inline">P</math> is called an '''ultrafilter''' on <math display="inline">P</math> if
** <math>U</math> is a filter on <math>P,</math> and
** there is no proper filter <math>F</math> on <math display="inline">P</math> that properly extends <math>U</math> (that is, such that <math>U</math> is a proper subset of <math>F</math>).

==={{vanchor|Types and existence of ultrafilters|Types}}===

Every ultrafilter falls into exactly one of two categories: principal or free. A '''principal''' (or '''fixed''', or '''trivial''') ultrafilter is a filter containing a [[least element]]. Consequently, each principal ultrafilter is of the form <math>F_p = \{x : p \leq x\}</math> for some element <math>p</math> of the given poset. In this case <math>p</math> is called the {{em|principal element}} of the ultrafilter. Any ultrafilter that is not principal is called a '''free''' (or '''non-principal''') ultrafilter. For arbitrary <math>p</math>, the set <math>F_p</math> is a filter, called the principal filter at <math>p</math>; it is a principal ultrafilter only if it is maximal.

For ultrafilters on a powerset <math>{\mathcal P}(X),</math> a principal ultrafilter consists of all subsets of <math>X</math> that contain a given element <math>x \in X.</math> Each ultrafilter on <math>{\mathcal P}(X)</math> that is also a [[principal filter]] is of this form.<ref name="Davey.Priestley.1990"/>{{rp|187}} Therefore, an ultrafilter <math>U</math> on <math>{\mathcal P}(X)</math> is principal if and only if it contains a finite set.<ref group="note">To see the "if" direction: If <math>\left\{x_1, \ldots, x_n\right\} \in U,</math> then <math>\left\{x_1\right\} \in U, \text{ or } \ldots \text{ or } \left\{x_n\right\} \in U,</math> by the characterization Nr.7 from [[Ultrafilter on a set#Characterizations]]. That is, some <math>\left\{x_i\right\}</math> is the principal element of <math>U.</math></ref> If <math>X</math> is infinite, an ultrafilter <math>U</math> on <math>{\mathcal P}(X)</math> is hence non-principal if and only if it contains the [[Fréchet filter]] of [[cofinite subset]]s of <math>X.</math><ref group="note"><math>U</math> is non-principal if and only if it contains no finite set, that is, (by Nr.3 of the [[#Special case: ultrafilter on the powerset of a set|above]] characterization theorem) if and only if it contains every cofinite set, that is, every member of the Fréchet filter.</ref>{{R|Kaya.2019|at=Proposition 3}} If <math>X</math> is finite, every ultrafilter is principal.<ref name="Davey.Priestley.1990"/>{{rp|187}} 
If <math>X</math> is infinite then the [[Fréchet filter]] is not an ultrafilter on the power set of <math>X</math> but it is an ultrafilter on the [[finite–cofinite algebra]] of <math>X.</math> 

Every filter on a Boolean algebra (or more generally, any subset with the [[finite intersection property]]) is contained in an ultrafilter (see [[ultrafilter lemma]]) and free ultrafilters therefore exist, but the proofs involve the [[axiom of choice]] ('''AC''') in the form of [[Zorn's lemma]]. On the other hand, the statement that every filter is contained in an ultrafilter does not imply '''AC'''. Indeed, it is equivalent to the [[Boolean prime ideal theorem]] ('''BPIT'''), a well-known intermediate point between the axioms of [[Zermelo–Fraenkel set theory]] ('''ZF''') and the '''ZF''' theory augmented by the axiom of choice ('''ZFC'''). In general, proofs involving the axiom of choice do not produce explicit examples of free ultrafilters, though it is possible to find explicit examples in some models of '''ZFC''';  for example, [[Kurt Gödel|Gödel]] showed that this can be done in the [[constructible universe]] where one can write down an explicit global choice function.  <!---commented out: "almost all" is vague in absence of a measure, "all UFs principal on finite sets" has been said above---Nonetheless, almost all ultrafilters on the powerset of an infinite set are free. By contrast, every ultrafilter of a finite poset (or {{em|on}} a finite set) is principal, since any finite filter has a least element.---> In '''ZF''' without the axiom of choice, it is possible that every ultrafilter is principal.<ref name="Halbeisen2012">{{cite book|first= L. J.|last= Halbeisen|title= Combinatorial Set Theory|publisher= Springer|year= 2012|series= Springer Monographs in Mathematics}}</ref>

==Ultrafilter on a Boolean algebra==

An important special case of the concept occurs if the considered poset is a [[Boolean algebra (structure)|Boolean algebra]].  In this case, ultrafilters are characterized by containing, for each element <math>x</math> of the Boolean algebra, exactly one of the elements <math>x</math> and <math>\lnot x</math> (the latter being the [[Boolean algebra#Nonmonotone laws|Boolean complement]] of <math>x</math>):

If <math display="inline">P</math> is a Boolean algebra and <math>F</math> is a proper filter on <math>P,</math> then the following statements are equivalent:
# <math>F</math> is an ultrafilter on <math>P,</math>
# <math>F</math> is a [[prime filter]] on <math>P,</math>
# for each <math>x \in P,</math> either <math>x \in F</math> or (<math>\lnot x</math>) <math>\in F.</math><ref name="Davey.Priestley.1990"/>{{rp|186}}
A proof that 1. and 2. are equivalent is also given in (Burris, Sankappanavar, 2012, Corollary 3.13, p.133).<ref name="Burris.Sankappanavar.2012">{{cite book|url= http://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra2012.pdf|isbn=978-0-9880552-0-9|first1= Stanley N.|last1= Burris|first2= H. P.|last2= Sankappanavar|title=A Course in Universal Algebra|year=2012 |publisher=S. Burris and H.P. Sankappanavar }}</ref>

Moreover, ultrafilters on a Boolean algebra can be related to [[Boolean algebra (structure)#Ideals and filters|maximal ideals]] and [[Boolean algebra (structure)#Homomorphisms and isomorphisms|homomorphisms]] to the 2-element Boolean algebra {true, false} (also known as [[2-valued morphism]]s) as follows:
* Given a homomorphism of a Boolean algebra onto {true, false}, the [[inverse image]] of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
* Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
* Given an ultrafilter on a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".{{cn|date=July 2016}}

==Ultrafilter on the power set of a set==
{{Main|Ultrafilter on a set}}

Given an arbitrary set <math>X,</math> its [[power set]] <math>{\mathcal P}(X),</math> ordered by [[set inclusion]], is always a Boolean algebra; hence the results of the above section apply. An (ultra)filter on <math>{\mathcal P}(X)</math> is often called just an "(ultra)filter on <math>X</math>".<ref name="notation warning" group=note/> Given an arbitrary set <math>X,</math> an ultrafilter on <math>{\mathcal P}(X)</math> is a set <math>\mathcal U</math> consisting of subsets of <math>X</math> such that:
#The empty set is not an element of <math>\mathcal U</math>.
#If <math>A</math> is an element of <math>\mathcal U</math> then so is every superset <math>B\supset A</math>.
#If <math>A</math> and <math>B</math> are elements of <math>\mathcal U</math> then so is the [[Intersection (set theory)|intersection]] <math>A\cap B</math>.
#If <math>A</math> is a subset of <math>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 complement <math>X \setminus A</math> is an element of <math>\mathcal U</math>.

Equivalently, a family <math>\mathcal U</math> of subsets of <math>X</math> is an ultrafilter if and only if for any finite collection <math>\mathcal F</math> of subsets of <math>X</math>, there is some <math>x\in X</math> such that <math>\mathcal U\cap\mathcal F=F_x\cap\mathcal F</math> where <math>F_x=\{Y\subseteq X : x \in Y\}</math> is the principal ultrafilter seeded by <math>x</math>. In other words, an ultrafilter may be seen as a family of sets which "locally" resembles a principal ultrafilter.{{cn|date=December 2023}}

An equivalent form of a given <math>\mathcal U</math> is a [[2-valued morphism]], a function <math>m</math> on <math>{\mathcal P}(X)</math> defined as <math>m(A) = 1</math> if <math>A</math> is an element of <math>\mathcal U</math> and <math>m(A) = 0</math> otherwise. Then <math>m</math> is [[finitely additive]], and hence a {{em|[[Content (measure theory)|content]]}} on <math>{\mathcal P}(X),</math> and every property of elements of <math>X</math> is either true [[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.

For a filter <math>\mathcal F</math> that is not an ultrafilter, one can define <math>m(A) = 1</math> if <math>A \in \mathcal F</math> and <math>m(A) = 0</math> if <math>X \setminus A \in \mathcal F,</math> leaving <math>m</math> undefined elsewhere.<ref name="Kruckman.2012">{{Cite web |title=Notes on Ultrafilters |url=https://math.berkeley.edu/~kruckman/ultrafilters.pdf|author=Alex Kruckman|date=November 7, 2012|publisher=Berkeley Math Toolbox Seminar}}</ref>

==Applications==

Ultrafilters on [[power set]]s are useful in [[topology]], especially in relation to [[Compact space|compact]] [[Hausdorff space|Hausdorff]] spaces, and in [[model theory]] in the construction of [[Ultraproduct|ultraproducts and ultrapowers]]. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on Boolean algebras play a central role in [[Stone's representation theorem for Boolean algebras|Stone's representation theorem]]. In [[set theory]] ultrafilters are used to show that the [[axiom of constructibility]] is incompatible with the existence of a [[measurable cardinal]] {{mvar|κ}}. This is proved by taking the ultrapower of the set theoretical universe modulo a {{mvar|κ}}-complete, non-principal ultrafilter.<ref> Kanamori, The Higher infinite, p. 49.</ref>

The set <math>G</math> of all ultrafilters of a poset <math display="inline">P</math> can be topologized in a natural way, that is in fact closely related to the above-mentioned representation theorem. For any element <math>x</math> of <math display="inline">P</math>, let <math>D_x = \left\{ U \in G : x \in U \right\}.</math> This is most useful when <math display="inline">P</math> is again a Boolean algebra, since in this situation the set of all <math>D_x</math> is a base for a compact Hausdorff topology on <math>G</math>. Especially, when considering the ultrafilters on a powerset <math>{\mathcal P}(S)</math>, the resulting [[topological space]] is the [[Stone–Čech compactification]] of a [[discrete space]] of cardinality <math>| S |.</math>

The [[ultraproduct]] construction in [[model theory]] uses ultrafilters to produce a new model starting from a sequence of <math>X</math>-indexed models; for example, the [[compactness theorem]] can be proved this way.
In the special case of ultrapowers, one gets [[elementary extension]]s of structures. For example, in [[nonstandard analysis]], the [[hyperreal number]]s can be constructed as an ultraproduct of the [[real numbers]], extending the [[domain of discourse]] from real numbers to sequences of real numbers. This sequence space is regarded as a [[superset]] of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead the functions and relations are defined "[[Ultraproduct#Definition|pointwise modulo]]" <math>U</math>, where <math>U</math> is an ultrafilter on the [[index set]] of the sequences; by [[Łoś' theorem]], this preserves all properties of the reals that can be stated in [[first-order logic]]. If <math>U</math> is nonprincipal, then the extension thereby obtained is nontrivial.

In [[geometric group theory]], non-principal ultrafilters are used to define the [[Ultralimit#Asymptotic cones|asymptotic cone]] of a group. This construction yields a rigorous way to consider {{em|looking at the group from infinity}}, that is the large scale geometry of the group. Asymptotic cones are particular examples of [[ultralimit]]s of [[metric space]]s.

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

In [[social choice theory]], non-principal ultrafilters are used to define a rule (called a ''social welfare function'') for aggregating the preferences of ''infinitely'' many individuals. Contrary to [[Arrow's impossibility theorem]] for ''finitely'' many individuals, such a rule satisfies the conditions (properties) that Arrow proposes (for example, Kirman and Sondermann, 1972).<ref>{{Cite journal|last1 = Kirman|first1 = A.|last2 = Sondermann|first2 = D.|title = Arrow's theorem, many agents, and invisible dictators|journal = Journal of Economic Theory|volume = 5|issue = 2|pages = 267–277|year = 1972|doi = 10.1016/0022-0531(72)90106-8}}</ref> Mihara (1997,<ref name=mihara97>{{Cite journal|last1 = Mihara|first1 = H. R.|title = Arrow's Theorem and Turing computability|journal = Economic Theory|volume = 10|issue = 2|pages = 257–276|year = 1997|postscript = Reprinted in K. V. Velupillai, S. Zambelli, and S. Kinsella, ed., Computable Economics, International Library of Critical Writings in Economics, Edward Elgar, 2011.|doi = 10.1007/s001990050157|url = https://econwpa.ub.uni-muenchen.de/econ-wp/pe/papers/9408/9408001.pdf|citeseerx = 10.1.1.200.520|s2cid = 15398169 }}</ref> 1999)<ref name=mihara99>{{Cite journal|last1 = Mihara|first1 = H. R.|title = Arrow's theorem, countably many agents, and more visible invisible dictators|journal = [[Journal of Mathematical Economics]]|volume = 32|issue = 3|pages = 267–277|year = 1999|doi = 10.1016/S0304-4068(98)00061-5|url= http://econpapers.repec.org/paper/wpawuwppe/9705001.htm|citeseerx = 10.1.1.199.1970}}</ref> shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.

==See also==

* {{annotated link|Filter (mathematics)}}
* {{annotated link|Filter on a set}}
* {{annotated link|Filters in topology}}
* {{annotated link|The ultrafilter lemma}}
* {{annotated link|Universal net}}

==Notes==
{{reflist|group=note}}

==References==
{{reflist|refs=
<ref name="Kaya.2019">[https://users.metu.edu.tr/burakk/lecturenotes/village2019lecturenotes.pdf "Ultrafilters and how to use them"], Burak Kaya, lecture notes, Nesin Mathematics Village, Summer 2019.</ref>
}}

==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|author-link=Thomas Jech|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=[[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=[[Springer-Verlag]]|location=Berlin, New York|mr=0396267|year=1974}}
*{{nlab|title=Ultrafilter|id=ultrafilter}}
*{{YouTube|id=0H2rf8bluOE|title="Mathematical Logic 15, The Ultrafilter Theorem"}}

[[Category:Order theory]]
[[Category:Families of sets]]
[[Category:Nonstandard analysis]]