Ultrafilter

From Wikipedia, the free encyclopedia

In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that can be considered so "large" that they contain "almost all" elements of X. That description applies equally well to a filter; the new defining characteristic of an ultrafilter is that every subset of X is either considered "almost everything" or "almost nothing"; that is, 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 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, and topology.

1 Formal definition
2 Completeness
3 Generalization to partial orders
4 Types and existence of ultrafilters
5 Applications
6 Notes
7 See also

[edit] Formal definition

Given a 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, 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 A or <math>X \setminus A</math> is an element of U. (Note: axioms 1 and 3 imply that A and <math>X \setminus A</math> cannot both be elements of U.)

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 or false almost everywhere. (For non-maximal filters, one would say m(A) = 1 if A ∈ U and m(A) = 0 if X\A ∈ U, leaving m undefined elsewhere.)

[edit] 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 <math>\aleph_0</math>. An ultrafilter whose completeness is greater than <math>\aleph_0</math> — that is, the intersection of any countable collection of elements of U is still in U — is called countably complete or <math>\sigma</math>-complete.

The completeness of a countably complete nonprincipal ultrafilter on a set is always a measurable cardinal.

[edit] Generalization to partial orders

In order theory, an ultrafilter is a subset of a partially ordered set (a poset) which is maximal 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 ideals, maximal ideals, 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 definition of concept “ultrafilter”. Let B denote a Bool-algebra and F a proper filter<ref>i.e. a filter F with the surplus restriction <math>0 \notin F</math>, i.e. being a filter that does not “degenerate” to coincide with the whole (universe of) the Boolean algebra</ref> in it. F is an ultrafilter iff:

for all <math>a,b \in \mathbf B</math>, if <math>a \vee b \in F</math>, then <math>a \in f</math> or <math>b \in f</math>

(To avoid confusion: signs <math>0</math>, <math>\vee</math> are used here to denote operations of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in <ref> A Course in Universal Algebra (written by Stanley N. Burris and H.P. Sankappanavar), Corrolary 3.13 on p. 149.</ref>.

[edit] 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. Any ultrafilter which is not principal is called a free (or non-principal) ultrafilter.

One can show that every filter <ref>this statemant can be sharpened: it is enough to require the finite intersection property</ref> 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. Consequently explicit examples of free ultrafilters cannot be given. 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.

[edit] Applications

Ultrafilters on sets 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 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.

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 in G | a in 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 is the Stone-Čech compactification of a discrete space of cardinality |S|.

Ultrafilters on sets are used in the ultrapower construction of certain fields of hyperreal numbers. The idea of using ultrafilter to define total ordering on hyperreal numbers can suggest an intuitive metaphor to grasp the importance of notion ultrafilter: when transferring relations to “sequences” in a “point-wise” way, the resulting relation will “lose” some nice properties. This can be amended if we make this point-wise transferring in a more sophisticated way: we must “discriminate” positions that “matter”. Any ultrafilter can be used to “discriminate” positions that “matter”, so that the resulting relations have nicer properties. When using a principal ultrafilter, the resulting relation will coincide with one of those we started with, but when using a free ultrafilter, the construct will provide a brand-new relation. See details in article Hyperreal number.

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