Ultrafilter: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
en>Theorist2
(→‎Applications: Removed a joke.)
 
en>Arthur Rubin
(Reverted good faith edits by Crasshopper (talk): Remove categorization of axioms; seems misleading to me. Discuss? (TW))
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
In the [[mathematics|mathematical]] field of [[set theory]], an '''ultrafilter''' on a set ''X'' is a collection of [[subset]]s of ''X'' that is a [[filter (mathematics)|filter]], that cannot be enlarged (as a filter). An ultrafilter may be considered as a [[finitely additive]] [[measure (mathematics)|measure]]. 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 [[Complement (set theory)|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 algebra (structure)|Boolean algebra]]s or even to general [[partial order]]s, and has many applications in set theory, [[model theory]], and [[topology]].
{{confusing|date=September 2014}}


==Formal definition==
In the [[mathematics|mathematical]] field of [[set theory]], an '''ultrafilter''' is a [[maximal element|maximal]] [[filter (mathematics)|filter]], that is, a filter that cannot be enlarged. Filters and ultrafilters are special subsets of [[partially ordered set|partially ordered sets]]. Ultrafilters can also be defined on [[Boolean algebras]] and [[set (mathematics)|sets]]:
 
* An ultrafilter on a poset ''P'' is a maximal filter on ''P''.
* An ultrafilter on a Boolean algebra ''B'' is an ultrafilter on the poset of non-zero elements of ''B''.
* An ultrafilter on a set ''X'' is an ultrafilter on the Boolean algebra of subsets of ''X''.
 
Rather confusingly, an ultrafilter on a poset ''P'' or Boolean algebra ''B'' is a subset of ''P'' or ''B'', while an ultrafilter on a set ''X'' is a collection of subsets of ''X''. Ultrafilters have many applications in set theory, [[model theory]], and [[topology]].
 
An ultrafilter on a set ''X'' has some special properties. For example, given any subset ''A'' of ''X'', the ultrafilter must contain either ''A'' or its [[relative complement|complement]] {{nowrap|''X'' \ ''A''}}. In addition, an ultrafilter on a set ''X'' may be considered as a [[finitely additive]] [[measure (mathematics)|measure]]. In this view, every subset of ''X'' is either considered "[[Almost everywhere|almost everything]]" (has measure 1) or "almost nothing" (has measure 0).
 
==Formal definition for ultrafilter on a set ==
Given a set ''X'', an ultrafilter on ''X'' is a set ''U'' consisting of subsets of ''X'' such that
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''
#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 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 (set theory)|intersection]] of ''A'' and ''B''.
#If ''A'' and ''B'' are elements of ''U'', then so is the [[Intersection (set theory)|intersection]] of ''A'' and ''B''.
#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''.)
#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 {{nowrap|''X'' \ ''A''}} cannot ''both'' be elements of ''U''.)


A characterization is given by the following theorem.
A characterization is given by the following theorem.
A [[filter (mathematics)|filter]] ''U'' on a set ''X'' is an ultrafilter if any of the following conditions are true:
A [[filter (mathematics)|filter]] ''U'' on a set ''X'' is an ultrafilter if any of the following conditions are true:
#There is no filter ''F'' finer than ''U'', i.e. <math>U\subseteq F</math> implies ''U'' = ''F''.
#There is no filter ''F'' [[Filter (mathematics)#Filter on a set|finer]] than ''U'', i.e., <math>U\subseteq F</math> implies ''U'' = ''F''.
#<math>A\cup B\in U</math> implies <math>A\in U</math> or <math>B\in U</math>.
#<math>A\cup B\in U</math> implies <math>A\in U</math> or <math>B\in U</math>.
#<math>\forall A\subseteq X\colon A\in U</math> or <math>X\setminus A \in U</math>.
#<math>\forall A\subseteq X\colon A\in U</math> or <math>X\setminus A \in U</math>.
 
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. Note that this does not define a [[measure (mathematics)|measure]] 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''&nbsp;∈&nbsp;''F'' and ''m''(''A'') = 0 if ''X'' \ ''A''&nbsp;∈&nbsp;''F'', leaving ''m'' undefined elsewhere.
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. Such a function is called a [[2-valued morphism]]. 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. Note that this does not define a [[measure (mathematics)|measure]] in the usual sense, which is required to be ''countably additive''.


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


A simple example of an ultrafilter is a ''principal ultrafilter'', which consists of subsets of ''X'' that contain a given element ''x'' of ''X''. All ultrafilters on a finite set are principal.


==Completeness==<!-- This section is linked from [[Martin measure]] -->
==Completeness==<!-- This section is linked from [[Martin measure]] -->
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 an ultrafilter ''U'' on a set is the smallest [[Cardinal number|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 [[#Types and existence of ultrafilters|nonprincipal]] ultrafilter on a set is always a [[measurable cardinal]].
The completeness of a countably complete [[#Types and existence of ultrafilters|nonprincipal]] ultrafilter on a set is always a [[measurable cardinal]].


==Generalization to partial orders==
==Generalization to partial orders==
In [[order theory]], an '''ultrafilter''' is a [[subset]] of a [[partially ordered set]] (a ''poset'') which is [[maximal element|maximal]] among all [[proper filter]]s. 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 (structure)|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'').
In [[order theory]], an '''ultrafilter''' is a [[subset]] of a [[partially ordered set]] (a ''poset'') that is [[maximal element|maximal]] among all [[filter (mathematics)#General definition|proper filter]]s. Formally, this states that any filter that properly contains an ultrafilter has to be equal to the whole poset.
 
==Special case: Boolean algebra==
An important special case of the concept occurs if the considered poset is a [[Boolean algebra (structure)|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 algebra#Nonmonotone laws|Boolean complement]] of ''a'').


Ultrafilters on a Boolean algebra can be identified with [[prime ideal]]s, [[maximal ideal]]s, and homomorphisms to  
Ultrafilters on a Boolean algebra can be identified with [[ideal (order theory)#Prime ideals|prime ideal]]s, [[maximal ideal]]s, and [[homomorphism]]s to the 2-element Boolean algebra {true, false}, as follows:
the 2-element Boolean algebra {true, false}, as follows:
*Maximal ideals of a Boolean algebra are the same as prime ideals.
*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 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.
Line 35: Line 47:
*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".
*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<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:
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<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>
: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: the sign <math>\vee</math> denotes the join operation of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in.<ref>[http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra] (written by [http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar), Corollary 3.13 on p. 149.</ref>
(To avoid confusion: the sign <math>\vee</math> denotes the join operation of the Boolean algebra, and logical connectives are rendered by English circumlocutions.) See details (and proof) in.<ref>[http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra] (written by [http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar), Corollary 3.13 on p. 149.</ref>


== Types and existence of ultrafilters ==
== 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''<sub>''a''</sub> = {''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 ultrafilters 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 that is not principal is called a '''free''' (or '''non-principal''') ultrafilter.


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''<sub>''a''</sub> = {''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.
Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the [[Fréchet filter]] of [[cofinite subset]]s of S. This is obvious, since a non-principal ultrafilter contains no finite set, it means that, by taking complements, it contains all cofinite subsets of S, which is exactly the Fréchet filter.
 
Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the [[Fréchet filter]] of cofinite subsets of S. This is obvious, since a non-principal ultrafilter contains no finite set, it means that, by taking complements, it contains all cofinite subsets of S, which is exactly the Fréchet filter.
 
One can show that every filter of 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]] 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). 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 ==
One can show that every filter of 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). 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]], especially in relation to [[Compact space|compact]] [[Hausdorff space|Hausdorff]] spaces, and in [[model theory]] in the construction of [[ultraproduct|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 filter]]s. Ultrafilters in this form play a central role in [[Stone's representation theorem for Boolean algebras]].
Ultrafilters on sets are useful in [[topology]], especially in relation to [[Compact space|compact]] [[Hausdorff space|Hausdorff]] spaces, and in [[model theory]] in the construction of [[ultraproduct|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 filter]]s. 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''<sub>''a''</sub> = {''U'' ∈ ''G'' | ''a'' ∈ ''U''}. This is most useful when ''P'' is again a Boolean algebra, since in this situation the set of all ''D''<sub>''a''</sub> 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''|.
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''<sub>''a''</sub> = {''U'' ∈ ''G'' | ''a'' ∈ ''U''}. This is most useful when ''P'' is again a Boolean algebra, since in this situation the set of all ''D''<sub>''a''</sub> 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''|.


The [[ultraproduct]] construction in model theory uses ultrafilters to produce [[elementary extension]]s of structures. For example, in constructing [[hyperreal number]]s as an ultraproduct of the [[real numbers]], we first extend the [[domain of discourse]] 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]]. If ''U'' is nonprincipal, then the extension thereby obtained is nontrivial.
The [[ultraproduct]] construction in [[model theory]] uses ultrafilters to produce [[elementary extension]]s of structures. For example, in constructing [[hyperreal number]]s as an ultraproduct of the [[real numbers]], we first extend the [[domain of discourse]] 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]]. If ''U'' is nonprincipal, then the extension thereby obtained is nontrivial.


In [[geometric group theory]], non-principal ultrafilters are used to define the [[ultralimit#Asymptotic cones|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]]s of [[metric space]]s.
In [[geometric group theory]], non-principal ultrafilters are used to define the [[ultralimit#Asymptotic cones|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 [[ultralimit]]s of [[metric space]]s.


[[Gödel's ontological proof]] of God's existence uses as an axiom that the set of all "positive properties" is an ultrafilter.
[[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
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
(e.g., Kirman and Sondermann, 1972<ref>{{cite doi | 10.1016/0022-0531(72)90106-8}}</ref>).
(e.g., Kirman and Sondermann, 1972<ref>{{cite doi | 10.1016/0022-0531(72)90106-8}}</ref>).
Mihara (1997,<ref name=mihara97>{{cite doi|10.1007/s001990050157}}</ref> 1999<ref name=mihara99>{{cite doi | 10.1016/S0304-4068(98)00061-5}}</ref>)
Mihara (1997,<ref name=mihara97>{{cite doi|10.1007/s001990050157}}</ref> 1999<ref name=mihara99>{{cite doi | 10.1016/S0304-4068(98)00061-5}}</ref>)
shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.
shows, however, such rules are practically of limited interest to social scientists, since they are non-algorithmic or non-computable.


== Ordering on ultrafilters ==
==Ordering on ultrafilters==
'''Rudin–Keisler ordering''' is a [[preorder]] on the class of ultrafilters defined as follows: if ''U'' is an ultrafilter on ''X'', and ''V'' an ultrafilter on ''Y'', then <math>V\le_{RK}U</math> if and only if there exists a function ''f'': ''X'' → ''Y'' such that
'''Rudin–Keisler ordering''' is a [[preorder]] on the class of ultrafilters defined as follows: if ''U'' is an ultrafilter on ''X'', and ''V'' an ultrafilter on ''Y'', then <math>V\le_{RK}U</math> if and only if there exists a function ''f'': ''X'' → ''Y'' such that
:<math>C\in V\iff f^{-1}[C]\in U</math>
:<math>C\in V\iff f^{-1}[C]\in U</math>
for every subset ''C'' of ''Y''.
for every subset ''C'' of ''Y''.


Ultrafilters ''U'' and ''V'' are '''Rudin–Keisler equivalent''', <math>U\equiv_{RK}V</math>, if there exist sets <math>A\in U</math>, <math>B\in V</math>, and a [[bijection]] ''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''.)
Ultrafilters ''U'' and ''V'' are '''Rudin–Keisler equivalent''', <math>U\equiv_{RK}V</math>, if there exist sets <math>A\in U</math>, <math>B\in V</math>, 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 <math>\equiv_{RK}</math> is the kernel of <math>\le_{RK}</math>, i.e., <math>U\equiv_{RK}V</math> if and only if <math>U\le_{RK}V</math> and <math>V\le_{RK}U</math>.
It is known that <math>\equiv_{RK}</math> is the [[kernel (set theory)|kernel]] of <math>\le_{RK}</math>, i.e., <math>U\equiv_{RK}V</math> if and only if <math>U\le_{RK}V</math> and <math>V\le_{RK}U</math>.


== Ultrafilters on ''ω'' ==
==Ultrafilters on ''ω''==
There are several special properties that an ultrafilter on ''ω'' may possess, which prove useful in various areas of set theory and topology.
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 of a set|partition]] of ''ω'', <math>\{ C_n\mid n<\omega \}</math> such that <math>C_n\not\in U,\forall n<\omega</math>, there exists <math>A\in U</math> such that <math>|A\cap C_n|<\omega,\forall n<\omega</math>.
* A non-principal ultrafilter ''U'' is a '''P-point''' (or '''weakly selective''') iff for every [[partition of a set|partition]] of ''ω'', <math>\{ C_n\mid n<\omega \}</math> such that <math>C_n\not\in U,\forall n<\omega</math>, there exists <math>A\in U</math> such that <math>|A\cap C_n|<\omega,\forall n<\omega</math>.
Line 116: Line 126:
   10.1007/BF02761683  
   10.1007/BF02761683  
   | accessdate = }}
   | accessdate = }}
</ref>  
</ref> Therefore the existence of these types of ultrafilters is [[independence (mathematical logic)|independent]] of [[ZFC]].
Therefore the existence of these types of ultrafilters is [[independence (mathematical logic)|independent]] of [[ZFC]].  


P-points are called as such because they are topological [[P-point]]s in the usual topology of the space [[Stone–Čech compactification|{{nowrap|βω \ ω}}]] 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 <math>[\omega]^2</math> there exists an element of the ultrafilter which has a homogeneous color.
P-points are called as such because they are topological [[P-point]]s in the usual topology of the space [[Stone–Čech compactification|{{nowrap|βω \ ω}}]] 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 <math>[\omega]^2</math> there exists an element of the ultrafilter that has a homogeneous color.


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


== See also ==
==See also==
* [[Hyperreal number]]
* [[Universal net]]
* [[Universal net]]


== Notes ==
==Notes==
<references/>
<references/>


==References==
==References==
*{{Citation | last1=Comfort | first1=W. W. | title=Ultrafilters: some old and some new results | url=http://www.ams.org/bull/1977-83-04/S0002-9904-1977-14316-4/home.html | doi=10.1090/S0002-9904-1977-14316-4 | mr=0454893 | year=1977 | journal=[[Bulletin of the American Mathematical Society]] | issn=0002-9904 | volume=83 | issue=4 | pages=417–455}}
*{{Citation | last1=Comfort | first1=W. W. | title=Ultrafilters: some old and some new results | url=http://www.ams.org/bull/1977-83-04/S0002-9904-1977-14316-4/home.html | doi=10.1090/S0002-9904-1977-14316-4 | mr=0454893 | year=1977 | journal=[[Bulletin of the American Mathematical Society]] | issn=0002-9904 | volume=83 | issue=4 | pages=417–455}}
*{{Citation | last1=Comfort | first1=W. W. | last2=Negrepontis | first2=S. | title=The theory of ultrafilters | publisher=[[Springer-Verlag]] | location=Berlin, New York | mr=0396267 | year=1974}}
*{{Citation | last1=Comfort | first1=W. W. | last2=Negrepontis | first2=S. | title=The theory of ultrafilters | publisher=[[Springer-Verlag]] | location=Berlin, New York | mr=0396267 | year=1974}}


[[Category:Order theory]]
[[Category:Order theory]]
[[Category:Set families]]
[[Category:Set families]]
[[Category:Non-standard analysis]]
[[Category:Non-standard analysis]]
[[cs:Ultrafiltr]]
[[de:Ultrafilter]]
[[es:Ultrafiltro]]
[[fr:Ultrafiltre]]
[[it:Ultrafiltro]]
[[kk:Ультрасүзгі]]
[[pt:Ultrafiltro]]
[[ru:Ультрафильтр]]
[[sv:Ultrafilter]]
[[uk:Ультрафільтр (математика)]]
[[zh:超滤子]]

Latest revision as of 06:09, 25 December 2014

{{ safesubst:#invoke:Unsubst||$N=Confusing |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}

In the mathematical field of set theory, an ultrafilter is a maximal filter, that is, a filter that cannot be enlarged. Filters and ultrafilters are special subsets of partially ordered sets. Ultrafilters can also be defined on Boolean algebras and sets:

  • An ultrafilter on a poset P is a maximal filter on P.
  • An ultrafilter on a Boolean algebra B is an ultrafilter on the poset of non-zero elements of B.
  • An ultrafilter on a set X is an ultrafilter on the Boolean algebra of subsets of X.

Rather confusingly, an ultrafilter on a poset P or Boolean algebra B is a subset of P or B, while an ultrafilter on a set X is a collection of subsets of X. Ultrafilters have many applications in set theory, model theory, and topology.

An ultrafilter on a set X has some special properties. For example, given any subset A of X, the ultrafilter must contain either A or its complement X \ A. In addition, an ultrafilter on a set X may be considered as a finitely additive measure. In this view, every subset of X is either considered "almost everything" (has measure 1) or "almost nothing" (has measure 0).

Formal definition for ultrafilter on a set

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 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 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. Such a function is called a 2-valued morphism. 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. Note that this does not define a measure in the usual sense, which is required to be countably additive.

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.

A simple example of an ultrafilter is a principal ultrafilter, which consists of subsets of X that contain a given element x of X. All ultrafilters on a finite set are principal.

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.

Generalization to partial orders

In order theory, an ultrafilter is a subset of a partially ordered set (a poset) that 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.

Special case: Boolean algebra

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 the definition of the concept of “ultrafilter”. Let B denote a Boolean algebra and F a proper filter[1] 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.[2]

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 Fa = {x | ax} 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 ultrafilters 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 that is not principal is called a free (or non-principal) ultrafilter.

Note that an ultrafilter on an infinite set S is non-principal if and only if it contains the Fréchet filter of cofinite subsets of S. This is obvious, since a non-principal ultrafilter contains no finite set, it means that, by taking complements, it contains all cofinite subsets of S, which is exactly the Fréchet filter.

One can show that every filter of 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). 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, 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 above-mentioned representation theorem. For any element a of P, let Da = {UG | aU}. This is most useful when P is again a Boolean algebra, since in this situation the set of all Da 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|.

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, we first extend the domain of discourse 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. 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 (e.g., 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.

Ordering on ultrafilters

Rudin–Keisler ordering is a preorder 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: XY such that

for every subset C of Y.

Ultrafilters U and V are Rudin–Keisler equivalent, , if there exist sets , , and a bijection f: AB 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 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.

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.[6] 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.[7] 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 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 ultrafilters.

See also

Notes

  1. I.e., a filter F with the surplus restriction , i.e., being a filter that does not “degenerate” to coincide with the whole (universe of the) Boolean algebra
  2. A Course in Universal Algebra (written by Stanley N. Burris and H.P. Sankappanavar), Corollary 3.13 on p. 149.
  3. Template:Cite doi
  4. Template:Cite doi
  5. Template:Cite doi
  6. {{#invoke:citation/CS1|citation |CitationClass=citation }}
  7. {{#invoke:citation/CS1|citation |CitationClass=citation }}

References

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}