Difference between revisions of "Ultrafilter"
(started a page; will finish later) |
m (→Existence of Non-trivial Filters on Infinite Sets) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 10: | Line 10: | ||
== Types of Ultrafilters == | == 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''. | + | 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.''' Let <math>\mathcal{F}</math> be a trivial ultrafilter on <math>X</math>. Then there exists an element <math>a\in X</math> such that <math>\mathcal{F}</math> is the set of subsets of <math>X</math> which contain <math>a</math>. | + | '''Proposition 1.''' Let <math>\mathcal{F}</math> be a trivial ultrafilter on <math>X</math>. Then there exists an element <math>a\in X</math> such that <math>\mathcal{F}</math> is the set of subsets of <math>X</math> which contain <math>a</math>. |
''Proof.'' Let <math>A</math> be a minimal element of <math>\mathcal{F}</math>. It suffices to show that <math>A</math> contains a single element. Indeed, let <math>a</math> be an element of <math>A</math>. Since <math>\mathcal{F}</math> is an ultrafilter, one of the sets <math>\{ a\}</math>, <math>X \setminus \{a\}</math> must be an element of <math>\mathcal{F}</math>. But <math>A \not\subseteq X \setminus \{a\}</math>, so <math>\{a\}</math> must be an element of <math>\mathcal{F}</math>. Hence <math>A \subseteq \{a\}</math>, so <math>A = \{a\}</math>, as desired. <math>\blacksquare</math> | ''Proof.'' Let <math>A</math> be a minimal element of <math>\mathcal{F}</math>. It suffices to show that <math>A</math> contains a single element. Indeed, let <math>a</math> be an element of <math>A</math>. Since <math>\mathcal{F}</math> is an ultrafilter, one of the sets <math>\{ a\}</math>, <math>X \setminus \{a\}</math> must be an element of <math>\mathcal{F}</math>. But <math>A \not\subseteq X \setminus \{a\}</math>, so <math>\{a\}</math> must be an element of <math>\mathcal{F}</math>. Hence <math>A \subseteq \{a\}</math>, so <math>A = \{a\}</math>, as desired. <math>\blacksquare</math> | ||
− | Evidently, the | + | '''Proposition 2.''' An ultrafilter <math>\mathcal{F}</math> is nontrivial if and only if it contains no [[finite]] element. |
+ | |||
+ | ''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. | ||
+ | |||
+ | '''Lemma 3.''' Let <math>\mathcal{F}</math> be a filter with no finite elements on an infinite set <math>X</math>, and let <math>A</math> be a subset of <math>X</math>. Suppose that for every element <math>F</math> of <math>\mathcal{F}</math>, <math>A \cap F</math> is infinite. Then there exists a filter <math>\mathcal{F'}</math> with no finite elements on <math>X</math> such that <math>A \in \mathcal{F'}</math> and <math>\mathcal{F} \subseteq \mathcal{F'}</math>. | ||
+ | |||
+ | ''Proof.'' Let <math>\mathcal{A}</math> denote set of subsets of <math>X</math> which have subsets of the form <math>F \cap A</math>, for <math>F \in \mathcal{F}</math>. By hypothesis, <math>\mathcal{A}</math> contains no finite elements; it is therefore enough to show that <math>\mathcal{A} \cup \mathcal{F}</math> is a filter on <math>X</math>. | ||
+ | |||
+ | Evidently, the empty set is not an element of <math>\mathcal{A} \cup \mathcal{F}</math>. If <math>B</math> and <math>C</math> are sets such that <math>B</math> is a subset of <math>C</math> and <math>B</math> is an element of <math>\mathcal{A} \cup \mathcal{F}</math>, then either <math>B</math> is an element of <math>\mathcal{F}</math> and so is <math>C</math>; or <math>B</math> has a subset of the form <math>A \cup F</math>, for some <math>F \in \mathcal{F}</math>, and so does <math>C</math>. Either way, <math>C</math> is an element of <math>\mathcal{A} \cup \mathcal{F}</math>. | ||
+ | |||
+ | Finally, suppose <math>B</math> and <math>C</math> are elements of <math>\mathcal{A} \cup \mathcal{F}</math>. If they are both elements of <math>\mathcal{F}</math>, then <math>B\cap C</math> is in <math>F</math>. Suppose one, say <math>B</math>, is an element of <math>\mathcal{F}</math>, and the other is an element of <math>\mathcal{A}</math>. Then <math>B \cap C</math> has a subset of the form <math>A \cap (F \cap B)</math>, for some <math>F \in \mathcal{F}</math>; since <math>F \cap B</math> is an element of <math>\mathcal{F}</math>, <math>B \cap C</math> is an element of <math>\mathcal{A}</math>. If <math>B</math> and <math>C</math> are elements of <math>\mathcal{A}</math>, then <math>B \cap C</math> has a subset of the form <math>(A \cap F_B) \cap (A \cap F_C) = A \cap (F_B \cap F_C)</math>; since <math>F_B \cap F_C</math> is in <math>\mathcal{F}</math>, it follows that <math>B\cap C</math> is in <math>\mathcal{A}</math>. In any case, <math>B \cap C</math> is an element of <math>\mathcal{A} \cup \mathcal{F}</math>, so <math>\mathcal{A} \cup \mathcal{F}</math> is a filter on <math>X</math>, as desired. <math>\blacksquare</math> | ||
+ | |||
+ | |||
+ | '''Lemma 4.''' Let <math>X</math> be an infinite set, and let <math>\mathcal{F}</math> be a filter on <math>X</math> with no finite elements. Then there exists a nontrivial ultrafilter <math>\mathcal{F'}</math> on <math>X</math> such that <math>\mathcal{F} \subseteq \mathcal{F'}</math>. | ||
+ | |||
+ | ''Proof.'' Let <math>\mathfrak{F}</math> be the family of filters on <math>X</math> that contain <math>\mathcal{F}</math> and have no finite elements. Evidently, every totally ordered subfamily of <math>\mathfrak{F}</math> has an upper bound, so by [[Zorn's Lemma]], <math>\mathfrak{F}</math> has a maximal element <math>\mathcal{F'}</math>. Since <math>\mathcal{F'}</math> is a filter on <math>X</math> with no finite elements, it suffices to show that for any set <math>A \subset X</math>, either <math>A</math> or <math>X \setminus A</math> is an element of <math>\mathcal{F'}</math>. | ||
+ | |||
+ | We first prove that one of the sets <math>A, X \setminus A</math> has infinite intersection with every element of <math>\mathcal{F'}</math>. Indeed, suppose this is not the case. Then there exist <math>B, C \in \mathcal{F'}</math> such that <math>B \cup A</math> and <math>C \cap (X \setminus A)</math> are both finite. Evidently <math>B\cap C</math> is an element of <math>\mathcal{F'}</math>, but | ||
+ | <cmath> B \cap C = (B \cap C) \cap \bigl( A \cap (X\setminus A) \bigr) = \bigl(C \cap (B \cap A) \bigr) \cup \bigl( B \cap C \cap (X \setminus A) \bigr) </cmath> | ||
+ | is finite, a contradiction. | ||
+ | |||
+ | Thus one of the sets, <math>A, X \setminus A</math> has infinite intersection with every element of <math>\mathcal{F'}</math>. Without loss of generality, let this set be <math>A</math>. Then by Lemma 3, there exists a filter <math>\mathcal{F''}</math> with no finite elements such that <math>A</math> is an element of <math>\mathcal{F''}</math> and <math>\mathcal{F'} \subseteq \mathcal{F''}</math>. But since <math>\mathcal{F'}</math> is maximal, <math>\mathcal{F' = F''}</math>. It follows that <math>A \in \mathcal{F'}</math>. | ||
+ | |||
+ | Therefore for every set <math>A \subseteq X</math>, one of the sets <math>A</math>, <math>X \setminus A</math> is an element of <math>\mathcal{F'}</math>. Therefore <math>\mathcal{F'}</math> is a nontrivial ultrafilter on <math>X</math> which contains <math>\mathcal{F}</math>, as desired. <math>\blacksquare</math> | ||
+ | |||
+ | '''Corollary 5.''' Every finest filter is an ultrafilter. | ||
+ | |||
+ | Note: The proof of Lemma 4 uses Zorn's Lemma, and it is indeed sufficient but not necessary. This is also known as the Ultrafilter lemma, which is implied by Zorn's Lemma but not equivalent to it. However, the Ultrafilter lemma cannot be proved in <math>\sf{ZF}</math> alone. | ||
+ | |||
+ | '''Theorem 6.''' If <math>\mathcal{F}</math> is a filter on a set <math>X</math>, then there exists an ultrafilter <math>\mathcal{F'}</math> on <math>X</math> such that <math>\mathcal{F} \subseteq \mathcal{F'}</math>. | ||
+ | |||
+ | ''Proof.'' If <math>\mathcal{F}</math> contains a finite set <math>A</math>, then the subsets of this set which are elements of <math>\mathcal{F}</math>, ordered by inclusion, have a least element <math>B</math>, which is therefore a subset of every element of <math>\mathcal{F}</math>. Let <math>b</math> be an element of <math>B</math>. Then the set of subsets of <math>X</math> which contain <math>b</math> constitute an ultrafilter <math>\mathcal{F'}</math> finer than <math>\mathcal{F}</math>, as desired. | ||
+ | |||
+ | If <math>\mathcal{F}</math> contains no finite set, then by Lemma 4, there is a nontrivial ultrafilter <math>\mathcal{F'}</math> on <math>X</math> that is finer than <math>\mathcal{F}</math>, as desired. <math>\blacksquare</math> | ||
+ | |||
+ | '''Theorem 7.''' Every infinite set has a nontrivial ultrafilter. | ||
+ | |||
+ | ''Proof.'' Let <math>X</math> be an infinite set. Then the set <math>\{X\}</math> is a filter on <math>X</math> with no finite element, so by Lemma 4, there is a non-trivial ultrafilter on <math>X</math> of which <math>\{X\}</math> is a subset. <math>\blacksquare</math> | ||
+ | |||
+ | == 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]]. | ||
− | |||
== See also == | == See also == |
Latest revision as of 20:28, 13 October 2019
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.
Note: The proof of Lemma 4 uses Zorn's Lemma, and it is indeed sufficient but not necessary. This is also known as the Ultrafilter lemma, which is implied by Zorn's Lemma but not equivalent to it. However, the Ultrafilter lemma cannot be proved in alone.
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.