Ultrafilter

 ( Order Theory ) 

In the Mathematics field of order theory, an ultrafilter on a given partially ordered set (or "poset") $P$ is a certain subset of $P,$ namely a Maximal element filter on $P;$ that is, a proper filter on $P$ that cannot be enlarged to a bigger proper filter on $P.$

If $X$ is an arbitrary set, its power set $\{\backslash mathcal\; P\}(X),$ ordered by set inclusion, is always a Boolean algebra and hence a poset, and ultrafilters on $\{\backslash mathcal\; P\}(X)$ are usually called $X$.If $X$ happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on $\{\backslash mathcal\; P\}(X)$ or an (ultra)filter just on $X$ is meant; both kinds of (ultra)filters are quite different. Some authors use "(ultra)filter of a partial ordered set" vs. " on an arbitrary set"; i.e. they write "(ultra)filter on $X$" to abbreviate "(ultra)filter of $\{\backslash mathcal\; P\}(X)$". An ultrafilter on a set $X$ may be considered as a finitely additive 0-1-valued measure on $\{\backslash mathcal\; P\}(X)$. In this view, every subset of $X$ is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0), depending on whether it belongs to the given ultrafilter or not.

Ultrafilters have many applications in set theory, model theory, topology and combinatorics.

---

Ultrafilters on partial orders In order theory, an ultrafilter is a subset of a partially ordered set that is Maximal element among all . This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.

Formally, if $P$ is a set, partially ordered by $\backslash ,\backslash leq\backslash ,$ then

• a subset $F\; \backslash subseteq\; P$ is called a filter on $P$ if
• $F$ is nonempty,
• for every $x,\; y\; \backslash in\; F,$ there exists some element $z\; \backslash in\; F$ such that $z\; \backslash leq\; x$ and $z\; \backslash leq\; y,$ and
• for every $x\; \backslash in\; F$ and $y\; \backslash in\; P,$ $x\; \backslash leq\; y$ implies that $y$ is in $F$ too;
• a proper subset $U$ of $P$ is called an ultrafilter on $P$ if
• $U$ is a filter on $P,$ and
• there is no proper filter $F$ on $P$ that properly extends $U$ (that is, such that $U$ is a proper subset of $F$).

---

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 $F\_p\; =\; \backslash \{x\; :\; p\; \backslash leq\; x\backslash \}$ for some element $p$ of the given poset. In this case $p$ is called the of the ultrafilter. Any ultrafilter that is not principal is called a free (or non-principal) ultrafilter. For arbitrary $p$, the set $F\_p$ is a filter, called the principal filter at $p$; it is a principal ultrafilter only if it is maximal.

For ultrafilters on a powerset $\{\backslash mathcal\; P\}(X),$ a principal ultrafilter consists of all subsets of $X$ that contain a given element $x\; \backslash in\; X.$ Each ultrafilter on $\{\backslash mathcal\; P\}(X)$ that is also a principal filter is of this form. Therefore, an ultrafilter $U$ on $\{\backslash mathcal\; P\}(X)$ is principal if and only if it contains a finite set.To see the "if" direction: If $\backslash left\backslash \{x\_1,\; \backslash ldots,\; x\_n\backslash right\backslash \}\; \backslash in\; U,$ then $\backslash left\backslash \{x\_1\backslash right\backslash \}\; \backslash in\; U,\; \backslash text\{\; or\; \}\; \backslash ldots\; \backslash text\{\; or\; \}\; \backslash left\backslash \{x\_n\backslash right\backslash \}\; \backslash in\; U,$ by the characterization Nr.7 from Ultrafilter on a set#Characterizations. That is, some $\backslash left\backslash \{x\_i\backslash right\backslash \}$ is the principal element of $U.$ If $X$ is infinite, an ultrafilter $U$ on $\{\backslash mathcal\; P\}(X)$ is hence non-principal if and only if it contains the Fréchet filter of of $X.$$U$ is non-principal if and only if it contains no finite set, that is, (by Nr.3 of the characterization theorem) if and only if it contains every cofinite set, that is, every member of the Fréchet filter. If $X$ is finite, every ultrafilter is principal. If $X$ is infinite then the Fréchet filter is not an ultrafilter on the power set of $X$ but it is an ultrafilter on the finite–cofinite algebra of $X.$

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, Gödel showed that this can be done in the constructible universe where one can write down an explicit global choice function. In ZF without the axiom of choice, it is possible that every ultrafilter is principal.

---

Ultrafilter on a Boolean algebra An important special case of the concept occurs if the considered poset is a Boolean algebra. In this case, ultrafilters are characterized by containing, for each element $x$ of the Boolean algebra, exactly one of the elements $x$ and $\backslash lnot\; x$ (the latter being the Boolean complement of $x$):

If $P$ is a Boolean algebra and $F$ is a proper filter on $P,$ then the following statements are equivalent:

1. $F$ is an ultrafilter on $P,$
2. $F$ is a prime filter on $P,$
3. for each $x\; \backslash in\; P,$ either $x\; \backslash in\; F$ or ($\backslash lnot\; x$) $\backslash in\; F.$

A proof that 1. and 2. are equivalent is also given in (Burris, Sankappanavar, 2012, Corollary 3.13, p.133).

(2025). 9780988055209, S. Burris and H.P. Sankappanavar. . ISBN 9780988055209

Moreover, ultrafilters on a Boolean algebra can be related to maximal ideals and homomorphisms to the 2-element Boolean algebra {true, false} (also known as 2-valued morphisms) 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".

---

Ultrafilter on the power set of a set Given an arbitrary set $X,$ its power set $\{\backslash mathcal\; P\}(X),$ ordered by set inclusion, is always a Boolean algebra; hence the results of the above section apply. An (ultra)filter on $\{\backslash mathcal\; P\}(X)$ is often called just an "(ultra)filter on $X$". Given an arbitrary set $X,$ an ultrafilter on $\{\backslash mathcal\; P\}(X)$ is a set $\backslash mathcal\; U$ consisting of subsets of $X$ such that:

1. The empty set is not an element of $\backslash mathcal\; U$.
2. If $A$ is an element of $\backslash mathcal\; U$ then so is every superset $B\backslash supset\; A$.
3. If $A$ and $B$ are elements of $\backslash mathcal\; U$ then so is the intersection $A\backslash cap\; B$.
4. If $A$ is a subset of $X,$ then eitherProperties 1 and 3 imply that $A$ and $X\; \backslash setminus\; A$ cannot be elements of $U.$ $A$ or its complement $X\; \backslash setminus\; A$ is an element of $\backslash mathcal\; U$.

Equivalently, a family $\backslash mathcal\; U$ of subsets of $X$ is an ultrafilter if and only if for any finite collection $\backslash mathcal\; F$ of subsets of $X$, there is some $x\backslash in\; X$ such that $\backslash mathcal\; U\backslash cap\backslash mathcal\; F=F\_x\backslash cap\backslash mathcal\; F$ where $F\_x=\backslash \{Y\backslash subseteq\; X\; :\; x\; \backslash in\; Y\backslash \}$ is the principal ultrafilter seeded by $x$. In other words, an ultrafilter may be seen as a family of sets which "locally" resembles a principal ultrafilter.

An equivalent form of a given $\backslash mathcal\; U$ is a 2-valued morphism, a function $m$ on $\{\backslash mathcal\; P\}(X)$ defined as $m(A)\; =\; 1$ if $A$ is an element of $\backslash mathcal\; U$ and $m(A)\; =\; 0$ otherwise. Then $m$ is finitely additive, and hence a on $\{\backslash mathcal\; P\}(X),$ and every property of elements of $X$ is either true almost everywhere or false almost everywhere. However, $m$ is usually not , and hence does not define a measure in the usual sense.

For a filter $\backslash mathcal\; F$ that is not an ultrafilter, one can define $m(A)\; =\; 1$ if $A\; \backslash in\; \backslash mathcal\; F$ and $m(A)\; =\; 0$ if $X\; \backslash setminus\; A\; \backslash in\; \backslash mathcal\; F,$ leaving $m$ undefined elsewhere.

---

Applications

Ultrafilters on are useful in topology, especially in relation to Compact space Hausdorff space spaces, and in model theory in the construction of Ultraproduct. 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. In set theory ultrafilters are used to show that the axiom of constructibility is incompatible with the existence of a measurable cardinal . This is proved by taking the ultrapower of the set theoretical universe modulo a -complete, non-principal ultrafilter. Kanamori, The Higher infinite, p. 49.

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

The ultraproduct construction in model theory uses ultrafilters to produce a new model starting from a sequence of $X$-indexed models; for example, the compactness theorem can be proved this way. In the special case of ultrapowers, one gets elementary extensions of structures. For example, in nonstandard analysis, the 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 "pointwise modulo" $U$, where $U$ 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 $U$ is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory, non-principal ultrafilters are used to define the asymptotic cone of a group. This construction yields a rigorous way to consider , that is the large scale geometry of the group. Asymptotic cones are particular examples of of .

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). Mihara (1997, 1999) shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.

---

See also

---

Notes

---

Bibliography

• Thomas Jech (2025). 9783540440857, Springer Science & Business Media. ISBN 9783540440857

---

Further reading

Categories: Order Theory, Families Of Sets, Nonstandard Analysis

Post Comment