principal ultrafilter
   HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, an ultrafilter is a ''maximal proper filter'': it is a
filter Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...
U on a given non-empty set X which is a certain type of non-empty family of subsets of X, that is not equal to the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\wp(X) of X (such filters are called ) and that is also "maximal" in that there does not exist any other proper filter on X that contains it as a
proper subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
. Said differently, a proper filter U is called an ultrafilter if there exists proper filter that contains it as a subset, that proper filter (necessarily) being U itself. More formally, an ultrafilter U on X is a proper filter that is also a maximal
filter Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...
on X with respect to
set inclusion In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
, meaning that there does not exist any
proper filter In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an or ...
on X that contains U as a
proper subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
. Ultrafilters on sets are an important special instance of ultrafilters on partially ordered sets, where the
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
consists of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\wp(X) and the partial order is subset inclusion \,\subseteq. Ultrafilters have many applications in set theory, model theory, and
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
.


Definitions

Given an arbitrary set X, an ultrafilter on X is a non-empty
family Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
U of subsets of X such that: # or : The empty set is not an element of U. #: If A \in U and if B \subseteq X is any superset of A (that is, if A \subseteq B \subseteq X) then B \in U. #: If A and B are elements of U then so is their intersection A \cap B. #If A \subseteq X then eitherProperties 1 and 3 imply that A and X \setminus A cannot be elements of U. A or its relative complement X \setminus A is an element of U. Properties (1), (2), and (3) are the defining properties of a Some authors do not include non-degeneracy (which is property (1) above) in their definition of "filter". However, the definition of "ultrafilter" (and also of "prefilter" and "filter subbase") always includes non-degeneracy as a defining condition. This article requires that all filters be proper although a filter might be described as "proper" for emphasis. For a filter F that is not an ultrafilter, one would say m(A) = 1 if A \in F and m(A) = 0 if X \setminus A \in F, leaving m undefined elsewhere. A filter base is a non-empty family of sets that has the
finite intersection property In general topology, a branch of mathematics, a non-empty family ''A'' of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite inters ...
(i.e. all finite intersections are non-empty). Equivalently, a filter subbase is a non-empty family of sets that is contained in (proper) filter. The smallest (relative to \subseteq) filter containing a given filter subbase is said to be generated by the filter subbase. The upward closure in X of a family of sets P is the set :P^ := \. A or is a non-empty and proper (i.e. \varnothing \not\in P) family of sets P that is downward directed, which means that if B, C \in P then there exists some A \in P such that A \subseteq B \cap C. Equivalently, a prefilter is any family of sets P whose upward closure P^ is a filter, in which case this filter is called the filter generated by P and P is said to be a filter base P^. The dual in X of a family of sets P is the set X \setminus P := \. For example, the dual of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\wp(X) is itself: X \setminus \wp(X) = \wp(X). A family of sets is a proper filter on X if and only if its dual is a proper
ideal Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considere ...
on X ("" means not equal to the power set). Interpretation as sets The elements of a proper filter F on X may be thought of as being "large sets (relative to F)" and the complements in X of a large sets can be thought of as being "small" sets (the "small sets" are exactly the elements in the
ideal Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considere ...
X \setminus F). To see why filters and ideals should respectively be associated with "large" and "small" sets (rather than vice versa), we begin by explaining why sets in an ideal should be interpreted as "small" by considering the notion of "bounded subsets" (such as in a
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
or a normed space like \R^3). The following properties should be expected of any reasonable generalization of "bounded subsets": subsets of bounded sets should be bounded, the empty set should be bounded, the union of two bounded sets should be bounded, and every point (singleton subset) should be bounded. These are the defining properties of a on X, although the term is more common, and elements of a given bornology are called . Explicitly (and equivalently), a on X is an
ideal Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring considere ...
\mathcal that covers X. Bounded sets, especially singleton and finite sets, are naturally interpreted as "small sets". Thus we are led to associate ideals with "small sets". Assuming that X is not a bounded/"small set" (that is, if X \not\in \mathcal or said differently, if \mathcal is a proper ideal) then it is reasonable to interpret complements of "small sets" as being "large sets". In other words, "large sets" are those belonging to the dual X \setminus \mathcal := \ of the ideal \mathcal. Recalling that a family of subsets of X is a proper ideal if and only if its dual is a filter on X, we are thus led to associate filters with "large sets". In general, there may be subsets of X that are large nor small (e.g. a set not in \mathcal nor its dual X \setminus \mathcal), or possibly large and small (e.g. X if \mathcal is not a proper ideal). A dual ideal is a filter (i.e. proper) if there is no set that is both large and small, or equivalently, if the \varnothing is not large. A filter is ultra if and only if subset of X is either large or else small. With this terminology, the defining properties of a filter can be restarted as: (1) any superset of a large set is large set, (2) the intersection of any two (or finitely many) large sets is large, (3) X is a large set (i.e. F \neq \varnothing), (4) the empty set is not large. Different dual ideals give different notions of "large" sets. Another way of looking at ultrafilters on a power set \wp(X) is as follows: for a given ultrafilter U define a function m on \wp(X) by setting m(A) = 1 if A is an element of U and m(A) = 0 otherwise. Such a function is called a
2-valued morphism In mathematics, a 2-valued morphism. is a homomorphism that sends a Boolean algebra ''B'' onto the two-element Boolean algebra 2 = . It is essentially the same thing as an ultrafilter on ''B'', and, in a different way, also the same things as a max ...
. Then m is
finitely additive In mathematics, an additive set function is a function mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, \mu(A \cup B) = \mu(A) + \mu(B). If this additivit ...
, and hence a on \wp(X), and every property of elements of X is either true
almost everywhere In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
or false almost everywhere. However, m is usually not , and hence does not define a measure in the usual sense.


Generalization to ultra prefilters

A family U \neq \varnothing of subsets of X is called if \varnothing \not\in U and any of the following equivalent conditions are satisfied:
  1. For every set S \subseteq X there exists some set B \in U such that B \subseteq S or B \subseteq X \setminus S (or equivalently, such that B \cap S equals B or \varnothing).
  2. For every set S \subseteq \bigcup_ B there exists some set B \in U such that B \cap S equals B or \varnothing. * Here, \bigcup_ B is defined to be the union of all sets in U. * This characterization of "U is ultra" does not depend on the set X, so mentioning the set X is optional when using the term "ultra."
  3. For set S (not necessarily even a subset of X) there exists some set B \in U such that B \cap S equals B or \varnothing. * If U satisfies this condition then so does superset V \supseteq U. In particular, a set V is ultra if and only if \varnothing \not\in V and V contains as a subset some ultra family of sets.
A filter subbase that is ultra is necessarily a prefilter.Suppose \mathcal is filter subbase that is ultra. Let C, D \in \mathcal and define S = C \cap D. Because \mathcal is ultra, there exists some B \in \mathcal such that B \cap S equals B or \varnothing. The finite intersection property implies that B \cap S \neq \varnothing so necessarily B \cap S = B, which is equivalent to B \subseteq C \cap D. \blacksquare The ultra property can now be used to define both ultrafilters and ultra prefilters: :An is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra. :An on X is a (proper) filter on X that is ultra. Equivalently, it is any filter on X that is generated by an ultra prefilter. Ultra prefilters as maximal prefilters To characterize ultra prefilters in terms of "maximality," the following relation is needed. :Given two families of sets M and N, the family M is said to be coarser than N, and N is finer than and subordinate to M, written M \leq N or , if for every C \in M, there is some F \in N such that F \subseteq C. The families M and N are called equivalent if M \leq N and N \leq M. The families M and N are comparable if one of these sets is finer than the other. The subordination relationship, i.e. \,\geq,\, is a preorder so the above definition of "equivalent" does form an equivalence relation. If M \subseteq N then M \leq N but the converse does not hold in general. However, if N is upward closed, such as a filter, then M \leq N if and only if M \subseteq N. Every prefilter is equivalent to the filter that it generates. This shows that it is possible for filters to be equivalent to sets that are not filters. If two families of sets M and N are equivalent then either both M and N are ultra (resp. prefilters, filter subbases) or otherwise neither one of them is ultra (resp. a prefilter, a filter subbase). In particular, if a filter subbase is not also a prefilter, then it is equivalent to the filter or prefilter that it generates. If M and N are both filters on X then M and N are equivalent if and only if M = N. If a proper filter (resp. ultrafilter) is equivalent to a family of sets M then M is necessarily a prefilter (resp. ultra prefilter). Using the following characterization, it is possible to define prefilters (resp. ultra prefilters) using only the concept of filters (resp. ultrafilters) and subordination: :An arbitrary family of sets is a prefilter if and only it is equivalent to a (proper) filter. :An arbitrary family of sets is an ultra prefilter if and only it is equivalent to an ultrafilter. :A on X is a prefilter U \subseteq \wp(X) that satisfies any of the following equivalent conditions:
  1. U is ultra.
  2. U is maximal on \operatorname(X) with respect to \,\leq, meaning that if P \in \operatorname(X) satisfies U \leq P then P \leq U.
  3. There is no prefilter properly subordinate to U.
  4. If a (proper) filter F on X satisfies U \leq F then F \leq U.
  5. The filter on X generated by U is ultra.


Characterizations

There are no ultrafilters on the empty set, so it is henceforth assumed that X is nonempty. A filter base U on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:
  1. for any S \subseteq X, either S \in U or X \setminus S \in U.
  2. U is a maximal filter subbase on X, meaning that if F is any filter subbase on X then U \subseteq F implies U = F.
A (proper) filter U on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:
  1. U is ultra;
  2. U is generated by an ultra prefilter;
  3. For any subset S \subseteq X, S \in U or X \setminus S \in U. * So an ultrafilter U decides for every S \subseteq X whether S is "large" (i.e. S \in U) or "small" (i.e. X \setminus S \in U).
  4. For each subset A \subseteq X, either A is in U or (X \setminus A) is.
  5. U \cup (X \setminus U) = \wp(X). This condition can be restated as: \wp(X) is partitioned by U and its dual X \setminus U. * The sets P and X \setminus P are disjoint for all prefilters P on X.
  6. \wp(X) \setminus U = \left\ is an ideal on X.
  7. For any finite family S_1, \ldots, S_n of subsets of X (where n \geq 1), if S_1 \cup \cdots \cup S_n \in U then S_i \in U for some index i. * In words, a "large" set cannot be a finite union of sets that aren't large.
  8. For any R, S \subseteq X, if R \cup S = X then R \in U or S \in U.
  9. For any R, S \subseteq X, if R \cup S \in U then R \in U or S \in U (a filter with this property is called a ).
  10. For any R, S \subseteq X, if R \cup S \in U and R \cap S = \varnothing then R \in U or S \in U.
  11. U is a maximal filter; that is, if F is a filter on X such that U \subseteq F then U = F. Equivalently, U is a maximal filter if there is no filter F on X that contains U as a
    proper subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
    (that is, no filter is strictly finer than U).


Grills and Filter-Grills

If \mathcal \subseteq \wp(X) then its is the family \mathcal^ := \ where \mathcal^ may be written if X is clear from context. For example, \varnothing^ = \wp(X) and if \varnothing \in \mathcal then \mathcal^ = \varnothing. If \mathcal \subseteq \mathcal then \mathcal^ \subseteq \mathcal^ and moreover, if \mathcal is a filter subbase then \mathcal \subseteq \mathcal^. The grill \mathcal^ is upward closed in X if and only if \varnothing \not\in \mathcal, which will henceforth be assumed. Moreover, \mathcal^ = \mathcal^ so that \mathcal is upward closed in X if and only if \mathcal^ = \mathcal. The grill of a filter on X is called a For any \varnothing \neq \mathcal \subseteq \wp(X), \mathcal is a filter-grill on X if and only if (1) \mathcal is upward closed in X and (2) for all sets R and S, if R \cup S \in \mathcal then R \in \mathcal or S \in \mathcal. The grill operation \mathcal \mapsto \mathcal^ induces a bijection :^ ~:~ \operatorname(X) \to \operatorname(X) whose inverse is also given by \mathcal \mapsto \mathcal^. If \mathcal \in \operatorname(X) then \mathcal is a filter-grill on X if and only if \mathcal = \mathcal^, or equivalently, if and only if \mathcal is an ultrafilter on X. That is, a filter on X is a filter-grill if and only if it is ultra. For any non-empty \mathcal \subseteq \wp(X), \mathcal is both a filter on X and a filter-grill on X if and only if (1) \varnothing \not\in \mathcal and (2) for all R, S \subseteq X, the following equivalences hold: :R \cup S \in \mathcal if and only if R, S \in \mathcal if and only if R \cap S \in \mathcal.


Free or principal

If P is any non-empty family of sets then the
Kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learn ...
of P is the intersection of all sets in P: \operatorname P := \bigcap_ B. A non-empty family of sets P is called: * if \operatorname P = \varnothing and otherwise (that is, if \operatorname P \neq \varnothing). * if \operatorname P \in P. * if \operatorname P \in P and \operatorname P is a singleton set; in this case, if \operatorname P = \ then P is said to be principal at x. If a family of sets P is fixed then P is ultra if and only if some element of P is a singleton set, in which case P will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter P is ultra if and only if \operatorname P is a singleton set. A singleton set is ultra if and only if its sole element is also a singleton set. Every filter on X that is principal at a single point is an ultrafilter, and if in addition X is finite, then there are no ultrafilters on X other than these. If there exists a free ultrafilter (or even filter subbase) on a set X then X must be infinite. The next theorem shows that every ultrafilter falls into one of two categories: either it is free or else it is a principal filter generated by a single point.


Examples, properties, and sufficient conditions

If U and S are families of sets such that U is ultra, \varnothing \not\in S, and U \leq S, then S is necessarily ultra. A filter subbase U that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by U to be ultra. Suppose U \subseteq \wp(X) is ultra and Y is a set. The trace U \cap Y := \ is ultra if and only if it does not contain the empty set. Furthermore, at least one of the sets \cap Y\setminus \ and \cap (X \setminus Y)\setminus \ will be ultra (this result extends to any finite partition of X). If F_1, \ldots, F_n are filters on X, U is an ultrafilter on X, and F_1 \cap \cdots \cap F_n \leq U, then there is some F_i that satisfies F_i \leq U. This result is not necessarily true for an infinite family of filters. The image under a map f : X \to Y of an ultra set U \subseteq \wp(X) is again ultra and if U is an ultra prefilter then so is f(U). The property of being ultra is preserved under bijections. However, the preimage of an ultrafilter is not necessarily ultra, not even if the map is surjective. For example, if X has more than one point and if the range of f : X \to Y consists of a single point \ then \ is an ultra prefilter on Y but its preimage is not ultra. Alternatively, if U is a principal filter generated by a point in Y \setminus f(X)then the preimage of U contains the empty set and so is not ultra. The elementary filter induced by an infinite sequence, all of whose points are distinct, is an ultrafilter. If n = 2, then U_n denotes the set consisting all subsets of X having cardinality n, and if Xcontains at least 2 n - 1 (=3) distinct points, then U_n is ultra but it is not contained in any prefilter. This example generalizes to any integer n > 1 and also to n = 1 if X contains more than one element. Ultra sets that are not also prefilters are rarely used. For every S \subseteq X \times X and every a \in X, let S\big\vert_ := \left\. If \mathcal is an ultrafilter on X then the set of all S \subseteq X \times X such that \left\ \in \mathcal is an ultrafilter on X \times X.


Monad structure

The
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
associating to any set X the set of U(X) of all ultrafilters on X forms a
monad Monad may refer to: Philosophy * Monad (philosophy), a term meaning "unit" **Monism, the concept of "one essence" in the metaphysical and theological theory ** Monad (Gnosticism), the most primal aspect of God in Gnosticism * ''Great Monad'', a ...
called the ultrafilter monad. The unit map :X \to U(X) sends any element x \in X to the principal ultrafilter given by x. This monad admits a conceptual explanation as the codensity monad of the inclusion of the category of finite sets into the category of all sets.


The ultrafilter lemma

The ultrafilter lemma was first proved by
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
in 1930. The ultrafilter lemma is equivalent to each of the following statements: # For every prefilter on a set X, there exists a maximal prefilter on X subordinate to it. # Every proper filter subbase on a set X is contained in some ultrafilter on X. A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.Let \mathcal be a filter on X that is not an ultrafilter. If S \subseteq X is such that S \not\in \mathcal then \ \cup \mathcal has the finite intersection property (because if F \in \mathcal then F \cap (X \setminus S) = \varnothing if and only if F \subseteq S) so that by the ultrafilter lemma, there exists some ultrafilter \mathcal_S on X such that \ \cup \mathcal \subseteq \mathcal_S (so in particular S \not\in \mathcal_S). It follows that \mathcal = \bigcap_ \mathcal_S. \blacksquare The following results can be proven using the ultrafilter lemma. A free ultrafilter exists on a set X if and only if X is infinite. Every proper filter is equal to the intersection of all ultrafilters containing it. Since there are filters that are not ultra, this shows that the intersection of a family of ultrafilters need not be ultra. A family of sets \mathbb \neq \varnothing can be extended to a free ultrafilter if and only if the intersection of any finite family of elements of \mathbb is infinite.


Relationships to other statements under ZF

Throughout this section, ZF refers to
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such ...
and ZFC refers to ZF with the Axiom of Choice (AC). The ultrafilter lemma is independent of ZF. That is, there exist models in which the axioms of ZF hold but the ultrafilter lemma does not. There also exist models of ZF in which every ultrafilter is necessarily principal. Every filter that contains a singleton set is necessarily an ultrafilter and given x \in X, the definition of the discrete ultrafilter \ does not require more than ZF. If X is finite then every ultrafilter is a discrete filter at a point; consequently, free ultrafilters can only exist on infinite sets. In particular, if X is finite then the ultrafilter lemma can be proven from the axioms ZF. The existence of free ultrafilter on infinite sets can be proven if the axiom of choice is assumed. More generally, the ultrafilter lemma can be proven by using the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
, which in brief states that any Cartesian product of non-empty sets is non-empty. Under ZF, the axiom of choice is, in particular,
equivalent Equivalence or Equivalent may refer to: Arts and entertainment *Album-equivalent unit, a measurement unit in the music industry * Equivalence class (music) *'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre *''Equiva ...
to (a) Zorn's lemma, (b)
Tychonoff's theorem In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is trans ...
, (c) the weak form of the vector basis theorem (which states that every vector space has a
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
), (d) the strong form of the vector basis theorem, and other statements. However, the ultrafilter lemma is strictly weaker than the axiom of choice. While free ultrafilters can be proven to exist, it is possible to construct an explicit example of a free ultrafilter; that is, free ultrafilters are intangible.
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
proved that under ZFC, the cardinality of the set of all free ultrafilters on an infinite set X is equal to the cardinality of \wp(\wp(X)), where \wp(X) denotes the power set of X. Other authors attribute this discovery to Bedřich Pospíšil (following a combinatorial argument from Fichtenholz, and Kantorovitch, improved by Hausdorff). Under ZF, the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
can be used to prove both the ultrafilter lemma and the
Krein–Milman theorem In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs). This theorem generalizes to infinite-dimensional spaces and to arbitrar ...
; conversely, under ZF, the ultrafilter lemma together with the Krein–Milman theorem can prove the axiom of choice.


Statements that cannot be deduced

The ultrafilter lemma is a relatively weak axiom. For example, each of the statements in the following list can be deduced from ZF together with the ultrafilter lemma:
  1. A countable union of countable sets is a countable set.
  2. The
    axiom of countable choice The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function ''A'' with domain N (where ...
    (ACC).
  3. The axiom of dependent choice (ADC).


Equivalent statements

Under ZF, the ultrafilter lemma is equivalent to each of the following statements:
  1. The
    Boolean prime ideal theorem 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 consi ...
    (BPIT). * This equivalence is provable in ZF set theory without the Axiom of Choice (AC).
  2. Stone's representation theorem for Boolean algebras.
  3. Any product of
    Boolean space 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 h ...
    s is a Boolean space.
  4. Boolean Prime Ideal Existence Theorem: Every nondegenerate
    Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
    has a prime ideal.
  5. Tychonoff's theorem In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is trans ...
    for
    Hausdorff space In topology and related branches of mathematics, a Hausdorff space ( , ), separated space or T2 space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the m ...
    s: Any
    product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...
    of
    compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
    Hausdorff space In topology and related branches of mathematics, a Hausdorff space ( , ), separated space or T2 space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the m ...
    s is compact.
  6. If \ is endowed with the
    discrete topology In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest top ...
    then for any set I, the
    product space In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemi ...
    \^I is
    compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
    .
  7. Each of the following versions of the Banach-Alaoglu theorem is equivalent to the ultrafilter lemma:
    1. Any
      equicontinuous In mathematical analysis, a family of functions is equicontinuous if all the functions are continuous and they have equal variation over a given neighbourhood, in a precise sense described herein. In particular, the concept applies to countable fa ...
      set of scalar-valued maps on a
      topological vector space In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is als ...
      (TVS) is relatively compact in the
      weak-* topology In mathematics, weak topology is an alternative term for certain initial topologies, often on topological vector spaces or spaces of linear operators, for instance on a Hilbert space. The term is most commonly used for the initial topology of a ...
      (that is, it is contained in some weak-* compact set).
    2. The polar of any neighborhood of the origin in a TVS X is a weak-* compact subset of its
      continuous dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by const ...
      .
    3. The closed unit ball in the
      continuous dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by const ...
      of any normed space is weak-* compact. * If the normed space is separable then the ultrafilter lemma is sufficient but not necessary to prove this statement.
  8. A topological space X is compact if every ultrafilter on X converges to some limit.
  9. A topological space X is compact if every ultrafilter on X converges to some limit. * The addition of the words "and only if" is the only difference between this statement and the one immediately above it.
  10. The Ultranet lemma: Every
    net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
    has a universal subnet. * By definition, a
    net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
    in X is called an or an if for every subset S \subseteq X, the net is eventually in S or in X \setminus S.
  11. A topological space X is compact if and only if every ultranet on X converges to some limit. * If the words "and only if" are removed then the resulting statement remains equivalent to the ultrafilter lemma.
  12. A
    convergence space In mathematics, a convergence space, also called a generalized convergence, is a set together with a relation called a that satisfies certain properties relating elements of ''X'' with the family of filters on ''X''. Convergence spaces generaliz ...
    X is compact if every ultrafilter on X converges.
  13. A
    uniform space In the mathematical field of topology, a uniform space is a set with a uniform structure. Uniform spaces are topological spaces with additional structure that is used to define uniform properties such as completeness, uniform continuity and unifo ...
    is compact if it is complete and
    totally bounded In topology and related branches of mathematics, total-boundedness is a generalization of compactness for circumstances in which a set is not necessarily closed. A totally bounded set can be covered by finitely many subsets of every fixed “size†...
    .
  14. The Stone–Čech compactification Theorem.
  15. Each of the following versions of the
    compactness theorem In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generally ...
    is equivalent to the ultrafilter lemma:
    1. If \Sigma is a set of
      first-order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
      sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the '' sententiae'' ...
      such that every finite subset of \Sigma has a
      model A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
      , then \Sigma has a model.
    2. If \Sigma is a set of zero-order sentences such that every finite subset of \Sigma has a model, then \Sigma has a model.
  16. The
    completeness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...
    : If \Sigma is a set of zero-order sentences that is syntactically consistent, then it has a model (that is, it is semantically consistent).


Weaker statements

Any statement that can be deduced from the ultrafilter lemma (together with ZF) is said to be than the ultrafilter lemma. A weaker statement is said to be if under ZF, it is not equivalent to the ultrafilter lemma. Under ZF, the ultrafilter lemma implies each of the following statements:
  1. The Axiom of Choice for Finite sets (ACF): Given I \neq \varnothing and a family \left(X_i\right)_ of non-empty sets, their product \prod_ X_i is not empty.
  2. A
    countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
    union of finite sets is a countable set. * However, ZF with the ultrafilter lemma is too weak to prove that a countable union of sets is a countable set.
  3. The
    Hahn–Banach theorem The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear f ...
    . * In ZF, the Hahn–Banach theorem is strictly weaker than the ultrafilter lemma.
  4. The
    Banach–Tarski paradox The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be p ...
    . * In fact, under ZF, the Banach–Tarski paradox can be deduced from the
    Hahn–Banach theorem The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear f ...
    , which is strictly weaker than the Ultrafilter Lemma.
  5. Every set can be
    linearly ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
    .
  6. Every
    field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass ...
    has a unique
    algebraic closure In mathematics, particularly abstract algebra, an algebraic closure of a field ''K'' is an algebraic extension of ''K'' that is algebraically closed. It is one of many closures in mathematics. Using Zorn's lemmaMcCarthy (1991) p.21Kaplansky ( ...
    .
  7. The Alexander subbase theorem.
  8. Non-trivial ultraproducts exist.
  9. The weak ultrafilter theorem: A free ultrafilter exists on \N. * Under ZF, the weak ultrafilter theorem does not imply the ultrafilter lemma; that is, it is strictly weaker than the ultrafilter lemma.
  10. There exists a free ultrafilter on every infinite set; * This statement is actually strictly weaker than the ultrafilter lemma. * ZF alone does not even imply that there exists a non-principal ultrafilter on set.


Completeness

The completeness of an ultrafilter U on a powerset is the smallest cardinal κ such that there are κ elements of U whose intersection is not in U. The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least \aleph_0. An ultrafilter whose completeness is than \aleph_0—that is, the intersection of any countable collection of elements of U is still in U—is called countably complete or σ-complete. The completeness of a countably complete nonprincipal ultrafilter on a powerset is always a
measurable cardinal In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivisi ...
.


The (named after

Mary Ellen Rudin Mary Ellen Rudin (December 7, 1924 – March 18, 2013) was an American mathematician known for her work in set-theoretic topology. In 2013, Elsevier established the Mary Ellen Rudin Young Researcher Award, which is awarded annually to a young res ...
and
Howard Jerome Keisler Howard Jerome Keisler (born 3 December 1936) is an American mathematician, currently professor emeritus at University of Wisconsin–Madison. His research has included model theory and non-standard analysis. His Ph.D. advisor was Alfred Tarski a ...
) is a preorder on the class of powerset ultrafilters defined as follows: if U is an ultrafilter on \wp(X), and V an ultrafilter on \wp(Y), then V \leq _ U if there exists a function f : X \to Y such that :C \in V if and only if f^ \in U for every subset C \subseteq Y. Ultrafilters U and V are called , denoted , if there exist sets A \in U and B \in V and a bijection f : A \to B that satisfies the condition above. (If X and Y have the same cardinality, the definition can be simplified by fixing A = X, B = Y.) It is known that ≡RK is the
kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learn ...
of ≤RK, i.e., that if and only if U \leq _ V and V \leq _ U.


Ultrafilters on ℘(ω)

There are several special properties that an ultrafilter on \wp(\omega), where \omega extends the natural numbers, may possess, which prove useful in various areas of set theory and topology. * A non-principal ultrafilter U is called a P-point (or ) if for every
partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
\left\ of \omega such that for all n < \omega, C_n \not\in U, there exists some A \in U such that A \cap C_n is a finite set for each n. * A non-principal ultrafilter U is called Ramsey (or selective) if for every partition \left\ of \omega such that for all n < \omega, C_n \not\in U, there exists some A \in U such that A \cap C_n is a
singleton set In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the ...
for each n. It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin proved that the continuum hypothesis implies the existence of Ramsey ultrafilters. In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom. Saharon Shelah later showed that it is consistent that there are no P-point ultrafilters. Therefore, the existence of these types of ultrafilters is Independence (mathematical logic), independent of ZFC. P-points are called as such because they are topological P-points in the usual topology of the space Stone–Čech compactification, of non-principal ultrafilters. The name Ramsey comes from Ramsey's theorem. To see why, one can prove that an ultrafilter is Ramsey if and only if for every 2-coloring of [\omega]^2 there exists an element of the ultrafilter that has a homogeneous color. An ultrafilter on \wp(\omega) is Ramsey if and only if it is Minimal element, minimal in the Rudin–Keisler ordering of non-principal powerset ultrafilters.


See also

* * *


Notes

Proofs


References


Bibliography

* * * * * * * * * * *


Further reading

* * * {{Mathematical logic Families of sets Nonstandard analysis Order theory