Editing Ultrafilter (section)

==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 (set theory)#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>