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 concern ...
, an ultrafilter is a ''maximal proper filter'': it is a filter U on a given non-empty
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 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 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 binary ...
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 In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (math ...
, 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 In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
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 (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 considered ...
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 considered ...
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 setti ...
or a
normed space In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length ...
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 considered ...
\mathcal that
cover Cover or covers may refer to: Packaging * Another name for a lid * Cover (philately), generic term for envelope or package * Album cover, the front of the packaging * Book cover or magazine cover ** Book design ** Back cover copy, part of copy ...
s 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. Then m is finitely additive, 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 In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
so the above definition of "equivalent" does form an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
. 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 In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
, 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 In the mathematical field of category theory, FinSet is the category whose objects are all finite sets and whose morphisms are all functions between them. FinOrd is the category whose objects are all finite ordinal numbers and whose morphisms are a ...
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 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 ...
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 In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
of non-empty sets is non-empty. Under ZF, the axiom of choice is, in particular, equivalent to (a) Zorn's lemma, (b) Tychonoff's theorem, (c) the weak form of the vector basis theorem (which states that every vector space has a basis), (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 set 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 numb ...
    s is a countable set.
  2. The axiom of countable choice (ACC).
  3. The
    axiom of dependent choice In mathematics, the axiom of dependent choice, denoted by \mathsf , is a weak form of the axiom of choice ( \mathsf ) that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that explores wh ...
    (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 cons ...
    (BPIT). * This equivalence is provable in ZF set theory without the Axiom of Choice (AC).
  2. Stone's representation theorem for Boolean algebras 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 hal ...
    .
  3. Any product of Boolean spaces 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 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 ma ...
    s: Any product 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 Britis ...
    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 ma ...
    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 \^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 Britis ...
    .
  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 Polar may refer to: Geography Polar may refer to: * Geographical pole, either of two fixed points on the surface of a rotating body or planet, at 90 degrees from the equator, based on the axis around which a body rotates *Polar climate, the cli ...
      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 In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length ...
      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 has a universal subnet. * By definition, a net 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 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 t ...
    and totally bounded.
  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 hig ...
      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, 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: 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.
  6. Every field has a unique algebraic closure.
  7. The
    Alexander subbase theorem In topology, a subbase (or subbasis, prebase, prebasis) for a topological space X with topology T is a subcollection B of T that generates T, in the sense that T is the smallest topology containing B. A slightly different definition is used by so ...
    .
  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 Cardinal or The Cardinal may refer to: Animals * Cardinal (bird) or Cardinalidae, a family of North and South American birds **'' Cardinalis'', genus of cardinal in the family Cardinalidae **'' Cardinalis cardinalis'', or northern cardinal, t ...
κ 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 and Howard Jerome Keisler) is a

preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cas ...
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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
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 \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 In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that or equivalently, that In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
implies the existence of Ramsey ultrafilters. In fact, many hypotheses imply the existence of Ramsey ultrafilters, including
Martin's axiom In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consis ...
.
Saharon Shelah Saharon Shelah ( he, שהרן שלח; born July 3, 1945) is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey. Biography Shelah was born in Jerusalem on July 3, ...
later showed that it is consistent that there are no P-point ultrafilters. Therefore, the existence of these types of ultrafilters is
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independe ...
of ZFC. P-points are called as such because they are topological P-points in the usual topology of the space 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 Omega (; capital: Ω, lowercase: ω; Ancient Greek ὦ, later ὦ μέγα, Modern Greek ωμέγα) is the twenty-fourth and final letter in the Greek alphabet. In the Greek numeric system/ isopsephy ( gematria), it has a value of 800. The ...
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 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