Ultrafilter

Summary

In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") is a certain subset of namely a maximal filter on that is, a proper filter on that cannot be enlarged to a bigger proper filter on

Hasse diagram of the divisors of 210, ordered by the relation is divisor of, with the upper set ↑14 colored dark green. It is a principal filter, but not an 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.

If is an arbitrary set, its power set ordered by set inclusion, is always a Boolean algebra and hence a poset, and ultrafilters on are usually called ultrafilters on the set .[note 1] An ultrafilter on a set may be considered as a finitely additive 0-1-valued measure on . In this view, every subset of 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

edit

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   is a set, partially ordered by   then

  • a subset   is called a filter on   if
    •   is nonempty,
    • for every   there exists some element   such that   and   and
    • for every   and     implies that   is in   too;
  • a proper subset   of   is called an ultrafilter on   if
    •   is a filter on   and
    • there is no proper filter   on   that properly extends   (that is, such that   is a proper subset of  ).

Types and existence of ultrafilters

edit

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   for some element   of the given poset. In this case   is called the principal element of the ultrafilter. Any ultrafilter that is not principal is called a free (or non-principal) ultrafilter. For arbitrary  , the set   is a filter, called the principal filter at  ; it is a principal ultrafilter only if it is maximal.

For ultrafilters on a powerset   a principal ultrafilter consists of all subsets of   that contain a given element   Each ultrafilter on   that is also a principal filter is of this form.[2]: 187  Therefore, an ultrafilter   on   is principal if and only if it contains a finite set.[note 2] If   is infinite, an ultrafilter   on   is hence non-principal if and only if it contains the Fréchet filter of cofinite subsets of  [note 3][4]: Proposition 3  If   is finite, every ultrafilter is principal.[2]: 187  If   is infinite then the Fréchet filter is not an ultrafilter on the power set of   but it is an ultrafilter on the finite–cofinite algebra of  

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 that 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.[5]

Ultrafilter on a Boolean algebra

edit

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   of the Boolean algebra, exactly one of the elements   and   (the latter being the Boolean complement of  ):

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

  1.   is an ultrafilter on  
  2.   is a prime filter on  
  3. for each   either   or ( )  [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

edit

Given an arbitrary set   its power set   ordered by set inclusion, is always a Boolean algebra; hence the results of the above section apply. An (ultra)filter on   is often called just an "(ultra)filter on  ".[note 1] Given an arbitrary set   an ultrafilter on   is a set   consisting of subsets of   such that:

  1. The empty set is not an element of  .
  2. If   is an element of   then so is every superset  .
  3. If   and   are elements of   then so is the intersection  .
  4. If   is a subset of   then either[note 4]   or its complement   is an element of  .

Equivalently, a family   of subsets of   is an ultrafilter if and only if for any finite collection   of subsets of  , there is some   such that   where   is the principal ultrafilter seeded by  . 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   is a 2-valued morphism, a function   on   defined as   if   is an element of   and   otherwise. Then   is finitely additive, and hence a content on   and every property of elements of   is either true almost everywhere or false almost everywhere. However,   is usually not countably additive, and hence does not define a measure in the usual sense.

For a filter   that is not an ultrafilter, one can define   if   and   if   leaving   undefined elsewhere.[1]

Applications

edit

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   of all ultrafilters of a poset   can be topologized in a natural way, that is in fact closely related to the above-mentioned representation theorem. For any element   of  , let   This is most useful when   is again a Boolean algebra, since in this situation the set of all   is a base for a compact Hausdorff topology on  . Especially, when considering the ultrafilters on a powerset  , the resulting topological space is the Stone–Čech compactification of a discrete space of cardinality  

The ultraproduct construction in model theory uses ultrafilters to produce a new model starting from a sequence of  -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"  , where   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   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

edit
  • 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 filter
  • Universal net – A generalization of a sequence of points

Notes

edit
  1. ^ a b If   happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on   or an (ultra)filter just on   is meant; both kinds of (ultra)filters are quite different. Some authors[citation needed] use "(ultra)filter of a partial ordered set" vs. "on an arbitrary set"; i.e. they write "(ultra)filter on  " to abbreviate "(ultra)filter of  ".
  2. ^ To see the "if" direction: If   then   by the characterization Nr.7 from Ultrafilter (set theory)#Characterizations. That is, some   is the principal element of  
  3. ^   is non-principal if and only if it contains no finite set, that is, (by Nr.3 of the above characterization theorem) if and only if it contains every cofinite set, that is, every member of the Fréchet filter.
  4. ^ Properties 1 and 3 imply that   and   cannot both be elements of  

References

edit
  1. ^ a b Alex Kruckman (November 7, 2012). "Notes on Ultrafilters" (PDF). Berkeley Math Toolbox Seminar.
  2. ^ a b c d Davey, B. A.; Priestley, H. A. (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
  3. ^ Goldbring, Isaac (2021). "Ultrafilter methods in combinatorics". Snapshots of Modern Mathematics from Oberwolfach. Marta Maggioni, Sophia Jahns. doi:10.14760/SNAP-2021-006-EN.
  4. ^ "Ultrafilters and how to use them", Burak Kaya, lecture notes, Nesin Mathematics Village, Summer 2019.
  5. ^ Halbeisen, L. J. (2012). Combinatorial Set Theory. Springer Monographs in Mathematics. Springer.
  6. ^ Burris, Stanley N.; Sankappanavar, H. P. (2012). A Course in Universal Algebra (PDF). ISBN 978-0-9880552-0-9.
  7. ^ Kanamori, The Higher infinite, p. 49.
  8. ^ Kirman, A.; Sondermann, D. (1972). "Arrow's theorem, many agents, and invisible dictators". Journal of Economic Theory. 5 (2): 267–277. doi:10.1016/0022-0531(72)90106-8.
  9. ^ Mihara, H. R. (1997). "Arrow's Theorem and Turing computability" (PDF). Economic Theory. 10 (2): 257–276. CiteSeerX 10.1.1.200.520. doi:10.1007/s001990050157. S2CID 15398169Reprinted in K. V. Velupillai, S. Zambelli, and S. Kinsella, ed., Computable Economics, International Library of Critical Writings in Economics, Edward Elgar, 2011.{{cite journal}}: CS1 maint: postscript (link)
  10. ^ Mihara, H. R. (1999). "Arrow's theorem, countably many agents, and more visible invisible dictators". Journal of Mathematical Economics. 32 (3): 267–277. CiteSeerX 10.1.1.199.1970. doi:10.1016/S0304-4068(98)00061-5.

Bibliography

edit
  • 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

edit