![Filter vs ultrafilter_210div](https://upload.wikimedia.org/wikipedia/commons/6/66/Filter_vs_ultrafilter_210div.svg)
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
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, an ultrafilter on a given
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 (mathematics), set. A poset consists of a set toget ...
(or "poset")
is a certain subset of
namely 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
that is, a
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
that cannot be enlarged to a bigger proper filter on
If
is an arbitrary set, its
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 po ...
ordered by
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 ...
, is always a
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 in e ...
and hence a poset, and ultrafilters on
are usually called
.
[If happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on or an (ultra)filter just on is meant; both kinds of (ultra)filters are quite different. Some authors use "(ultra)filter" ''of'' a partial ordered set" vs. "''on'' an arbitrary set"; i.e. they write "(ultra)filter on " to abbreviate "(ultra)filter of ".] An ultrafilter on a set
may be considered as a
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 additivity ...
measure
Measure may refer to:
* Measurement, the assignment of a number to a characteristic of an object or event
Law
* Ballot measure, proposed legislation in the United States
* Church of England Measure, legislation of the Church of England
* Mea ...
on
. In this view, every subset of
is either considered "
almost everything
''Almost Everything'' is an album by American jazz pianist Don Friedman recorded in Denmark in 1995 and released on the Danish SteepleChase Records, SteepleChase label.model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
,
topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
and combinatorics.
Ultrafilters on partial orders
In
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
, an ultrafilter is a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), 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 ...
of a
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 (mathematics), set. A poset consists of a set toget ...
that is
maximal among all
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 ...
s. This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.
Formally, if
is a set, partially ordered by
then
* a subset
is called a filter on
if
**
is nonempty,
** for every
there exists some element
such that
and
and
** for every
and
implies that
is in
too;
* a
proper subset
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 ...
of
is called an ultrafilter on
if
**
is a filter on
and
** there is no proper filter
on
that properly extends
(that is, such that
is a proper subset of
).
Every ultrafilter falls into exactly one of two categories: principal or free. A principal (or fixed, or trivial) ultrafilter is a filter containing a
least element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
. Consequently, principal ultrafilters are of the form
for some (but not all) elements
of the given poset. In this case
is called the of the ultrafilter. Any ultrafilter that is not principal is called a free (or non-principal) ultrafilter.
For ultrafilters on a powerset
a principal ultrafilter consists of all subsets of
that contain a given element
Each ultrafilter on
that is also a
principal filter
In mathematics, a filter on a set X is a family \mathcal of subsets such that:
# X \in \mathcal and \emptyset \notin \mathcal
# if A\in \mathcal and B \in \mathcal, then A\cap B\in \mathcal
# If A,B\subset X,A\in \mathcal, and A\subset B, then ...
is of this form.
Therefore, an ultrafilter
on
is principal if and only if it contains a finite set.
[To see the "if" direction: If then by induction on using Nr.2 of the above characterization theorem. That is, some is the principal element of ] If
is infinite, an ultrafilter
on
is hence non-principal if and only if it contains the
Fréchet filter In mathematics, the Fréchet filter, also called the cofinite filter, on a set X is a certain collection of subsets of X (that is, it is a particular subset of the power set of X).
A subset F of X belongs to the Fréchet filter if and only if the c ...
of
cofinite subset
In mathematics, a cofinite subset of a set X is a subset A whose complement in X is a finite set. In other words, A contains all but finitely many elements of X. If the complement is not finite, but it is countable, then one says the set is coco ...
s of
[ is non-principal if and only if it contains no finite set, that is, (by Nr.3 of the above characterization theorem) if and only if it contains every cofinite set, that is, every member of the Fréchet filter.] If
is finite, every ultrafilter is principal.
If
is infinite then the
Fréchet filter In mathematics, the Fréchet filter, also called the cofinite filter, on a set X is a certain collection of subsets of X (that is, it is a particular subset of the power set of X).
A subset F of X belongs to the Fréchet filter if and only if the c ...
is not an ultrafilter on the power set of
but it is an ultrafilter on the
finite–cofinite algebra
In mathematics, a cofinite subset of a set X is a subset A whose complement in X is a finite set. In other words, A contains all but finitely many elements of X. If the complement is not finite, but it is countable, then one says the set is coco ...
of
Every filter on a Boolean algebra (or more generally, any subset with 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 ...
) is contained in an ultrafilter (see
ultrafilter lemma
In the mathematical field of set theory, an ultrafilter is a ''maximal proper filter'': it is a filter 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 \wp(X) of X (suc ...
) and that free ultrafilters therefore exist, but the proofs involve 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 collectio ...
(AC) in the form of
Zorn's lemma. On the other hand, the statement that every filter is contained in an ultrafilter does not imply AC. Indeed, it is equivalent to the
Boolean prime ideal theorem
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), a well-known intermediate point between the axioms of
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 as ...
(ZF) and the ZF theory augmented by the axiom of choice (ZFC). In general, proofs involving the axiom of choice do not produce explicit examples of free ultrafilters, though it is possible to find explicit examples in some models of ZFC; for example,
Gödel showed that this can be done in the
constructible universe
In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It w ...
where one can write down an explicit global choice function. In ZF without the axiom of choice, it is possible that every ultrafilter is principal.
Ultrafilter on a Boolean algebra
An important special case of the concept occurs if the considered poset is a
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 in e ...
. In this case, ultrafilters are characterized by containing, for each element
of the Boolean algebra, exactly one of the elements
and
(the latter being the
Boolean complement of
):
If
is a Boolean algebra and
is a proper filter on
then the following statements are equivalent:
#
is an ultrafilter on
#
is a
prime filter on
# for each
either
or (
)
A proof that 1. and 2. are equivalent is also given in (Burris, Sankappanavar, 2012, Corollary 3.13, p.133).
Moreover, ultrafilters on a Boolean algebra can be related to
maximal ideals and
homomorphisms to the 2-element Boolean algebra (also known as
2-valued morphisms) as follows:
* Given a homomorphism of a Boolean algebra onto , the
inverse image
In mathematics, the image of a function is the set of all output values it may produce.
More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through) ...
of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
* Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto taking the maximal ideal to "false".
* Given an ultrafilter on a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto taking the ultrafilter to "true".
Ultrafilter on the power set of a set
Given an arbitrary set
its
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 po ...
ordered by
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 ...
, is always a Boolean algebra; hence the results of the above section apply. An (ultra)filter on
is often called just an "(ultra)filter on
".
[ The above formal definitions can be particularized to the powerset case as follows:
Given an arbitrary set an ultrafilter on is a set consisting of subsets of such that:
#The empty set is not an element of
#If and are subsets of the set is a subset of and is an element of then is also an element of
#If and are elements of then so is the ]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, their i ...
of and
#If is a subset of then either[Properties 1 and 3 imply that and cannot be elements of ] or its relative complement is an element of
Another way of looking at ultrafilters on a power set is as follows: for a given ultrafilter define a function on by setting if is an element of and otherwise. Such a function is called a 2-valued morphism. Then 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 additivity ...
, and hence a on and every property of elements of 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, is usually not , and hence does not define a measure
Measure may refer to:
* Measurement, the assignment of a number to a characteristic of an object or event
Law
* Ballot measure, proposed legislation in the United States
* Church of England Measure, legislation of the Church of England
* Mea ...
in the usual sense.
For a filter that is not an ultrafilter, one would say if and if leaving undefined elsewhere.
Applications
Ultrafilters on 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 po ...
s are useful in topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
, especially in relation to 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 spaces, and in model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
in the construction of ultraproducts and ultrapowers. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on Boolean algebras play a central role in Stone's representation theorem
In 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 ...
.
The set of all ultrafilters of a poset can be topologized in a natural way, that is in fact closely related to the above-mentioned representation theorem. For any element of , let This is most useful when is again a Boolean algebra, since in this situation the set of all is a base for a compact Hausdorff topology on . Especially, when considering the ultrafilters on a powerset the resulting topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
is the Stone–Čech compactification In the mathematical discipline of general topology, Stone–Čech compactification (or Čech–Stone compactification) is a technique for constructing a universal map from a topological space ''X'' to a compact Hausdorff space ''βX''. The Stone ...
of a discrete space
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 to ...
of cardinality
The ultraproduct
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factors ...
construction in model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
uses ultrafilters to produce elementary extension In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences.
If ''N'' is a substructure of ''M'', one oft ...
s of structures. For example, in constructing hyperreal number
In mathematics, the system of hyperreal numbers is a way of treating infinite and infinitesimal (infinitely small but non-zero) quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers ...
s as an ultraproduct of the real numbers
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
, the domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range.
Overview
The domain ...
is extended from real numbers to sequences of real numbers. This sequence space is regarded as a superset
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 ...
of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead the functions and relations are defined " pointwise modulo" , where is an ultrafilter on the index set
In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consists ...
of the sequences; by Łoś' theorem
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factor ...
, this preserves all properties of the reals that can be stated in first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
. If is nonprincipal, then the extension thereby obtained is nontrivial.
In geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
, non-principal ultrafilters are used to define the asymptotic cone
In mathematics, an ultralimit is a geometric construction that assigns to a sequence of metric spaces ''Xn'' a limiting metric space. The notion of an ultralimit captures the limiting behavior of finite configurations in the spaces ''Xn'' and uses ...
of a group. This construction yields a rigorous way to consider , that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimit
In mathematics, an ultralimit is a geometric construction that assigns to a sequence of metric spaces ''Xn'' a limiting metric space. The notion of an ultralimit captures the limiting behavior of finite configurations in the spaces ''Xn'' and uses ...
s of 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 settin ...
s.
Gödel's ontological proof
Gödel's ontological proof is a formal argument by the mathematician Kurt Gödel (1906–1978) for the existence of God. The argument is in a line of development that goes back to Anselm of Canterbury (1033–1109). St. Anselm's ontological argum ...
of God's existence uses as an axiom that the set of all "positive properties" is an ultrafilter.
In social choice theory
Social choice theory or social choice is a theoretical framework for analysis of combining individual opinions, preferences, interests, or welfares to reach a ''collective decision'' or ''social welfare'' in some sense.Amartya Sen (2008). "Soci ...
, non-principal ultrafilters are used to define a rule (called a ''social welfare function'') for aggregating the preferences of ''infinitely'' many individuals. Contrary to Arrow's impossibility theorem
Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral syste ...
for ''finitely'' many individuals, such a rule satisfies the conditions (properties) that Arrow proposes (for example, Kirman and Sondermann, 1972). Mihara (1997, 1999) shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.
See also
*
*
*
*
*
Notes
References
Bibliography
*
*
*
*
*
*
*
*
*
*
*
Further reading
*
*
*
*{{YouTube, id=0H2rf8bluOE, title="Mathematical Logic 15, The Ultrafilter Theorem"
Order theory
Families of sets
Nonstandard analysis