Ultrafilter

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 ${\displaystyle x}$ of the Boolean algebra, exactly one of the elements ${\displaystyle x}$ and ${\displaystyle \mathrm{\neg }x}$ (the latter being the Boolean complement of ${\displaystyle x}$):

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

1. ${\displaystyle F}$ is an ultrafilter on ${\displaystyle P,}$
2. ${\displaystyle F}$ is a prime filter on ${\displaystyle P,}$
3. for each ${\displaystyle x\in P,}$ either ${\displaystyle x\in F}$ or (${\displaystyle \mathrm{\neg }x}$) ${\displaystyle \in F.}$

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

1. The empty set is not an element of ${\displaystyle \mathcal{U}}$.
2. If ${\displaystyle A}$ is an element of ${\displaystyle \mathcal{U}}$ then so is every superset ${\displaystyle B\supset A}$.
3. If ${\displaystyle A}$ and ${\displaystyle B}$ are elements of ${\displaystyle \mathcal{U}}$ then so is the intersection ${\displaystyle A\cap B}$.
4. If ${\displaystyle A}$ is a subset of ${\displaystyle X,}$ then either ${\displaystyle A}$ or its complement ${\displaystyle X\setminus A}$ is an element of ${\displaystyle \mathcal{U}}$.

Equivalently, a family ${\displaystyle \mathcal{U}}$ of subsets of ${\displaystyle X}$ is an ultrafilter if and only if for any finite collection ${\displaystyle \mathcal{F}}$ of subsets of ${\displaystyle X}$, there is some ${\displaystyle x\in X}$ such that ${\displaystyle \mathcal{U}\cap \mathcal{F}=F_x\cap \mathcal{F}}$ where ${\displaystyle F_x=\{Y\subseteq X:x\in Y\}}$ is the principal ultrafilter seeded by ${\displaystyle 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 ${\displaystyle \mathcal{U}}$ is a 2-valued morphism, a function ${\displaystyle m}$ on ${\displaystyle \mathcal{P}(X)}$ defined as ${\displaystyle m(A)=1}$ if ${\displaystyle A}$ is an element of ${\displaystyle \mathcal{U}}$ and ${\displaystyle m(A)=0}$ otherwise. Then ${\displaystyle m}$ is finitely additive, and hence a content on ${\displaystyle \mathcal{P}(X),}$ and every property of elements of ${\displaystyle X}$ is either true almost everywhere or false almost everywhere. However, ${\displaystyle m}$ is usually not countably additive, and hence does not define a measure in the usual sense.

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

Applications

Ultrafilters on power sets are useful in topology, especially in relation to compact Hausdorff spaces, and in model theory in the construction of 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. 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.

The set ${\displaystyle 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 ${\displaystyle x}$ of $P$, let ${\displaystyle D_x=\left\{U\in G:x\in U\right\}.}$ This is most useful when $P$ is again a Boolean algebra, since in this situation the set of all ${\displaystyle D_x}$ is a base for a compact Hausdorff topology on ${\displaystyle G}$. Especially, when considering the ultrafilters on a powerset ${\displaystyle \mathcal{P}(S)}$, the resulting topological space is the Stone–Čech compactification of a discrete space of cardinality ${\displaystyle |S|.}$

The ultraproduct construction in model theory uses ultrafilters to produce a new model starting from a sequence of ${\displaystyle 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 hyperreal numbers 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" ${\displaystyle U}$, where ${\displaystyle 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 ${\displaystyle 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 looking at the group from infinity, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimits of metric spaces.

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. However, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.