Ultrafilter

In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") ${\textstyle P}$ is a certain subset of ${\displaystyle P,}$ namely a maximal filter on ${\displaystyle P;}$ that is, a proper filter on ${\textstyle P}$ that cannot be enlarged to a bigger proper filter on ${\displaystyle P.}$

Contents

• Ultrafilters on partial orders
• Types and existence of ultrafilters
• Ultrafilter on a Boolean algebra
• Ultrafilter on the power set of a set
• Applications
• See also
• Notes
• References
• Bibliography
• Further reading

If ${\displaystyle X}$ is an arbitrary set, its power set ${\displaystyle {\mathcal {P}}(X),}$ ordered by set inclusion, is always a Boolean algebra and hence a poset, and ultrafilters on ${\displaystyle {\mathcal {P}}(X)}$ are usually called ultrafilters on the set ${\displaystyle X}$. ^{[note 1]} An ultrafilter on a set ${\displaystyle X}$ may be considered as a finitely additive 0-1-valued measure on ${\displaystyle {\mathcal {P}}(X)}$. In this view, every subset of ${\displaystyle 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. ^{[1] : §4}

Ultrafilters have many applications in set theory, model theory, topology ^{[2] : 186} and combinatorics. ^[3]

Ultrafilters on partial orders

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

Formally, if ${\textstyle P}$ is a set, partially ordered by ${\displaystyle \,\leq \,}$ then

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

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 \lnot x}$ (the latter being the Boolean complement of ${\displaystyle x}$):

If ${\textstyle 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 \lnot x}$) ${\displaystyle \in F.}$ ^{[2] : 186}

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

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".^{[ citation needed ]}

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}$". ^{[note 1]} 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 ^{[note 4]} ${\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.^{[ citation needed ]}

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. ^[1]

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. ^[7]

The set ${\displaystyle G}$ of all ultrafilters of a poset ${\textstyle 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 ${\textstyle P}$, let ${\displaystyle D_{x}=\left\{U\in G:x\in U\right\}.}$ This is most useful when ${\textstyle 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 (for example, Kirman and Sondermann, 1972). ^[8] Mihara (1997, ^[9] 1999) ^[10] shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.

See also

• Filter (mathematics)  – In mathematics, a special subset of a partially ordered set
• Filter (set theory)  – Family of sets representing "large" sets
• Filters in topology  – Use of filters to describe and characterize all basic topological notions and results.
• The ultrafilter lemma  – Maximal proper filterPages displaying short descriptions of redirect targets
• Universal net  – A generalization of a sequence of pointsPages displaying short descriptions of redirect targets

Notes

Related Research Articles

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

In mathematics, a filter or order filter is a special subset of a partially ordered set (poset), describing "large" or "eventual" elements. Filters appear in order and lattice theory, but also topology, whence they originate. The notion dual to a filter is an order ideal.

In commutative algebra, the prime spectrum of a commutative ring R is the set of all prime ideals of R, and is usually denoted by ; in algebraic geometry it is simultaneously a topological space equipped with the sheaf of rings .

In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX. The Stone–Čech compactification βX of a topological space X is the largest, most general compact Hausdorff space "generated" by X, in the sense that any continuous map from X to a compact Hausdorff space factors through βX. If X is a Tychonoff space then the map from X to its image in βX is a homeomorphism, so X can be thought of as a (dense) subspace of βX; every other compact Hausdorff space that densely contains X is a quotient of βX. For general topological spaces X, the map from X to βX need not be injective.

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature. The ultrapower is the special case of this construction in which all factors are equal.

In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings and prime ideals, or distributive lattices and maximal ideals. This article focuses on prime ideal theorems from order theory.

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In general topology, a branch of mathematics, a non-empty family A of subsets of a set is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of is non-empty. It has the strong finite intersection property (SFIP) if the intersection over any finite subcollection of is infinite. Sets with the finite intersection property are also called centered systems and filter subbases.

In mathematics, a cofinite subset of a set is a subset whose complement in is a finite set. In other words, contains all but finitely many elements of If the complement is not finite, but is countable, then one says the set is cocountable.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.

In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Marshall H. Stone. Stone was led to it by his study of the spectral theory of operators on a Hilbert space.

In mathematics, a field of sets is a mathematical structure consisting of a pair consisting of a set and a family of subsets of called an algebra over that contains the empty set as an element, and is closed under the operations of taking complements in finite unions, and finite intersections.

In mathematics, the Fréchet filter, also called the cofinite filter, on a set is a certain collection of subsets of . A subset of belongs to the Fréchet filter if and only if the complement of in is finite. Any such set is said to be cofinite in , which is why it is alternatively called the cofinite filter on .

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean algebra.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In mathematics, a filter on a set is a family of subsets such that:

1. and
2. if and , then
3. If and , then

This is a glossary of set theory.

Filters in topology, a subfield of mathematics, can be used to study topological spaces and define all basic topological notions such as convergence, continuity, compactness, and more. Filters, which are special families of subsets of some given set, also provide a common framework for defining various types of limits of functions such as limits from the left/right, to infinity, to a point or a set, and many others. Special types of filters called ultrafilters have many useful technical properties and they may often be used in place of arbitrary filters.

In the mathematical field of set theory, an ultrafilter on a set is a maximal filter on the set In other words, it is a collection of subsets of that satisfies the definition of a filter on and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of that is also a filter. Equivalently, an ultrafilter on the set can also be characterized as a filter on with the property that for every subset of either or its complement belongs to the ultrafilter.

References

Bibliography

• Arkhangel'skii, Alexander Vladimirovich; Ponomarev, V.I. (1984). Fundamentals of General Topology: Problems and Exercises. Mathematics and Its Applications. Vol. 13. Dordrecht Boston: D. Reidel. ISBN   978-90-277-1355-1. OCLC   9944489.
• Bourbaki, Nicolas (1989) [1966]. General Topology: Chapters 1–4 [ Topologie Générale ]. Éléments de mathématique. Berlin New York: Springer Science & Business Media. ISBN   978-3-540-64241-1. OCLC   18588129.
• Dixmier, Jacques (1984). General Topology. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York: Springer-Verlag. ISBN   978-0-387-90972-1. OCLC   10277303.
• Dolecki, Szymon; Mynard, Frederic (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN   978-981-4571-52-4. OCLC   945169917.
• Dugundji, James (1966). Topology. Boston: Allyn and Bacon. ISBN   978-0-697-06889-7. OCLC   395340485.
• Császár, Ákos (1978). General topology. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd. ISBN   0-85274-275-4. OCLC   4146011.
• Jech, Thomas (2006). Set Theory: The Third Millennium Edition, Revised and Expanded. Berlin New York: Springer Science & Business Media. ISBN   978-3-540-44085-7. OCLC   50422939.
• Joshi, K. D. (1983). Introduction to General Topology. New York: John Wiley and Sons Ltd. ISBN   978-0-85226-444-7. OCLC   9218750.
• Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN   978-1584888666. OCLC   144216834.
• Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN   978-0-12-622760-4. OCLC   175294365.
• Schubert, Horst (1968). Topology. London: Macdonald & Co. ISBN   978-0-356-02077-8. OCLC   463753.

Further reading

• Comfort, W. W. (1977). "Ultrafilters: some old and some new results". Bulletin of the American Mathematical Society . 83 (4): 417–455. doi: 10.1090/S0002-9904-1977-14316-4 . ISSN   0002-9904. MR   0454893.
• Comfort, W. W.; Negrepontis, S. (1974), The theory of ultrafilters, Berlin, New York: Springer-Verlag, MR   0396267
• Ultrafilter at the nLab
• "Mathematical Logic 15, The Ultrafilter Theorem" on YouTube