Difference between revisions of "Ultrafilter"

Revision as of 21:52, 9 April 2008

An ultrafilter is a set theoretic structure.

Definition

An ultrafilter on a set $X$ is a non-empty filter $\mathcal{F}$ on $X$ with the following property:

For every set $A \subseteq X$ , either $A$ or its complement is an element of $\mathcal{F}$ .

An ultrafilter is a finest filter, that is, if $\mathcal{F}$ is an ultrafilter on $X$ , then there is no filter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subsetneq \mathcal{F'}$ . 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 $\mathcal{F}$ be a trivial ultrafilter on $X$ . Then there exists an element $a\in X$ such that $\mathcal{F}$ is the set of subsets of $X$ which contain $a$ .

Proof. Let $A$ be a minimal element of $\mathcal{F}$ . It suffices to show that $A$ contains a single element. Indeed, let $a$ be an element of $A$ . Since $\mathcal{F}$ is an ultrafilter, one of the sets $\{ a\}$ , $X \setminus \{a\}$ must be an element of $\mathcal{F}$ . But $A \not\subseteq X \setminus \{a\}$ , so $\{a\}$ must be an element of $\mathcal{F}$ . Hence $A \subseteq \{a\}$ , so $A = \{a\}$ , as desired. $\blacksquare$

Proposition 2. An ultrafilter $\mathcal{F}$ is nontrivial if and only if it contains no finite element.

Proof. By Proposition 1, if $\mathcal{F}$ is trivial, it contains a finite element. Converesly, suppose $\mathcal{F}$ contains a finite element $A$ . Then the set of subsets of $A$ which are elements of $\mathcal{F}$ , ordered by inclusion, is nonempty and finite, and must have a least element. This least element must then be a least element of $\mathcal{F}$ , so $\mathcal{F}$ is trivial. $\blacksquare$

Existance of Non-trivial Filters on Infinite Sets

We will now show that every infinite set has a non-trivial ultrafilter.

Lemma 3. Let $\mathcal{F}$ be a filter with no finite elements on an infinite set $X$ , and let $A$ be a subset of $X$ . Suppose that for every element $F$ of $\mathcal{F}$ , $A \cap F$ is infinite. Then there exists a filter $\mathcal{F'}$ with no finite elements on $X$ such that $A \in \mathcal{F'}$ and $\mathcal{F} \subseteq \mathcal{F'}$ .

Proof. Let $\mathcal{A}$ denote set of subsets of $X$ which have subsets of the form $F \cap A$ , for $F \in \mathcal{F}$ . By hypothesis, $\mathcal{A}$ contains no finite elements; it is therefore enough to show that $\mathcal{A} \cup \mathcal{F}$ is a filter on $X$ .

Evidently, the empty set is not an element of $\mathcal{A} \cup \mathcal{F}$ . If $B$ and $C$ are sets such that $B$ is a subset of $C$ and $B$ is an element of $\mathcal{A} \cup \mathcal{F}$ , then either $B$ is an element of $\mathcal{F}$ and so is $C$ ; or $B$ has a subset of the form $A \cup F$ , for some $F \in \mathcal{F}$ , and so does $C$ . Either way, $C$ is an element of $\mathcal{A} \cup \mathcal{F}$ .

Finally, suppose $B$ and $C$ are elements of $\mathcal{A} \cup \mathcal{F}$ . If they are both elements of $\mathcal{F}$ , then $B\cap C$ is in $F$ . Suppose one, say $B$ , is an element of $\mathcal{F}$ , and the other is an element of $\mathcal{A}$ . Then $B \cap C$ has a subset of the form $A \cap (F \cap B)$ , for some $F \in \mathcal{F}$ ; since $F \cap B$ is an element of $\mathcal{F}$ , $B \cap C$ is an element of $\mathcal{A}$ . If $B$ and $C$ are elements of $\mathcal{A}$ , then $B \cap C$ has a subset of the form $(A \cap F_B) \cap (A \cap F_C) = A \cap (F_B \cap F_C)$ ; since $F_B \cap F_C$ is in $\mathcal{F}$ , it follows that $B\cap C$ is in $\mathcal{A}$ . In any case, $B \cap C$ is an element of $\mathcal{A} \cup \mathcal{F}$ , so $\mathcal{A} \cup \mathcal{F}$ is a filter on $X$ , as desired. $\blacksquare$

Lemma 4. Let $X$ be an infinite set, and let $\mathcal{F}$ be a filter on $X$ with no finite elements. Then there exists a nontrivial ultrafilter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subseteq \mathcal{F'}$ .

Proof. Let $\mathfrak{F}$ be the family of filters on $X$ that contain $\mathcal{F}$ and have no finite elements. Evidently, every totally ordered subfamily of $\mathfrak{F}$ has an upper bound, so by Zorn's Lemma, $\mathfrak{F}$ has a maximal element $\mathcal{F'}$ . Since $\mathcal{F'}$ is a filter on $X$ with no finite elements, it suffices to show that for any set $A \subset X$ , either $A$ or $X \setminus A$ is an element of $\mathcal{F'}$ .

We first prove that one of the sets $A, X \setminus A$ has infinite intersection with every element of $\mathcal{F'}$ . Indeed, suppose this is not the case. Then there exist $B, C \in \mathcal{F'}$ such that $B \cup A$ and $C \cap (X \setminus A)$ are both finite. Evidently $B\cap C$ is an element of $\mathcal{F'}$ , but $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)$ is finite, a contradiction.

Thus one of the sets, $A, X \setminus A$ has infinite intersection with every element of $\mathcal{F'}$ . Without loss of generality, let this set be $A$ . Then by Lemma 3, there exists a filter $\mathcal{F''}$ with no finite elements such that $A$ is an element of $\mathcal{F''}$ and $\mathcal{F'} \subseteq \mathcal{F''}$ . But since $\mathcal{F'}$ is maximal, $\mathcal{F' = F''}$ . It follows that $A \in \mathcal{F'}$ .

Therefore for every set $A \subseteq X$ , one of the sets $A$ , $X \setminus A$ is an element of $\mathcal{F'}$ . Therefore $\mathcal{F'}$ is a nontrivial ultrafilter on $X$ which contains $\mathcal{F}$ , as desired. $\blacksquare$

Corollary 5. Every finest filter is an ultrafilter.

Theorem 6. If $\mathcal{F}$ is a filter on a set $X$ , then there exists an ultrafilter $\mathcal{F'}$ on $X$ such that $\mathcal{F} \subseteq \mathcal{F'}$ .

Proof. If $\mathcal{F}$ contains a finite set $A$ , then the subsets of this set which are elements of $\mathcal{F}$ , ordered by inclusion, have a least element $B$ , which is therefore a subset of every element of $\mathcal{F}$ . Let $b$ be an element of $B$ . Then the set of subsets of $X$ which contain $b$ constitute an ultrafilter $\mathcal{F'}$ finer than $\mathcal{F}$ , as desired.

If $\mathcal{F}$ contains no finite set, then by Lemma 4, there is a nontrivial ultrafilter $\mathcal{F'}$ on $X$ that is finer than $\mathcal{F}$ , as desired. $\blacksquare$

Theorem 7. Every infinite set has a nontrivial ultrafilter.

Proof. Let $X$ be an infinite set. Then the set $\{X\}$ is a filter on $X$ with no finite element, so by Lemma 4, there is a non-trivial ultrafilter on $X$ of which $\{X\}$ is a subset. $\blacksquare$

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.

@@ Line 10: / Line 10: @@
 == 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>
-Evidently, the only filters on finite sets are trivial.
+'''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>
+== Existance 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.
+'''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]].
-{{stub}}
 == See also ==

Page

Toolbox

Search