Ultrafilter

Get Ultrafilter essential facts below. View Videos or join the Ultrafilter discussion. Add Ultrafilter to your PopFlock.com topic list for future reference or share this resource on social media.
## Ultrafilters on partial orders

## Special case: ultrafilter on a Boolean algebra

## Special case: ultrafilter on the powerset of a set

## Applications

## Types and existence of ultrafilters

## Ultrafilters on sets

### Generalization to ultra prefilters

### Characterizations

#### Grills and Filter-Grills

#### Free or principal

### Examples, properties, and sufficient conditions

#### Monad structure

### The ultrafilter lemma

#### Relationships to other statements under ZF

### Completeness

### Ordering on ultrafilters

### Ultrafilters on ?(*?*)

## See also

## Notes

## References

## Bibliography

## Further reading

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Ultrafilter

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

If *X* is an arbitrary set, its power set ?(*X*), ordered by set inclusion, is always a Boolean algebra and hence a poset, and (ultra)filters on ?(*X*) are usually called "(ultra)filters on *X*".^{[note 1]} An ultrafilter on a set *X* may be considered as a finitely additive measure on *X.* In this view, every subset of *X* is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0), depending on whether it belongs to the given ultrafilter or not.^{[]}

Ultrafilters have many applications in set theory, model theory, and topology.^{[1]}^{:186}

In order theory, an **ultrafilter** is a subset of a partially ordered set that is maximal among all proper filters. This implies that any filter that properly contains an ultrafilter has to be equal to the whole poset.

Formally, if *P* is a set, partially ordered by (

- a subset
*F*of*P*is called a**filter**on*P*if*F*is nonempty,- for every
*x*,*y*in*F*, there is some element*z*in*F*such that*z*x and*z*y, and - for every
*x*in*F*and*y*in*P*,*x*y implies that*y*is in*F*, too;

- a proper subset
*U*of*P*is called an**ultrafilter**on*P*if*U*is a filter on*P*, and- there is no proper filter
*F*on*P*that properly extends*U*(that is, such that*U*is a proper subset of*F*).

An important special case of the concept occurs if the considered poset is a Boolean algebra. In this case, ultrafilters are characterized by containing, for each element *a* of the Boolean algebra, exactly one of the elements *a* and ¬*a* (the latter being the Boolean complement of *a*):

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

*F*is an ultrafilter on*P*,*F*is a prime filter on*P*,- for each
*a*in*P*, either*a*is in*F*or (¬*a*) is in*F*.^{[1]}^{:186}

A proof of 1. 2. is also given in (Burris, Sankappanavar, 2012, Corollary 3.13, p.133).^{[2]}

Moreover, ultrafilters on a Boolean algebra can be related to maximal ideals and homomorphisms to the 2-element Boolean algebra {true, false} (also known as 2-valued morphisms) as follows:

- Given a homomorphism of a Boolean algebra onto {true, false}, the inverse image of "true" is an ultrafilter, and the inverse image of "false" is a maximal ideal.
- Given a maximal ideal of a Boolean algebra, its complement is an ultrafilter, and there is a unique homomorphism onto {true, false} taking the maximal ideal to "false".
- Given an ultrafilter on a Boolean algebra, its complement is a maximal ideal, and there is a unique homomorphism onto {true, false} taking the ultrafilter to "true".
^{[]}

Given an arbitrary set *X*, its power set ?(*X*), ordered by set inclusion, is always a Boolean algebra; hence the results of the above section *Special case: Boolean algebra* apply. An (ultra)filter on ?(*X*) is often called just an "(ultra)filter on *X*".^{[note 1]} The above formal definitions can be particularized to the powerset case as follows:

Given an arbitrary set *X*, an ultrafilter on ?(*X*) is a set *U* consisting of subsets of *X* such that:

- The empty set is not an element of
*U*. - If
*A*and*B*are subsets of*X*, the set*A*is a subset of*B*, and*A*is an element of*U*, then*B*is also an element of*U*. - If
*A*and*B*are elements of*U*, then so is the intersection of*A*and*B*. - If
*A*is a subset of*X*, then either^{[note 2]}*A*or its relative complement*X*\*A*is an element of*U*.

Another way of looking at ultrafilters on a power set ?(*X*) is as follows: for a given ultrafilter *U* define a function *m* on ?(*X*) by setting *m*(*A*) = 1 if *A* is an element of *U* and *m*(*A*) = 0 otherwise. Such a function is called a 2-valued morphism. Then *m* is finitely additive, and hence a *content* on ?(*X*), and every property of elements of *X* is either true almost everywhere or false almost everywhere. However, *m* is usually not *countably additive*, and hence does not define a measure in the usual sense.

For a filter *F* that 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.^{[]}^{[clarification needed]}

Ultrafilters on powersets are useful in topology, especially in relation to compact Hausdorff spaces, and in model theory in the construction of ultraproducts and ultrapowers. Every ultrafilter on a compact Hausdorff space converges to exactly one point. Likewise, ultrafilters on Boolean algebras play a central role in Stone's representation theorem.

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 above-mentioned 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 powerset ?(*S*), the resulting topological space is the Stone-?ech compactification of a discrete space of cardinality |*S*|.

The ultraproduct construction in model theory uses ultrafilters to produce elementary extensions of structures. For example, in constructing hyperreal numbers as an ultraproduct of the real numbers, the domain of discourse is extended from real numbers to sequences of real numbers. This sequence space is regarded as a superset of the reals by identifying each real with the corresponding constant sequence. To extend the familiar functions and relations (e.g., + and <) from the reals to the hyperreals, the natural idea is to define them pointwise. But this would lose important logical properties of the reals; for example, pointwise < is not a total ordering. So instead the functions and relations are defined "pointwise modulo *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. If *U* is nonprincipal, then the extension thereby obtained is nontrivial.

In geometric group theory, non-principal ultrafilters are used to define the asymptotic cone of a group. This construction yields a rigorous way to consider *looking at the group from infinity*, that is the large scale geometry of the group. Asymptotic cones are particular examples of ultralimits of metric spaces.

Gödel's ontological proof of God's existence uses as an axiom that the set of all "positive properties" is an ultrafilter.

In social choice theory, non-principal ultrafilters are used to define a rule (called a *social welfare function*) for aggregating the preferences of *infinitely* many individuals. Contrary to Arrow's impossibility theorem for *finitely* many individuals, such a rule satisfies the conditions (properties) that Arrow proposes (for example, Kirman and Sondermann, 1972).^{[3]} Mihara (1997,^{[4]} 1999)^{[5]} shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.

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. Any ultrafilter that is not principal is called a **free** (or **non-principal**) ultrafilter.

For ultrafilters on a powerset ?(*S*), a principal ultrafilter consists of all subsets of *S* that contain a given element *s* of *S*. Each ultrafilter on ?(*S*) that is also a principal filter is of this form.^{[1]}^{:187} Therefore, an ultrafilter *U* on ?(*S*) is principal if and only if it contains a finite set.^{[note 3]} If *S* is infinite, an ultrafilter *U* on ?(*S*) is hence non-principal if and only if it contains the Fréchet filter of cofinite subsets of *S*.^{[note 4]}^{[]} If *S* is finite, each ultrafilter is principal.^{[1]}^{:187}

One can show that every filter on a Boolean algebra (or more generally, any subset with the finite intersection property) is contained in an ultrafilter (see Ultrafilter lemma) and that free ultrafilters therefore exist, but the proofs involve the axiom of choice (AC) in the form of Zorn's lemma. On the other hand, the statement that every filter is contained in an ultrafilter does not imply AC. Indeed, it is equivalent to the Boolean prime ideal theorem (BPIT), a well-known intermediate point between the axioms of Zermelo-Fraenkel set theory (ZF) and the ZF theory augmented by the axiom of choice (ZFC). In general, proofs involving the axiom of choice do not produce explicit examples of free ultrafilters, though it is possible to find explicit examples in some models of ZFC; for example, Gödel showed that this can be done in the constructible universe where one can write down an explicit global choice function. In ZF without the axiom of choice, it is possible that every ultrafilter is principal.^{[6]}

A **filter subbase** is a non-empty family of sets that has the finite intersection property (i.e. all finite intersections are non-empty). Equivalently, a filter subbase is a non-empty family of sets that is contained in *some* proper filter. The smallest (relative to ?) proper filter containing a given filter subbase is said to be **generated** by the filter subbase.

The **upward closure** in X of a family of sets *P* is the set { *S* : *A* ? *S* ? *X* for some *A* ? *P* }.

A **prefilter** *P* is a non-empty and proper (i.e. ? ? *P*) family of sets that is **downward directed**, which means that if *B*, *C* ? *P* then there exists some *A* ? *P* such that *A* ? *B* ? *C*. Equivalently, a prefilter is any family of sets *P* whose upward closure is a proper filter, in which case this filter is called the **filter generated by P**.

The **dual in X**^{[7]} of a family of sets *U* is the set *X* \ *U* := { *X* \ *B* : *B* ? *U* }.

- A family
*U*? ? of subsets of X is called**ultra**if ? ?*U*and any of the following equivalent conditions are satisfied:^{[7]}^{[8]}

- For every set
*S*?*X*there exists some set*B*?*U*such that*B*?*S*or*B*?*X*\*S*(or equivalently, such that*B*?*S*equals B or ?). - For every set
*S*?*B*there exists some set*B*?*U*such that*B*?*S*equals B or ?.- Here,
*B*is defined to be the union of all sets in*U*. - This characterization of "
*U*is ultra" does not depend on the set X, so mentioning the set X is optional when using the term "ultra."

- Here,
- For
*every*set*S*(not necessarily even a subset of X ) there exists some set*B*?*U*such that*B*?*S*equals B or ?.- If
*U*satisfies this condition then so does*every*superset*V*?*U*. In particular, a set*V*is ultra if and only if ? ?*V*and*V*contains as a subset some ultra family of sets.

- If

A filter subbase that is ultra is necessarily a prefilter.

- An
**ultra prefilter**^{[7]}^{[8]}is a prefilter that is ultra. Equivalently, it is a filter subbase that is ultra.

- An
**ultrafilter**^{[7]}^{[8]}on X is a proper filter on X that is ultra. Equivalently, it is any proper filter on X that is generated by an ultra prefilter.

- Interpretation as
*large*sets

The elements of a proper filter *F* on X may be thought of as being "large sets (relative to *F*)" and the complements in X of a large sets can be thought of as being "small" sets^{[9]} (the "small sets" are exactly the elements in the ideal *X* \ *F*). In general, there may be subsets of X that are *neither* large nor small, or possibly *simultaneously* large and small. A dual ideal is a filter (i.e. proper) if there is no set that is both large and small, or equivalently, if the ? is not large.^{[9]} A filter is ultra if and only if *every* subset of X is either large or else small. With this terminology, the defining properties of a filter can be restarted as: (1) any superset of a large set is large set, (2) the intersection of any two (or finitely many) large sets is large, (3) X is a large set (i.e. *F* ? ?), (4) the empty set is not large. Different dual ideals give different notions of "large" sets.

- Ultra prefilters as maximal prefilters

To characterize ultra prefilters in terms of "maximality," the following relation is needed.

- Given two families of sets
*M*and*N*, the family*M*is said to be**coarser**^{[10]}^{[11]}than*N*, and*N*is**finer**than and**subordinate to***M*, written*M*N or*N*?*M*, if for every*C*?*M*, there is some*F*?*N*such that*F*?*C*. The families*M*and*N*are called**equivalent**if*M*N and*N*M. The families*M*and*N*are**comparable**if one of these sets is finer than the other.^{[10]}

The subordination relationship, i.e. , is a preorder so the above definition of "equivalent" does form an equivalence relation.
If *M* ? *N* then *M* N but the converse does not hold in general.
However, if *N* is upward closed, such as a filter, then *M* N if and only if *M* ? *N*.
Every prefilter is equivalent to the filter that it generates. This shows that it is possible for filters to be equivalent to sets that are not filters.

If two families of sets *M* and *N* are equivalent then either both *M* and *N* are ultra (resp. prefilters, filter subbases) or otherwise neither one of them is ultra (resp. a prefilter, a filter subbase).
In particular, if a filter subbase is not also a prefilter, then it is *not* equivalent to the filter or prefilter that it generates. If *M* and *N* are both filters on X then *M* and *N* are equivalent if and only if *M* = *N*. If a proper filter (resp. ultrafilter) is equivalent to a family of sets *M* then *M* is necessarily a prefilter (resp. ultra prefilter).
Using the following characterization, it is possible to define prefilters (resp. ultra prefilters) using only the concept of filters (resp. ultrafilters) and subordination:

- A family of sets is a prefilter (resp. an ultra prefilter) if and only it is equivalent to a proper filter (resp. an ultrafilter).

- A
**maximal prefilter on X**^{[7]}^{[8]}is a prefilter*U*? ?(*X*) that satisfies any of the following equivalent conditions:

*U*is ultra.*U*is**maximal**on Prefilters(*X*) (with respect to ), meaning that if*P*? Prefilters(*X*) satisfies*U*P then*P*U.^{[8]}- There is no prefilter properly subordinate to
*U*.^{[8]} - If a proper filter
*F*on X satisfies*U*F then*F*U. - The filter on X generated by
*U*is ultra.

There are no ultrafilters on ?(*?*) so it is henceforth assumed that *X* ? ?.

A filter *sub*base *U* on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:^{[7]}^{[8]}

- for any
*S*?*X*, either*S*?*U*or*X*\*S*?*U*. *U*is a maximal filter subbase on X, meaning that if*F*is any filter subbase on X then*U*?*F*implies*U*=*F*.^{[9]}

A proper filter *U* on X is an ultrafilter on X if and only if any of the following equivalent conditions hold:

*U*is ultra;*U*is generated an ultra prefilter;- For any subset
*S*?*X*,*S*?*U*or*X*\*S*?*U*.^{[9]}- So an ultrafilter
*U*decides for every*S*?*X*whether S is "large" (i.e.*S*?*U*) or "small" (i.e.*X*\*S*?*U*).^{[12]}

- So an ultrafilter
- For each subset
*A*of*X*, either^{[note 2]}*A*is in*U*or (*X*\*A*) is. *U*? (*X*\*U*) = ?(*X*). This condition can be restated as: ?(*X*) is partitioned by*U*and its dual*X*\*U*.- The sets
*P*and*X*\*P*are disjoint for all prefilters*P*on X.

- The sets
- ?(
*X*) \*U*= {*S*? ?(*X*) :*S*?*U*} is an ideal on X.^{[9]} - For any finite family
*S*_{1}, ...,*S*_{n}of subsets of X (where*n*>= 1), if*S*_{1}? ?*S*_{n}?*U*then*S*_{i}?*U*for some index i.- In words, a "large" set cannot be a finite union of sets that aren't large.
^{[13]}

- In words, a "large" set cannot be a finite union of sets that aren't large.
- For any
*R*,*S*?*X*, if*R*?*S*=*X*then*R*?*U*or*S*?*U*. - For any
*R*,*S*?*X*, if*R*?*S*?*U*then*R*?*U*or*S*?*U*(a filter with this property is called a).*prime filter* - For any
*R*,*S*?*X*, if*R*?*S*?*U*and*R*?*S*= ? then*either**R*?*U*or*S*?*U*. *U*is a maximal filter; that is, if*F*is a filter on X such that*U*?*F*then*U*=*F*. Equivalently,*U*is a maximal filter if there is no filter*F*on X that contains*U*as a proper subset (i.e. that is strictly finer than*U*).^{[9]}

If then its *grill on * is the family which is upward closed in and moreover, so that is upward closed in if and only if If is a filter subbase then ^{[14]} Moreover, and The grill of a filter on is called a *filter-grill on *^{[14]} For any is the grill of a filter on if and only if (1) is upward closed in and (2) for all sets and if then or The grill operation defined by is a bijection whose inverse is also given by ^{[14]} If then is a filter-grill on if and only if ^{[14]} or equivalently, if and only if is an ultrafilter on ^{[14]} Filter-grills on are thus the same as ultrafilters on For any non-empty is a filter-grill on if and only if and for all subsets the following equivalences hold: if and only if if and only if ^{[14]}

If *P* is any non-empty family of sets then the **Kernel of P** is the intersection of all set in

- ker
*P*:=*B*^{[15]}

A non-empty family of sets *P* is called:

**free**if ker*P*= ? and**fixed**otherwise (i.e. if ker*P*? ?),**principal**if ker*P*?*P*,**principal at a point**if ker*P*?*P*and ker*P*is a singleton set; in this case, if ker*P*= {*x*} then*P*is said to be**principal at x**.

If a family of sets *P* is fixed then *P* is ultra if and only if some element of *P* is a singleton set, in which case *P* will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter *P* is ultra if and only if ker *P* is a singleton set.
A singleton set is ultra if and only if its sole element is also a singleton set.

Every filter on X that is principal at a single point is an ultrafilter, and if in addition X is finite, then there are no ultrafilters on X other than these.^{[15]}
If there exists a free ultrafilter (or even filter subbase) on a set X then X must be infinite.

The next theorem shows that every ultrafilter falls into one of two categories: either it is free or else it is a principal filter generated by a single point.

**Proposition** — If *U* is an ultrafilter on X then the following are equivalent:

*U*is fixed, or equivalently, not free.*U*is principal.- Some element of
*U*is a finite set. - Some element of
*U*is a singleton set. *U*is principal at some point of X, which means ker*U*= {*x*} ?*U*for*x*?*X*.*U*does*not*contain the Fréchet filter on X.*U*is sequential.^{[14]}

If *U* and *S* are families of sets such that *U* is ultra, ? ? *S*, and *U* S, then *S* is necessarily ultra.
A filter subbase *U* that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by *U* to be ultra.

Suppose *U* ? ?(*X*) is ultra and *Y* is a set. The trace
*U* ? *Y* := { *B* ? *Y* : *B* ? *U* }
is ultra if and only if it does not contain the empty set.
Furthermore, at least one of the sets [*U* ? *Y*] \ { ? } and [*U* ? (*X* \ *Y*)] \ { ? } will be ultra (this result extends to any finite partition of X).
If *F*_{1}, ..., *F*_{n} are filters on X, *U* is an ultrafilter on X, and
*F*_{1} ? ? *F*_{n}U,
then there is some *F*_{i} that satisfies *F*_{i}U.^{[16]}
This result is not necessarily true for an infinite family of filters.^{[16]}

The image under a map *f* : *X* -> *Y* of an ultra set *U* ? ?(*X*) is again ultra and if *U* is an ultra prefilter then so is *f*(*U* ). The property of being ultra is preserved under bijections. However, the preimage of an ultrafilter is not necessarily ultra, not even if the map is surjective. For example, if X has more than one point and if the range of *f* : *X* -> *Y* consists of a single point { *y* } then { { *y* } } is an ultra prefilter on Y but its preimage is not ultra. Alternatively, if *U* is a principal filter generated by a point in *Y* \ *f* (*X*) then the preimage of *U* contains the empty set and so is not ultra.

The elementary filter induced by a infinite sequence, all of whose points are distinct, is *not* an ultrafilter.^{[16]} If *n* = 2, *U*_{n} denotes the set consisting all subsets of X having cardinality n, and if X contains at least 2 *n* - 1 (= 3) distinct points, then *U*_{n} is ultra but it is not contained in any prefilter. This example generalizes to any integer *n* > 1 and also to *n* = 1 if X contains more than one element. Ultra sets that aren't also prefilters are rarely used.

For every and every let If is an ultrafilter on X then the set of all such that is an ultrafilter on ^{[17]}

The functor associating to any set *X* the set of *U*(*X*) of all ultrafilters on *X* forms a monad called the ultrafilter monad. The unit map

sends any element *x* ? *X* to the principal ultrafilter given by *x*.

This monad admits a conceptual explanation as the codensity monad of the inclusion of the category of finite sets into the category of all sets.^{[18]}

The ultrafilter lemma was first proved by Alfred Tarski in 1930.^{[17]}

**The ultrafilter lemma/principle/theorem ^{[10]}** — Every proper filter on a set is contained in some ultrafilter on

The ultrafilter lemma is equivalent to each of the following statements:

- For every prefilter on a set there exists a maximal prefilter on subordinate to it.
^{[7]} - Every proper filter subbase on a set is contained in some ultrafilter on

A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.^{[19]}^{[note 5]}

The following results can be proven using the ultrafilter lemma.
A free ultrafilter exists on a set if and only if is infinite. Every proper filter is equal to the intersection of all ultrafilters containing it.^{[10]} Since there are filters that are not ultra, this shows that the intersection of a family of ultrafilters need not be ultra. A family of sets can be extended to a free ultrafilter if and only if the intersection of any finite family of elements of is infinite.

Throughout this section, Zermelo-Fraenkel set theory (ZF) is assumed.
The ultrafilter lemma is equivalent to the Boolean prime ideal theorem, with the equivalence provable in ZF set theory without the axiom of choice. Assuming ZF, the ultrafilter lemma is equivalent to the ultranet lemma: every net has a universal subnet.^{[20]} By definition, a net in is an *ultranet* or an *universal net* if for every subset the net is eventually in or

Every filter that contains a singleton set is necessarily an ultrafilter and given the definition of the discrete ultrafilter does not require more than ZF. If is finite, then every ultrafilter is discrete at a point so free ultrafilters can only exist on infinite sets. In particular, if is finite then the ultrafilter lemma can be proven from the axioms ZF.

The existence of free ultrafilter on infinite sets can be proven if the axiom of choice is assumed. More generally, the ultrafilter lemma can be proven by using the axiom of choice, which in brief states that any Cartesian product of non-empty sets is non-empty. Under ZF, the axiom of choice is, in particular, equivalent to (a) Zorn's lemma, (b) Tychonoff's theorem, (c) every vector space has a basis, and other statements. However, the ultrafilter lemma is strictly weaker than the axiom of choice.

The ultrafilter lemma has many applications in topology. The ultrafilter lemma can be used to prove the Hahn-Banach theorem, the Alexander subbase theorem, and that any product of compact *Hausdorff* spaces is compact (which is a special case of Tychonoff's theorem).^{[20]}
The ultrafilter lemma can be used to prove the Axiom of choice for finite sets; explicitly, this is the statement: Given and a family of non-empty *finite* sets, their product is not empty.^{[20]}

The **completeness** of an ultrafilter *U* on a powerset is the smallest cardinal ? such that there are ? elements of *U* whose intersection is not in *U*. The definition of an ultrafilter implies that the completeness of any powerset ultrafilter is at least . 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 powerset is always a measurable cardinal.^{[]}

The **Rudin-Keisler ordering** (named after Mary Ellen Rudin and Howard Jerome Keisler) is a preorder on the class of powerset ultrafilters defined as follows: if *U* is an ultrafilter on ?(*X*), and *V* an ultrafilter on ?(*Y*), then *V* RK *U* if there exists a function *f*: *X* -> *Y* such that

*C*?*V**f*^{ -1}[*C*] ?*U*

for every subset *C* of *Y*.

Ultrafilters *U* and *V* are called **Rudin-Keisler equivalent**, denoted *U* ?_{RK}*V*, if there exist sets *A* ? *U* and *B* ? *V*, and a bijection *f*: *A* -> *B* that satisfies the condition above. (If *X* and *Y* have the same cardinality, the definition can be simplified by fixing *A* = *X*, *B* = *Y*.)

It is known that ?_{RK} is the kernel of RK, i.e., that *U* ?_{RK}*V* if and only if *U* RK *V* and *V* RK *U*.^{[21]}

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 called a**P-point**(or**weakly selective**) if for every partition {*C*_{n}|*n*<*?*} of*?*such that ?*n*<*?*:*C*_{n}?*U*, there exists some*A*?*U*such that*A*?*C*_{n}is a finite set for each*n*. - A non-principal ultrafilter
*U*is called**Ramsey**(or**selective**) if for every partition {*C*_{n}|*n*<*?*} of*?*such that ?*n*<*?*:*C*_{n}?*U*, there exists some*A*?*U*such that*A*?*C*_{n}is a singleton set for each*n*.

It is a trivial observation that all Ramsey ultrafilters are P-points. Walter Rudin proved that the continuum hypothesis implies the existence of Ramsey ultrafilters.^{[22]}
In fact, many hypotheses imply the existence of Ramsey ultrafilters, including Martin's axiom. Saharon Shelah later showed that it is consistent that there are no P-point ultrafilters.^{[23]} Therefore, the existence of these types of ultrafilters is independent of ZFC.

P-points are called as such because they are topological P-points in the usual topology of the space of non-principal ultrafilters. The name Ramsey comes from Ramsey's theorem. To see why, one can prove that an ultrafilter is Ramsey if and only if for every 2-coloring of [*?*]^{2} there exists an element of the ultrafilter that has a homogeneous color.

An ultrafilter on ?(*?*) is Ramsey if and only if it is minimal in the Rudin-Keisler ordering of non-principal powerset ultrafilters.^{[]}

- ^
^{a}^{b}If*X*happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on ?(*X*) or an (ultra)filter just on*X*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*X*" to abbreviate "(ultra)filter of ?(*X*)". - ^
^{a}^{b}Properties 1 and 3 imply that*A*and cannot*both*be elements of*U*. **^**To see the "if" direction: If {*s*_{1},...,*s*_{n}} ?*U*, then {*s*_{1}} ?*U*, or ..., or {*s*_{n}} ?*U*by induction on*n*, using Nr.2 of the above characterization theorem. That is, some {*s*_{i}} is the principal element of*U*.**^***U*is non-principal iff it contains no finite set, i.e. (by Nr.3 of the above characterization theorem) iff it contains every cofinite set, i.e. every member of the Fréchet filter.**^**Let be a filter on that is not an ultrafilter. If is such that then has the finite intersection property (because if then if and only if ) so that by the ultrafilter lemma, there exists some ultrafilter on such that (so in particular ). It follows that ?

- ^
^{a}^{b}^{c}^{d}Davey, B. A.; Priestley, H. A. (1990).*Introduction to Lattices and Order*. Cambridge Mathematical Textbooks. Cambridge University Press. **^**Kirman, A.; Sondermann, D. (1972). "Arrow's theorem, many agents, and invisible dictators".*Journal of Economic Theory*.**5**(2): 267-277. doi:10.1016/0022-0531(72)90106-8.**^**Mihara, H. R. (1997). "Arrow's Theorem and Turing computability" (PDF).*Economic Theory*.**10**(2): 257-276. CiteSeerX 10.1.1.200.520. doi:10.1007/s001990050157. Archived from the original (PDF) on 2011-08-12Reprinted in K. V. Velupillai, S. Zambelli, and S. Kinsella, ed., Computable Economics, International Library of Critical Writings in Economics, Edward Elgar, 2011.**^**Mihara, H. R. (1999). "Arrow's theorem, countably many agents, and more visible invisible dictators".*Journal of Mathematical Economics*.**32**(3): 267-277. CiteSeerX 10.1.1.199.1970. doi:10.1016/S0304-4068(98)00061-5.**^**Halbeisen, L. J. (2012).*Combinatorial Set Theory*. Springer Monographs in Mathematics. Springer.- ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Narici & Beckenstein 2011, pp. 2-7. - ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Dugundji 1966, pp. 219-221. - ^
^{a}^{b}^{c}^{d}^{e}^{f}Schechter 1996, pp. 100-130. - ^
^{a}^{b}^{c}^{d}Bourbaki 1989, pp. 57-68. **^**Schubert 1968, pp. 48-71.**^**Higgins, Cecelia (2018). "Ultrafilters in set theory" (PDF).*math.uchicago.edu*. Retrieved 2020.**^**Kruckman, Alex (November 7, 2012). "Notes on Ultrafilters" (PDF).*math.berkeley.edu*. Retrieved 2020.- ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Dolecki & Mynard 2016, pp. 27-54. - ^
^{a}^{b}Dolecki & Mynard 2016, pp. 33-35. - ^
^{a}^{b}^{c}Bourbaki 1989, pp. 129-133. - ^
^{a}^{b}Jech 2006, pp. 73-89. **^**Leinster, Tom (2013). "Codensity and the ultrafilter monad".*Theory and Applications of Categories*.**28**: 332-370. arXiv:1209.3606. Bibcode:2012arXiv1209.3606L.**^**Bourbaki 1987, pp. 57-68.- ^
^{a}^{b}^{c}Muger, Michael (2020).*Topology for the Working Mathematician*. **^**Comfort, W. W.; Negrepontis, S. (1974).*The theory of ultrafilters*. Berlin, New York: Springer-Verlag. MR 0396267. Corollary 9.3.**^**Rudin, Walter (1956), "Homogeneity problems in the theory of ?ech compactifications",*Duke Mathematical Journal*,**23**(3): 409-419, doi:10.1215/S0012-7094-56-02337-7, hdl:10338.dmlcz/101493**^**Wimmers, Edward (March 1982), "The Shelah P-point independence theorem",*Israel Journal of Mathematics*,**43**(1): 28-48, doi:10.1007/BF02761683

- Arkhangel'skii, Alexander Vladimirovich; Ponomarev, V.I. (1984).
*Fundamentals of General Topology: Problems and Exercises*. Mathematics and Its Applications.**13**. Dordrecht Boston: D. Reidel. ISBN 978-90-277-1355-1. OCLC 9944489. - Bourbaki, Nicolas (1989) [1966].
*General Topology: Chapters 1-4*[*Topologie Générale*]. Éléments de mathématique. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-64241-1. OCLC 18588129. - Dixmier, Jacques (1984).
*General Topology*. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York: Springer-Verlag. ISBN 978-0-387-90972-1. OCLC 10277303. - Dolecki, Szymon; Mynard, Frederic (2016).
*Convergence Foundations Of Topology*. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917. - Dugundji, James (1966).
*Topology*. Boston: Allyn and Bacon. ISBN 978-0-697-06889-7. OCLC 395340485. - Császár, Ákos (1978).
*General topology*. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd. ISBN 0-85274-275-4. OCLC 4146011. - Jech, Thomas (2006).
*Set Theory: The Third Millennium Edition, Revised and Expanded*. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-44085-7. OCLC 50422939. - Joshi, K. D. (1983).
*Introduction to General Topology*. New York: John Wiley and Sons Ltd. ISBN 978-0-85226-444-7. OCLC 9218750. - Narici, Lawrence; Beckenstein, Edward (2011).
*Topological Vector Spaces*. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834. - Schechter, Eric (1996).
*Handbook of Analysis and Its Foundations*. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365. - Schubert, Horst (1968).
*Topology*. London: Macdonald & Co. ISBN 978-0-356-02077-8. OCLC 463753.

- Comfort, W. W. (1977). "Ultrafilters: some old and some new results".
*Bulletin of the American Mathematical Society*.**83**(4): 417-455. doi:10.1090/S0002-9904-1977-14316-4. ISSN 0002-9904. MR 0454893. - Comfort, W. W.; Negrepontis, S. (1974),
*The theory of ultrafilters*, Berlin, New York: Springer-Verlag, MR 0396267 - Ultrafilter in
*nLab*

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists