# Equivalence of Definitions of Ultrafilter on Set

## 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$.

### Definition 4

Let $S$ be a non-empty set.

Let $\mathcal F$ be a non-empty set of subsets of $S$.

Then $\mathcal F$ is an **ultrafilter** on $S$ if and only if both of the following hold:

- $\mathcal F$ has the finite intersection property
- For all $U \subseteq S$, either $U \in \mathcal F$ or $U^c \in \mathcal F$

where $U^c$ is the complement of $U$ in $S$.

## Proof

Let $S$ be a set.

### Equivalence of Definitions 1, 2 and 3

### 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.

$\Box$

### Definition 1 implies Definition 4

Let $\mathcal F \subseteq \mathcal P \left({S}\right)$ 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$

By definition of filter, $\mathcal F$ satisfies the Finite Intersection Property and is a non-empty set of subsets of $S$.

Let $U \subseteq S$.

Aiming for a contradiction, suppose $U \notin \mathcal F$.

Let $V = U^c$, where $U^c$ denotes the relative complement of $U$ in $S$.

Suppose there exists $C \in \mathcal F$ such that:

- $C \cap V = \varnothing$

By Empty Intersection iff Subset of Complement, it follows that:

- $C \subset U$

Thus $U \in \mathcal F$, which contradicts our hypothesis that $U \notin \mathcal F$.

Hence the set $\Omega = \left\{ {C \cap V: C \in \mathcal F}\right\}$ is a non-empty set of non-empty set.

Note that $\Omega$ is downward directed, that is, $\Omega$ is a filter basis.

From Filter Basis Generates Filter, $\Omega$ generates a filter $\mathcal G$ on $S$ that contains $\mathcal F$ and $\left\{ {V}\right\}$.

By hypothesis, we have:

- $\mathcal F =\mathcal G$

Hence $U^c = V \in \mathcal F$.

Thus $\mathcal F$ is an ultrafilter by Definition 2.

$\Box$

### Definition 4 implies Definition 1

Let $S$ be a non-empty set and $\mathcal F$ a non-empty set of subsets on $S$ which fulfills the conditions:

- $\mathcal F$ has the finite intersection property
- For all $U \subseteq S$, either $U \in S$ or $U^c \in S$.

Because $\mathcal F$ has the finite intersection property, it follows that $\varnothing \notin \mathcal F$.

As $\varnothing \notin \mathcal F$, it follows that $\varnothing^c = S \in \mathcal F$.

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

Assume that $\mathcal F \subsetneq \mathcal G$.

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

Since $\varnothing \notin \mathcal G$ this implies that $\complement_S \left({A}\right) \notin \mathcal G$.

As $\mathcal F \subsetneq \mathcal G$, it follows that $\complement_S \left({A}\right) \notin \mathcal F$.

Therefore neither $A \in \mathcal F$ nor $\complement_S \left({A}\right) \in \mathcal F$, a contradiction to our assumption.

Thus $\mathcal F = \mathcal G$, which implies that $\mathcal F$ is an ultrafilter.