Ultrafilter

In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, an ultrafilter on a set X is a collection of subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of X that is a filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

, that cannot be enlarged (as a filter). An ultrafilter may be considered as a finitely additive measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

. Then every subset of X is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0). If A is a subset of X, then either A or X \ A is an element of the ultrafilter (here X \ A is the relative complement

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 of A in X; that is, the set of all elements of X that are not in A). The concept can be generalized to Boolean algebras or even to general partial orders, and has many applications in set theory, model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, and topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

.

Formal definition

Given a set X, an ultrafilter on X is a set U consisting of subsets of X such that

1. The empty set is not an element of U
2. If A and B are subsets of X, A is a subset of B, and A is an element of U, then B is also an element of U.
3. If A and B are elements of U, then so is the intersection
   Intersection (set theory)
   In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
   
    of A and B.
4. If A is a subset of X, then either A or X \ A is an element of U. (Note: axioms 1 and 3 imply that A and X \ A cannot both be elements of U.)

A characterization is given by the following theorem.
A filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

 U on a set X is an ultrafilter if any of the following conditions are true:

1. There is no filter F finer than U, i.e. implies U = F.
2. implies or .
3. or .

Another way of looking at ultrafilters on a set X is to define a function m on the power set of X by setting m(A) = 1 if A is an element of U and m(A) = 0 otherwise. Then m is a finitely additive measure on X, and every property of elements of X is either true almost everywhere

Almost everywhere

In measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...

 or false almost everywhere. Note that this does not define a measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

 in the usual sense, which is required to be countably additive.

For a filter F which is not an ultrafilter, one would say m(A) = 1 if A ∈ F and m(A) = 0 if X \ A ∈ F, leaving m undefined elsewhere.

Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the Fréchet filter

Fréchet filter

In mathematics, Fréchet filter is an important concept in order theory.If X is an infinite set, the Fréchet filter,also called cofinite filter on X, is the set of all subsets of X having finite complement in X....

 of cofinite subsets of S. This is obvious, since a non-principal ultrafilter contains no finite set, and is closed under complement, which means that it contains all cofinite subsets of S, which is exactly the Fréchet filter.

Completeness

The completeness of an ultrafilter U on a set is the smallest cardinal κ such that there are κ elements of U whose intersection is not in U. The definition implies that the completeness of any ultrafilter is at least . An ultrafilter whose completeness is greater than —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 set is always a measurable cardinal

Measurable cardinal

- Measurable :Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of κ...

.

Generalization to partial orders

In order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, an ultrafilter is a subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of a partially ordered set

Partially ordered set

In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...

 (a poset) which is maximal

Maximal element

In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...

 among all proper filters. Formally, this states that any filter that properly contains an ultrafilter has to be equal to the whole poset. An important special case of the concept occurs if the considered poset is a Boolean algebra, as in the case of an ultrafilter on a set (defined as a filter of the corresponding powerset). In this case, ultrafilters are characterized by containing, for each element a of the Boolean algebra, exactly one of the elements a and ¬a (the latter being the Boolean complement of a).

Ultrafilters on a Boolean algebra can be identified with prime ideal

Prime ideal

In algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...

s, maximal ideal

Maximal ideal

In mathematics, more specifically in ring theory, a maximal ideal is an ideal which is maximal amongst all proper ideals. In other words, I is a maximal ideal of a ring R if I is an ideal of R, I ≠ R, and whenever J is another ideal containing I as a subset, then either J = I or J = R...

s, and homomorphisms to
the 2-element Boolean algebra {true, false}, as follows:

• Maximal ideals of a Boolean algebra are the same as prime ideals.
• Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
• Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
• Given an ultrafilter of a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".

Let us see another theorem which could be used for the definition of the concept of “ultrafilter”. Let B denote a Boolean algebra and F a proper filter in it. F is an ultrafilter iff:

for all , if , then or

(To avoid confusion: the sign denotes the join operation of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in.

Types and existence of ultrafilters

There are two very different types of ultrafilter: principal and free. A principal (or fixed, or trivial) ultrafilter is a filter containing a least element. Consequently, principal ultrafilters are of the form F_a = {x | a ≤ x} for some (but not all) elements a of the given poset. In this case a is called the principal element of the ultrafilter. For the case of filters on sets, the elements that qualify as principals are exactly the one-element sets. Thus, a principal ultrafilter on a set S consists of all sets containing a particular point of S. An ultrafilter on a finite set is principal. Any ultrafilter which is not principal is called a free (or non-principal) ultrafilter.

One can show that every filter of a Boolean algebra (or more generally, any subset with the finite intersection property

Finite intersection property

In general topology, a branch of mathematics, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty....

) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice in the form of Zorn's Lemma

Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...

. 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

Boolean prime ideal theorem

In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...

  (BPIT), a well-known intermediate point between the axioms of Zermelo-Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). Proofs involving the axiom of choice do not produce explicit examples of free ultrafilters. Nonetheless, almost all ultrafilters on an infinite set are free. By contrast, every ultrafilter of a finite poset (or on a finite set) is principal, since any finite filter has a least element.

Applications

Ultrafilters on sets are useful in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

, especially in relation to compact

Compact space

In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...

 Hausdorff

Hausdorff space

In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...

 spaces, and in model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

 in the construction of ultraproducts and ultrapowers

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on posets are most important if the poset is a Boolean algebra, since in this case the ultrafilters coincide with the prime filters. Ultrafilters in this form play a central role in Stone's representation theorem for Boolean algebras

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 field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...

.

The set G of all ultrafilters of a poset P can be topologized in a natural way, that is in fact closely related to the abovementioned representation theorem. For any element a of P, let D_a = {U ∈ G | a ∈ U}. This is most useful when P is again a Boolean algebra, since in this situation the set of all D_a is a base for a compact Hausdorff topology on G. Especially, when considering the ultrafilters on a set S (i.e. the case that P is the powerset of S ordered via subset inclusion), the resulting topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

 is the Stone–Čech compactification

Stone–Cech compactification

In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

 of a discrete space of cardinality |S|.

The ultraproduct

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

 construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal number

Hyperreal number

The system of hyperreal numbers represents a rigorous method of treating the infinite and infinitesimal quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers greater than anything of the form1 + 1 + \cdots + 1. \, Such a number is...

s as an ultraproduct of the real numbers, we first extend the domain of discourse

Domain of discourse

In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...

 from the real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead we define the functions and relations "pointwise modulo U", where U is an ultrafilter on the index set of the sequences; by Łoś' theorem, this preserves all properties of the reals that can be stated in first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. If U is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory

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 groups and topological and geometric properties of spaces on which these groups act .Another important...

, non-principal ultrafilters are used to define the asymptotic cone of a group. These construction yields a rigorous way to consider looking at the group from infinity, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimit

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 an ultrafilter to avoid the process of repeatedly passing...

s of metric space

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...

s.

Gödel's ontological proof

Gödel's ontological proof

Gödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. It is in a line of development that goes back to Anselm of Canterbury. St. Anselm's ontological argument, in its most succinct form, is as follows: "God, by definition, is that for which no...

 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

Social choice theory is a theoretical framework for measuring individual interests, values, or welfares as an aggregate towards collective decision. A non-theoretical example of a collective decision is passing a set of laws under a constitution. Social choice theory dates from Condorcet's...

, 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

In social choice theory, Arrow’s impossibility theorem, the General Possibility Theorem, or Arrow’s paradox, states that, when voters have three or more distinct alternatives , no voting system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a...

 for finitely many individuals, such a rule satisfies the conditions (properties) that Arrow proposes
(e.g., Kirman and Sondermann, 1972).
Mihara (1997, 1999)
shows, however, such rules are practically of limited interest, since they are non-algorithmic or non-computable.

Ordering on ultrafilters

Rudin–Keisler ordering is a preorder

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

 on the class of ultrafilters defined as follows: if U is an ultrafilter on X, and V an ultrafilter on Y, then if and only if there exists a function f: X → Y such that
for every subset C of Y.

Ultrafilters U and V are Rudin–Keisler equivalent, , if there exist sets , , and a bijection

Bijection

A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

 f: A → B which 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 is the kernel of , i.e., if and only if and .

Ultrafilters on ω

There are several special properties that an ultrafilter on ω may possess, which prove useful in various areas of set theory and topology.

• A non-principal ultrafilter U is a P-point (or weakly selective) iff for every partition
  Partition of a set
  In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
  
   of ω, such that , there exists such that .
• A non-principal ultrafilter U is Ramsey (or selective) iff for every partition of ω, such that , there exists such that

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin

Walter Rudin

Walter Rudin was an American mathematician, for most of his career a Professor of Mathematics at the University of Wisconsin–Madison....

 proved that the continuum hypothesis

Continuum hypothesis

In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...

 implies the existence of Ramsey ultrafilters.
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom

Martin's axiom

In the mathematical field of set theory, Martin's axiom, introduced by , is a statement which is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, so certainly consistent with ZFC, but is also known to be consistent with ZF + ¬ CH...

. Saharon Shelah

Saharon Shelah

Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...

 later showed that it is consistent that there are no P-point ultrafilters.
Therefore the existence of these types of ultrafilters is independent

Independence (mathematical logic)

In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...

 of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space
In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, an ultrafilter on a set X is a collection of subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of X that is a filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

, that cannot be enlarged (as a filter). An ultrafilter may be considered as a finitely additive measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

. Then every subset of X is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0). If A is a subset of X, then either A or X \ A is an element of the ultrafilter (here X \ A is the relative complement

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 of A in X; that is, the set of all elements of X that are not in A). The concept can be generalized to Boolean algebras or even to general partial orders, and has many applications in set theory, model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, and topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

.

Formal definition

Given a set X, an ultrafilter on X is a set U consisting of subsets of X such that

1. The empty set is not an element of U
2. If A and B are subsets of X, A is a subset of B, and A is an element of U, then B is also an element of U.
3. If A and B are elements of U, then so is the intersection
   Intersection (set theory)
   In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
   
    of A and B.
4. If A is a subset of X, then either A or X \ A is an element of U. (Note: axioms 1 and 3 imply that A and X \ A cannot both be elements of U.)

A characterization is given by the following theorem.
A filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

 U on a set X is an ultrafilter if any of the following conditions are true:

1. There is no filter F finer than U, i.e. implies U = F.
2. implies or .
3. or .

Another way of looking at ultrafilters on a set X is to define a function m on the power set of X by setting m(A) = 1 if A is an element of U and m(A) = 0 otherwise. Then m is a finitely additive measure on X, and every property of elements of X is either true almost everywhere

Almost everywhere

In measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...

 or false almost everywhere. Note that this does not define a measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

 in the usual sense, which is required to be countably additive.

For a filter F which is not an ultrafilter, one would say m(A) = 1 if A ∈ F and m(A) = 0 if X \ A ∈ F, leaving m undefined elsewhere.

Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the Fréchet filter

Fréchet filter

In mathematics, Fréchet filter is an important concept in order theory.If X is an infinite set, the Fréchet filter,also called cofinite filter on X, is the set of all subsets of X having finite complement in X....

 of cofinite subsets of S. This is obvious, since a non-principal ultrafilter contains no finite set, and is closed under complement, which means that it contains all cofinite subsets of S, which is exactly the Fréchet filter.

Completeness

The completeness of an ultrafilter U on a set is the smallest cardinal κ such that there are κ elements of U whose intersection is not in U. The definition implies that the completeness of any ultrafilter is at least . An ultrafilter whose completeness is greater than —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 set is always a measurable cardinal

Measurable cardinal

- Measurable :Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of κ...

.

Generalization to partial orders

In order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, an ultrafilter is a subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of a partially ordered set

Partially ordered set

In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...

 (a poset) which is maximal

Maximal element

In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...

 among all proper filters. Formally, this states that any filter that properly contains an ultrafilter has to be equal to the whole poset. An important special case of the concept occurs if the considered poset is a Boolean algebra, as in the case of an ultrafilter on a set (defined as a filter of the corresponding powerset). In this case, ultrafilters are characterized by containing, for each element a of the Boolean algebra, exactly one of the elements a and ¬a (the latter being the Boolean complement of a).

Ultrafilters on a Boolean algebra can be identified with prime ideal

Prime ideal

In algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...

s, maximal ideal

Maximal ideal

In mathematics, more specifically in ring theory, a maximal ideal is an ideal which is maximal amongst all proper ideals. In other words, I is a maximal ideal of a ring R if I is an ideal of R, I ≠ R, and whenever J is another ideal containing I as a subset, then either J = I or J = R...

s, and homomorphisms to
the 2-element Boolean algebra {true, false}, as follows:

• Maximal ideals of a Boolean algebra are the same as prime ideals.
• Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
• Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
• Given an ultrafilter of a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".

Let us see another theorem which could be used for the definition of the concept of “ultrafilter”. Let B denote a Boolean algebra and F a proper filter in it. F is an ultrafilter iff:

for all , if , then or

(To avoid confusion: the sign denotes the join operation of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in.

Types and existence of ultrafilters

There are two very different types of ultrafilter: principal and free. A principal (or fixed, or trivial) ultrafilter is a filter containing a least element. Consequently, principal ultrafilters are of the form F_a = {x | a ≤ x} for some (but not all) elements a of the given poset. In this case a is called the principal element of the ultrafilter. For the case of filters on sets, the elements that qualify as principals are exactly the one-element sets. Thus, a principal ultrafilter on a set S consists of all sets containing a particular point of S. An ultrafilter on a finite set is principal. Any ultrafilter which is not principal is called a free (or non-principal) ultrafilter.

One can show that every filter of a Boolean algebra (or more generally, any subset with the finite intersection property

Finite intersection property

In general topology, a branch of mathematics, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty....

) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice in the form of Zorn's Lemma

Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...

. 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

Boolean prime ideal theorem

In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...

  (BPIT), a well-known intermediate point between the axioms of Zermelo-Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). Proofs involving the axiom of choice do not produce explicit examples of free ultrafilters. Nonetheless, almost all ultrafilters on an infinite set are free. By contrast, every ultrafilter of a finite poset (or on a finite set) is principal, since any finite filter has a least element.

Applications

Ultrafilters on sets are useful in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

, especially in relation to compact

Compact space

In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...

 Hausdorff

Hausdorff space

In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...

 spaces, and in model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

 in the construction of ultraproducts and ultrapowers

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on posets are most important if the poset is a Boolean algebra, since in this case the ultrafilters coincide with the prime filters. Ultrafilters in this form play a central role in Stone's representation theorem for Boolean algebras

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 field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...

.

The set G of all ultrafilters of a poset P can be topologized in a natural way, that is in fact closely related to the abovementioned representation theorem. For any element a of P, let D_a = {U ∈ G | a ∈ U}. This is most useful when P is again a Boolean algebra, since in this situation the set of all D_a is a base for a compact Hausdorff topology on G. Especially, when considering the ultrafilters on a set S (i.e. the case that P is the powerset of S ordered via subset inclusion), the resulting topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

 is the Stone–Čech compactification

Stone–Cech compactification

In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

 of a discrete space of cardinality |S|.

The ultraproduct

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

 construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal number

Hyperreal number

The system of hyperreal numbers represents a rigorous method of treating the infinite and infinitesimal quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers greater than anything of the form1 + 1 + \cdots + 1. \, Such a number is...

s as an ultraproduct of the real numbers, we first extend the domain of discourse

Domain of discourse

In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...

 from the real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead we define the functions and relations "pointwise modulo U", where U is an ultrafilter on the index set of the sequences; by Łoś' theorem, this preserves all properties of the reals that can be stated in first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. If U is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory

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 groups and topological and geometric properties of spaces on which these groups act .Another important...

, non-principal ultrafilters are used to define the asymptotic cone of a group. These construction yields a rigorous way to consider looking at the group from infinity, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimit

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 an ultrafilter to avoid the process of repeatedly passing...

s of metric space

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...

s.

Gödel's ontological proof

Gödel's ontological proof

Gödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. It is in a line of development that goes back to Anselm of Canterbury. St. Anselm's ontological argument, in its most succinct form, is as follows: "God, by definition, is that for which no...

 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

Social choice theory is a theoretical framework for measuring individual interests, values, or welfares as an aggregate towards collective decision. A non-theoretical example of a collective decision is passing a set of laws under a constitution. Social choice theory dates from Condorcet's...

, 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

In social choice theory, Arrow’s impossibility theorem, the General Possibility Theorem, or Arrow’s paradox, states that, when voters have three or more distinct alternatives , no voting system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a...

 for finitely many individuals, such a rule satisfies the conditions (properties) that Arrow proposes
(e.g., Kirman and Sondermann, 1972).
Mihara (1997, 1999)
shows, however, such rules are practically of limited interest, since they are non-algorithmic or non-computable.

Ordering on ultrafilters

Rudin–Keisler ordering is a preorder

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

 on the class of ultrafilters defined as follows: if U is an ultrafilter on X, and V an ultrafilter on Y, then if and only if there exists a function f: X → Y such that
for every subset C of Y.

Ultrafilters U and V are Rudin–Keisler equivalent, , if there exist sets , , and a bijection

Bijection

A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

 f: A → B which 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 is the kernel of , i.e., if and only if and .

Ultrafilters on ω

There are several special properties that an ultrafilter on ω may possess, which prove useful in various areas of set theory and topology.

• A non-principal ultrafilter U is a P-point (or weakly selective) iff for every partition
  Partition of a set
  In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
  
   of ω, such that , there exists such that .
• A non-principal ultrafilter U is Ramsey (or selective) iff for every partition of ω, such that , there exists such that

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin

Walter Rudin

Walter Rudin was an American mathematician, for most of his career a Professor of Mathematics at the University of Wisconsin–Madison....

 proved that the continuum hypothesis

Continuum hypothesis

In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...

 implies the existence of Ramsey ultrafilters.
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom

Martin's axiom

In the mathematical field of set theory, Martin's axiom, introduced by , is a statement which is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, so certainly consistent with ZFC, but is also known to be consistent with ZF + ¬ CH...

. Saharon Shelah

Saharon Shelah

Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...

 later showed that it is consistent that there are no P-point ultrafilters.
Therefore the existence of these types of ultrafilters is independent

Independence (mathematical logic)

In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...

 of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space
In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, an ultrafilter on a set X is a collection of subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of X that is a filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

, that cannot be enlarged (as a filter). An ultrafilter may be considered as a finitely additive measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

. Then every subset of X is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0). If A is a subset of X, then either A or X \ A is an element of the ultrafilter (here X \ A is the relative complement

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 of A in X; that is, the set of all elements of X that are not in A). The concept can be generalized to Boolean algebras or even to general partial orders, and has many applications in set theory, model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, and topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

.

Formal definition

Given a set X, an ultrafilter on X is a set U consisting of subsets of X such that

1. The empty set is not an element of U
2. If A and B are subsets of X, A is a subset of B, and A is an element of U, then B is also an element of U.
3. If A and B are elements of U, then so is the intersection
   Intersection (set theory)
   In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
   
    of A and B.
4. If A is a subset of X, then either A or X \ A is an element of U. (Note: axioms 1 and 3 imply that A and X \ A cannot both be elements of U.)

A characterization is given by the following theorem.
A filter

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...

 U on a set X is an ultrafilter if any of the following conditions are true:

1. There is no filter F finer than U, i.e. implies U = F.
2. implies or .
3. or .

Another way of looking at ultrafilters on a set X is to define a function m on the power set of X by setting m(A) = 1 if A is an element of U and m(A) = 0 otherwise. Then m is a finitely additive measure on X, and every property of elements of X is either true almost everywhere

Almost everywhere

In measure theory , a property holds almost everywhere if the set of elements for which the property does not hold is a null set, that is, a set of measure zero . In cases where the measure is not complete, it is sufficient that the set is contained within a set of measure zero...

 or false almost everywhere. Note that this does not define a measure

Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

 in the usual sense, which is required to be countably additive.

For a filter F which is not an ultrafilter, one would say m(A) = 1 if A ∈ F and m(A) = 0 if X \ A ∈ F, leaving m undefined elsewhere.

Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the Fréchet filter

Fréchet filter

In mathematics, Fréchet filter is an important concept in order theory.If X is an infinite set, the Fréchet filter,also called cofinite filter on X, is the set of all subsets of X having finite complement in X....

 of cofinite subsets of S. This is obvious, since a non-principal ultrafilter contains no finite set, and is closed under complement, which means that it contains all cofinite subsets of S, which is exactly the Fréchet filter.

Completeness

The completeness of an ultrafilter U on a set is the smallest cardinal κ such that there are κ elements of U whose intersection is not in U. The definition implies that the completeness of any ultrafilter is at least . An ultrafilter whose completeness is greater than —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 set is always a measurable cardinal

Measurable cardinal

- Measurable :Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of κ...

.

Generalization to partial orders

In order theory

Order theory

Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, an ultrafilter is a subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of a partially ordered set

Partially ordered set

In mathematics, especially order theory, a partially ordered set 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 relation that indicates that, for certain pairs of elements in the...

 (a poset) which is maximal

Maximal element

In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...

 among all proper filters. Formally, this states that any filter that properly contains an ultrafilter has to be equal to the whole poset. An important special case of the concept occurs if the considered poset is a Boolean algebra, as in the case of an ultrafilter on a set (defined as a filter of the corresponding powerset). In this case, ultrafilters are characterized by containing, for each element a of the Boolean algebra, exactly one of the elements a and ¬a (the latter being the Boolean complement of a).

Ultrafilters on a Boolean algebra can be identified with prime ideal

Prime ideal

In algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...

s, maximal ideal

Maximal ideal

In mathematics, more specifically in ring theory, a maximal ideal is an ideal which is maximal amongst all proper ideals. In other words, I is a maximal ideal of a ring R if I is an ideal of R, I ≠ R, and whenever J is another ideal containing I as a subset, then either J = I or J = R...

s, and homomorphisms to
the 2-element Boolean algebra {true, false}, as follows:

• Maximal ideals of a Boolean algebra are the same as prime ideals.
• Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
• Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
• Given an ultrafilter of a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".

Let us see another theorem which could be used for the definition of the concept of “ultrafilter”. Let B denote a Boolean algebra and F a proper filter in it. F is an ultrafilter iff:

for all , if , then or

(To avoid confusion: the sign denotes the join operation of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in.

Types and existence of ultrafilters

There are two very different types of ultrafilter: principal and free. A principal (or fixed, or trivial) ultrafilter is a filter containing a least element. Consequently, principal ultrafilters are of the form F_a = {x | a ≤ x} for some (but not all) elements a of the given poset. In this case a is called the principal element of the ultrafilter. For the case of filters on sets, the elements that qualify as principals are exactly the one-element sets. Thus, a principal ultrafilter on a set S consists of all sets containing a particular point of S. An ultrafilter on a finite set is principal. Any ultrafilter which is not principal is called a free (or non-principal) ultrafilter.

One can show that every filter of a Boolean algebra (or more generally, any subset with the finite intersection property

Finite intersection property

In general topology, a branch of mathematics, the finite intersection property is a property of a collection of subsets of a set X. A collection has this property if the intersection over any finite subcollection of the collection is nonempty....

) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice in the form of Zorn's Lemma

Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...

. 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

Boolean prime ideal theorem

In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...

  (BPIT), a well-known intermediate point between the axioms of Zermelo-Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). Proofs involving the axiom of choice do not produce explicit examples of free ultrafilters. Nonetheless, almost all ultrafilters on an infinite set are free. By contrast, every ultrafilter of a finite poset (or on a finite set) is principal, since any finite filter has a least element.

Applications

Ultrafilters on sets are useful in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

, especially in relation to compact

Compact space

In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...

 Hausdorff

Hausdorff space

In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...

 spaces, and in model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

 in the construction of ultraproducts and ultrapowers

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on posets are most important if the poset is a Boolean algebra, since in this case the ultrafilters coincide with the prime filters. Ultrafilters in this form play a central role in Stone's representation theorem for Boolean algebras

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 field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...

.

The set G of all ultrafilters of a poset P can be topologized in a natural way, that is in fact closely related to the abovementioned representation theorem. For any element a of P, let D_a = {U ∈ G | a ∈ U}. This is most useful when P is again a Boolean algebra, since in this situation the set of all D_a is a base for a compact Hausdorff topology on G. Especially, when considering the ultrafilters on a set S (i.e. the case that P is the powerset of S ordered via subset inclusion), the resulting topological space

Topological space

Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...

 is the Stone–Čech compactification

Stone–Cech compactification

In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

 of a discrete space of cardinality |S|.

The ultraproduct

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic. An ultraproduct is a quotient of the direct product of a family of structures. All factors need to have the same signature...

 construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal number

Hyperreal number

The system of hyperreal numbers represents a rigorous method of treating the infinite and infinitesimal quantities. The hyperreals, or nonstandard reals, *R, are an extension of the real numbers R that contains numbers greater than anything of the form1 + 1 + \cdots + 1. \, Such a number is...

s as an ultraproduct of the real numbers, we first extend the domain of discourse

Domain of discourse

In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...

 from the real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead we define the functions and relations "pointwise modulo U", where U is an ultrafilter on the index set of the sequences; by Łoś' theorem, this preserves all properties of the reals that can be stated in first-order logic

First-order logic

First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. If U is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory

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 groups and topological and geometric properties of spaces on which these groups act .Another important...

, non-principal ultrafilters are used to define the asymptotic cone of a group. These construction yields a rigorous way to consider looking at the group from infinity, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimit

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 an ultrafilter to avoid the process of repeatedly passing...

s of metric space

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...

s.

Gödel's ontological proof

Gödel's ontological proof

Gödel's ontological proof is a formal argument for God's existence by the mathematician Kurt Gödel. It is in a line of development that goes back to Anselm of Canterbury. St. Anselm's ontological argument, in its most succinct form, is as follows: "God, by definition, is that for which no...

 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

Social choice theory is a theoretical framework for measuring individual interests, values, or welfares as an aggregate towards collective decision. A non-theoretical example of a collective decision is passing a set of laws under a constitution. Social choice theory dates from Condorcet's...

, 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

In social choice theory, Arrow’s impossibility theorem, the General Possibility Theorem, or Arrow’s paradox, states that, when voters have three or more distinct alternatives , no voting system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a...

 for finitely many individuals, such a rule satisfies the conditions (properties) that Arrow proposes
(e.g., Kirman and Sondermann, 1972).
Mihara (1997, 1999)
shows, however, such rules are practically of limited interest, since they are non-algorithmic or non-computable.

Ordering on ultrafilters

Rudin–Keisler ordering is a preorder

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

 on the class of ultrafilters defined as follows: if U is an ultrafilter on X, and V an ultrafilter on Y, then if and only if there exists a function f: X → Y such that
for every subset C of Y.

Ultrafilters U and V are Rudin–Keisler equivalent, , if there exist sets , , and a bijection

Bijection

A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

 f: A → B which 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 is the kernel of , i.e., if and only if and .

Ultrafilters on ω

There are several special properties that an ultrafilter on ω may possess, which prove useful in various areas of set theory and topology.

• A non-principal ultrafilter U is a P-point (or weakly selective) iff for every partition
  Partition of a set
  In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
  
   of ω, such that , there exists such that .
• A non-principal ultrafilter U is Ramsey (or selective) iff for every partition of ω, such that , there exists such that

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin

Walter Rudin

Walter Rudin was an American mathematician, for most of his career a Professor of Mathematics at the University of Wisconsin–Madison....

 proved that the continuum hypothesis

Continuum hypothesis

In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...

 implies the existence of Ramsey ultrafilters.
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom

Martin's axiom

In the mathematical field of set theory, Martin's axiom, introduced by , is a statement which is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, so certainly consistent with ZFC, but is also known to be consistent with ZF + ¬ CH...

. Saharon Shelah

Saharon Shelah

Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...

 later showed that it is consistent that there are no P-point ultrafilters.
Therefore the existence of these types of ultrafilters is independent

Independence (mathematical logic)

In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...

 of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space {{nowrap

Stone–Cech compactification

In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

 of non-principal ultrafilters. The name Ramsey comes from Ramsey's theorem

Ramsey's theorem

In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...

. To see why, one can prove that an ultrafilter is Ramsey if and only if for every 2-coloring of there exists an element of the ultrafilter which has a homogeneous color.

An ultrafilter on ω is Ramsey if and only if it is minimal in the Rudin–Keisler ordering of non-principal ultrafilters.