Ultrafilter on a set


In the mathematical field of set theory, an ultrafilter on a set is a maximal filter on the set In other words, it is a collection of subsets of that satisfies the definition of a filter on and that is maximal with respect to inclusion, in the sense that there does not exist a strictly larger collection of subsets of that is also a filter. Equivalently, an ultrafilter on the set can also be characterized as a filter on with the property that for every subset of either or its complement belongs to the ultrafilter.
Ultrafilters on sets are an important special instance of ultrafilters on partially ordered sets, where the partially ordered set consists of the power set and the partial order is subset inclusion This article deals specifically with ultrafilters on a set and does not cover the more general notion.
There are two types of ultrafilter on a set. A principal ultrafilter on is the collection of all subsets of that contain a fixed element. The ultrafilters that are not principal are the free ultrafilters. The existence of free ultrafilters on any infinite set is implied by the ultrafilter lemma, which can be proven in ZFC. On the other hand, there exist models of ZF where every ultrafilter on a set is principal.
Ultrafilters have many applications in set theory, model theory, and topology. Usually, only free ultrafilters lead to non-trivial constructions. For example, an ultraproduct modulo a principal ultrafilter is always isomorphic to one of the factors, while an ultraproduct modulo a free ultrafilter usually has a more complex structure.

Definitions

Given an arbitrary set an ultrafilter on is a non-empty family of subsets of such that:
  1. or : The empty set is not an element of
  2. : If and if is any superset of then
  3. : If and are elements of then so is their intersection
  4. If then either or its complement is an element of
Properties,, and are the defining properties of a Some authors do not include non-degeneracy in their definition of "filter". However, the definition of "ultrafilter" always includes non-degeneracy as a defining condition. This article requires that all filters be proper although a filter might be described as "proper" for emphasis.
A filter base is a non-empty family of sets that has the finite intersection property. Equivalently, a filter subbase is a non-empty family of sets that is contained in filter. The smallest filter containing a given filter subbase is said to be generated by the filter subbase.
The upward closure in of a family of sets is the set
A ' or ' is a non-empty and proper family of sets that is downward directed, which means that if then there exists some such that Equivalently, a prefilter is any family of sets whose upward closure is a filter, in which case this filter is called the filter generated by and is said to be a filter base
The dual in of a family of sets is the set For example, the dual of the power set is itself:
A family of sets is a proper filter on if and only if its dual is a proper ideal on .

Generalization to ultra prefilters

A family of subsets of is called if and any of the following equivalent conditions are satisfied:

  1. For every set there exists some set such that or .
  2. For every set there exists some set such that equals or
    • Here, is defined to be the union of all sets in
    • This characterization of " is ultra" does not depend on the set so mentioning the set is optional when using the term "ultra."
  3. For set there exists some set such that equals or
    • If satisfies this condition then so does superset In particular, a set is ultra if and only if and contains as a subset some ultra family of sets.
A filter subbase that is ultra is necessarily a prefilter.
The ultra property can now be used to define both ultrafilters and ultra prefilters:
Ultra prefilters as maximal prefilters
To characterize ultra prefilters in terms of "maximality," the following relation is needed.
The subordination relationship, i.e. is a preorder so the above definition of "equivalent" does form an equivalence relation.
If then but the converse does not hold in general.
However, if is upward closed, such as a filter, then if and only if
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 and are equivalent then either both and are ultra or otherwise neither one of them is ultra.
In particular, if a filter subbase is not also a prefilter, then it is equivalent to the filter or prefilter that it generates. If and are both filters on then and are equivalent if and only if If a proper filter is equivalent to a family of sets then is necessarily a prefilter.
Using the following characterization, it is possible to define prefilters using only the concept of filters and subordination:

  1. is ultra.
  2. is maximal on with respect to meaning that if satisfies then
  3. There is no prefilter properly subordinate to
  4. If a filter on satisfies then
  5. The filter on generated by is ultra.

Characterizations

There are no ultrafilters on the empty set, so it is henceforth assumed that is nonempty.
A filter base on is an ultrafilter on if and only if any of the following equivalent conditions hold:

  1. for any either or
  2. is a maximal filter subbase on meaning that if is any filter subbase on then implies
A filter on is an ultrafilter on if and only if any of the following equivalent conditions hold:

  1. is ultra;
  2. is generated by an ultra prefilter;
  3. For any subset or
    • So an ultrafilter decides for every whether is "large" or "small".
  4. For each subset either is in or is.
  5. This condition can be restated as: is partitioned by and its dual
    • The sets and are disjoint for all prefilters on
  6. is an ideal on
  7. For any finite family of subsets of , if then for some index
    • In words, a "large" set cannot be a finite union of sets none of which is large.
  8. For any if then or
  9. For any if then or .
  10. For any if and then or
  11. is a maximal filter; that is, if is a filter on such that then Equivalently, is a maximal filter if there is no filter on that contains as a proper subset.

Grills and filter-grills

If then its is the family
where may be written if is clear from context.
If is a filter then is the set of positive sets with respect to and is usually written as .
For example, and if then
If then and moreover, if is a filter subbase then
The grill is upward closed in if and only if which will henceforth be assumed. Moreover, so that is upward closed in if and only if
The grill of a filter on is called a For any is a filter-grill on if and only if is upward closed in and for all sets and if then or The grill operation induces a bijection
whose inverse is also given by If then is a filter-grill on if and only if or equivalently, if and only if is an ultrafilter on That is, a filter on is a filter-grill if and only if it is ultra. For any non-empty is both a filter on and a filter-grill on if and only if and for all the following equivalences hold:

Free or principal

If is any non-empty family of sets then the Kernel of is the intersection of all sets in
A non-empty family of sets is called:
  • ' if and ' otherwise.
  • ' if
  • ' if and is a singleton set; in this case, if then is said to be principal at
If a family of sets is fixed then is ultra if and only if some element of is a singleton set, in which case will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter is ultra if and only if is a singleton set. A singleton set is ultra if and only if its sole element is also a singleton set.
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.
Every filter on that is principal at a single point is an ultrafilter, and if in addition is finite, then there are no ultrafilters on other than these. In particular, if a set has finite cardinality then there are exactly ultrafilters on and those are the ultrafilters generated by each singleton subset of Consequently, free ultrafilters can only exist on an infinite set.

Examples, properties, and sufficient conditions

If is an infinite set then there are as many ultrafilters over as there are families of subsets of explicitly, if has infinite cardinality then the set of ultrafilters over has the same cardinality as that cardinality being
If and are families of sets such that is ultra, and then is necessarily ultra.
A filter subbase that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by to be ultra.
Suppose is ultra and is a set.
The trace is ultra if and only if it does not contain the empty set.
Furthermore, at least one of the sets and will be ultra.
If are filters on is an ultrafilter on and then there is some that satisfies
This result is not necessarily true for an infinite family of filters.
The image under a map of an ultra set is again ultra and if is an ultra prefilter then so is 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 has more than one point and if the range of consists of a single point then is an ultra prefilter on but its preimage is not ultra. Alternatively, if is a principal filter generated by a point in then the preimage of contains the empty set and so is not ultra.
The elementary filter induced by an infinite sequence, all of whose points are distinct, is an ultrafilter. If then denotes the set consisting all subsets of having cardinality and if contains at least distinct points, then is ultra but it is not contained in any prefilter. This example generalizes to any integer and also to if contains more than one element. Ultra sets that are not also prefilters are rarely used.
For every and every let If is an ultrafilter on then the set of all such that is an ultrafilter on