Equivalence of Definitions of Ultrafilter on Set/Equivalence of Definitions 1, 2 and 3

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of ultrafilter on a set $S$ are equivalent:

Definition 1

Let $S$ be a set.

Let $\mathcal F \subseteq \powerset S$ be a filter on $S$.


Then $\mathcal F$ is an ultrafilter (on $S$) if and only if:

there is no filter on $S$ which is strictly finer than $\mathcal F$

or equivalently, if and only if:

whenever $\mathcal G$ is a filter on $S$ and $\mathcal F \subseteq \mathcal G$ holds, then $\mathcal F = \mathcal G$.

Definition 2

Let $S$ be a set.

Let $\mathcal F \subseteq \mathcal P \left({S}\right)$ be a filter on $S$.


Then $\mathcal F$ is an ultrafilter (on $S$) if and only if:

for every $A \subseteq S$ and $B \subseteq S$ such that $A \cap B = \varnothing$ and $A \cup B \in \mathcal F$, either $A \in \mathcal F$ or $B \in \mathcal F$.

Definition 3

Let $S$ be a set.

Let $\mathcal F \subseteq \mathcal P \left({S}\right)$ be a filter on $S$.


Then $\mathcal F$ is an ultrafilter (on $S$) if and only if:

for every $A \subseteq S$, either $A \in \mathcal F$ or $\complement_S \left({A}\right) \in \mathcal F$

where $\complement_S \left({A}\right)$ is the relative complement of $A$ in $S$, that is, $S \setminus A$.


Proof

Let $S$ be a set.


Definition 1 implies Definition 2

Let $\mathcal F$ be an ultrafilter on $S$ by definition 1.

Thus $\mathcal F \subseteq \mathcal P \left({S}\right)$ is a filter on $S$ which fulfills the condition:

whenever $\mathcal G$ is a filter on $S$ and $\mathcal F \subseteq \mathcal G$ holds, then $\mathcal F = \mathcal G$.


Let $A \subseteq S$ and $B \subseteq S$ such that:

$A \cap B = \varnothing$
$A \cup B \in \mathcal F$


Aiming for a contradiction, suppose $A \notin \mathcal F$ and $B \notin \mathcal F$.

Consider the set $\mathcal B := \left\{{V \cap A: V \in \mathcal F}\right\} \cup \left\{{V \cap B: V \in \mathcal F}\right\}$.

This is a basis of a filter $\mathcal G$ on $S$, for which $\mathcal F \subseteq \mathcal G$ holds.


Let $U \in \mathcal F$.

\(\displaystyle A\) \(\notin\) \(\displaystyle \mathcal F\) by hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle U \cap A\) \(=\) \(\displaystyle \varnothing\) Definition of Filter: Axiom $(4)$: $U \cap A \subseteq A \implies A \in \mathcal F$
\(\displaystyle \leadsto \ \ \) \(\displaystyle U\) \(\subseteq\) \(\displaystyle \complement_S \left({A}\right)\) Empty Intersection iff Subset of Complement
\(\displaystyle B\) \(\notin\) \(\displaystyle \mathcal F\) by hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle U \cap B\) \(=\) \(\displaystyle \varnothing\) Definition of Filter: Axiom $(4)$: $U \cap B \subseteq B \implies B \in \mathcal F$
\(\displaystyle \leadsto \ \ \) \(\displaystyle U\) \(\subseteq\) \(\displaystyle \complement_S \left({B}\right)\) Empty Intersection iff Subset of Complement
\(\displaystyle \leadsto \ \ \) \(\displaystyle U\) \(\subseteq\) \(\displaystyle \complement_S \left({A}\right) \cap \complement_S \left({B}\right)\) Intersection is Largest Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle U\) \(\subseteq\) \(\displaystyle \complement_S \left({A \cup B}\right)\) De Morgan's Laws: Relative Complement of Union
\(\displaystyle \leadsto \ \ \) \(\displaystyle U \cap \left({A \cup B}\right)\) \(=\) \(\displaystyle \varnothing\) Empty Intersection iff Subset of Complement

But by definition of a filter:

$U, V \in \mathcal F \implies U \cap V \in \mathcal F$

But $\varnothing \notin \mathcal F$.

This contradicts our initial hypothesis.

Hence either:

$A \in \mathcal F$

or:

$B \in \mathcal F$

and so $\mathcal F$ fulfils the conditions to be an ultrafilter by Definition 2.

$\Box$


Definition 2 implies Definition 3

Let $\mathcal F$ be an ultrafilter on $S$ by definition 2.

That is, $\mathcal F \subseteq \mathcal P \left({S}\right)$ is a filter on $S$ which fulfills the condition:

for every $A \subseteq S$ and $B \subseteq S$ such that $A \cap B = \varnothing$ and $A \cup B \in \mathcal F$, either $A \in \mathcal F$ or $B \in \mathcal F$.


Let $A \subseteq S$.

We have:

\(\displaystyle A \cup \complement_S \left({A}\right)\) \(=\) \(\displaystyle S\) Union with Relative Complement
\(\displaystyle \leadsto \ \ \) \(\displaystyle A \cup \complement_S \left({A}\right)\) \(\in\) \(\displaystyle \mathcal F\) Definition of Filter: Axiom $(1)$: $S \in \mathcal F$
\(\displaystyle A \cap \complement_S \left({A}\right)\) \(=\) \(\displaystyle \varnothing\) Intersection with Relative Complement is Empty
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({A \in \mathcal F}\right)\) \(\lor\) \(\displaystyle \left({\complement_S \left({A}\right) \in \mathcal F}\right)\) by hypothesis: Definition of Ultrafilter by Definition 2

So $\mathcal F$ fulfils the conditions to be an ultrafilter by Definition 3.

$\Box$


Definition 3 implies Definition 1

Let $\mathcal F$ be an ultrafilter on $S$ by definition 3.

That is, $\mathcal F \subseteq \mathcal P \left({S}\right)$ is a filter on $S$ which fulfills the condition:

for any $A \subseteq S$ either $A \in \mathcal F$ or $\complement_S \left({A}\right) \in \mathcal F$ holds.


Let $\mathcal G$ be a filter on $X$ such that $\mathcal F \subseteq \mathcal G$.

Aiming for a contradiction, suppose $\mathcal F \subsetneq \mathcal G$.

Then there exists $A \in \mathcal G \setminus \mathcal F$.

By definition of filter, $\varnothing \notin \mathcal G$.

But from Intersection with Relative Complement is Empty:

$A \cap \complement_S \left({A}\right)$

and so:

$\complement_S \left({A}\right) \notin \mathcal G$


By hypothesis:

$\mathcal F \subsetneq \mathcal G$

and so:

$\complement_S \left({A}\right) \notin \mathcal F$

Therefore neither $A \in \mathcal F$ nor $\complement_S \left({A}\right) \in \mathcal F$.

This contradicts our assumption:

for any $A \subseteq S$ either $A \in \mathcal F$ or $\complement_S \left({A}\right) \in \mathcal F$ holds.

Thus:

$\mathcal F = \mathcal G$

and so $\mathcal F$ fulfils the conditions to be an ultrafilter by Definition 1.

$\blacksquare$