Difference between revisions of "Ultrafilter"
(finished) |
m |
||
Line 20: | Line 20: | ||
''Proof.'' By Proposition 1, if <math>\mathcal{F}</math> is trivial, it contains a finite element. Converesly, suppose <math>\mathcal{F}</math> contains a finite element <math>A</math>. Then the set of subsets of <math>A</math> which are elements of <math>\mathcal{F}</math>, ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of <math>\mathcal{F}</math>, so <math>\mathcal{F}</math> is trivial. <math>\blacksquare</math> | ''Proof.'' By Proposition 1, if <math>\mathcal{F}</math> is trivial, it contains a finite element. Converesly, suppose <math>\mathcal{F}</math> contains a finite element <math>A</math>. Then the set of subsets of <math>A</math> which are elements of <math>\mathcal{F}</math>, ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of <math>\mathcal{F}</math>, so <math>\mathcal{F}</math> is trivial. <math>\blacksquare</math> | ||
− | == | + | == Existence of Non-trivial Filters on Infinite Sets == |
We will now show that every [[infinite]] set has a non-trivial ultrafilter. | We will now show that every [[infinite]] set has a non-trivial ultrafilter. |
Revision as of 22:57, 9 April 2008
An ultrafilter is a set theoretic structure.
Contents
Definition
An ultrafilter on a set is a non-empty filter
on
with the following property:
- For every set
, either
or its complement is an element of
.
An ultrafilter is a finest filter, that is, if is an ultrafilter on
, then there is no filter
on
such that
. All finest filters are also ultrafilters; we will prove this later.
Types of Ultrafilters
An ultrafilter is said to be principle, or fixed, or trivial if it has a least element, i.e., an element which is a subset of all the others. Otherwise, an ultrafilter is said to be nontrivial, or free, or non-principle. Evidently, the only filters on finite sets are trivial.
Proposition 1. Let be a trivial ultrafilter on
. Then there exists an element
such that
is the set of subsets of
which contain
.
Proof. Let be a minimal element of
. It suffices to show that
contains a single element. Indeed, let
be an element of
. Since
is an ultrafilter, one of the sets
,
must be an element of
. But
, so
must be an element of
. Hence
, so
, as desired.
Proposition 2. An ultrafilter is nontrivial if and only if it contains no finite element.
Proof. By Proposition 1, if is trivial, it contains a finite element. Converesly, suppose
contains a finite element
. Then the set of subsets of
which are elements of
, ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of
, so
is trivial.
Existence of Non-trivial Filters on Infinite Sets
We will now show that every infinite set has a non-trivial ultrafilter.
Lemma 3. Let be a filter with no finite elements on an infinite set
, and let
be a subset of
. Suppose that for every element
of
,
is infinite. Then there exists a filter
with no finite elements on
such that
and
.
Proof. Let denote set of subsets of
which have subsets of the form
, for
. By hypothesis,
contains no finite elements; it is therefore enough to show that
is a filter on
.
Evidently, the empty set is not an element of . If
and
are sets such that
is a subset of
and
is an element of
, then either
is an element of
and so is
; or
has a subset of the form
, for some
, and so does
. Either way,
is an element of
.
Finally, suppose and
are elements of
. If they are both elements of
, then
is in
. Suppose one, say
, is an element of
, and the other is an element of
. Then
has a subset of the form
, for some
; since
is an element of
,
is an element of
. If
and
are elements of
, then
has a subset of the form
; since
is in
, it follows that
is in
. In any case,
is an element of
, so
is a filter on
, as desired.
Lemma 4. Let be an infinite set, and let
be a filter on
with no finite elements. Then there exists a nontrivial ultrafilter
on
such that
.
Proof. Let be the family of filters on
that contain
and have no finite elements. Evidently, every totally ordered subfamily of
has an upper bound, so by Zorn's Lemma,
has a maximal element
. Since
is a filter on
with no finite elements, it suffices to show that for any set
, either
or
is an element of
.
We first prove that one of the sets has infinite intersection with every element of
. Indeed, suppose this is not the case. Then there exist
such that
and
are both finite. Evidently
is an element of
, but
is finite, a contradiction.
Thus one of the sets, has infinite intersection with every element of
. Without loss of generality, let this set be
. Then by Lemma 3, there exists a filter
with no finite elements such that
is an element of
and
. But since
is maximal,
. It follows that
.
Therefore for every set , one of the sets
,
is an element of
. Therefore
is a nontrivial ultrafilter on
which contains
, as desired.
Corollary 5. Every finest filter is an ultrafilter.
Theorem 6. If is a filter on a set
, then there exists an ultrafilter
on
such that
.
Proof. If contains a finite set
, then the subsets of this set which are elements of
, ordered by inclusion, have a least element
, which is therefore a subset of every element of
. Let
be an element of
. Then the set of subsets of
which contain
constitute an ultrafilter
finer than
, as desired.
If contains no finite set, then by Lemma 4, there is a nontrivial ultrafilter
on
that is finer than
, as desired.
Theorem 7. Every infinite set has a nontrivial ultrafilter.
Proof. Let be an infinite set. Then the set
is a filter on
with no finite element, so by Lemma 4, there is a non-trivial ultrafilter on
of which
is a subset.
Examples and Applications
Ultrafilters are used in topology. They are also used to construct the hyperreals, which lie at the foundations of non-standard analysis.
Examples of non-trivial ultrafilters are difficult (if not impossible) to give, as the only known proof of their existance relies on the Axiom of Choice.