Filters and Ultrafilters: Examples and Counterexamples

Every member of $\mathcal F_C$ is a subset of $X$, and $X\in\mathcal F_C$ because $C\subseteq X$.

The empty set is not in $\mathcal F_C$, since $C\subseteq\emptyset$ would contradict $C\neq\emptyset$.

If $A,B\in\mathcal F_C$, then $C\subseteq A\cap B$, so $A\cap B\in\mathcal F_C$.

If $A\in\mathcal F_C$ and $A\subseteq B\subseteq X$, then $C\subseteq B$, so $B\in\mathcal F_C$.

The family $\{C\}$ is a filter base: it is nonempty, it omits $\emptyset$ because $C\neq\emptyset$, and its only pair of members has $C\subseteq C\cap C$.

Its upward closure is $\langle\{C\}\rangle=\{A\subseteq X:C\subseteq A\}=\mathcal F_C$.

If $C=\{x\}$ and $A\subseteq X$, then either $x\in A$, giving $C\subseteq A$, or $x\notin A$, giving $C\subseteq X\setminus A$.

If $C$ is not a singleton, choose $x\in C$ and $y\in C\setminus\{x\}$. Then $C\nsubseteq\{x\}$ because $y\notin\{x\}$, and $C\nsubseteq X\setminus\{x\}$ because $x\in C$.

Steps 1.1 through 1.4 verify the four axioms in [F1], so $\mathcal F_C$ is a filter on $X$.

By steps 1.5 and 1.6 and [L1], $\mathcal F_C$ is the filter generated by $\{C\}$.

If $C=\{x\}$, step 1.7 says that $\mathcal F_C$ contains one member of every complementary pair, so [L2] makes it an ultrafilter.

If $C$ is not a singleton, step 1.8 says that neither $\{x\}$ nor its complement belongs to $\mathcal F_C$, so [L2] says that $\mathcal F_C$ is not an ultrafilter.

Thus $\mathcal F_C$ is the filter generated by $\{C\}$, and it is an ultrafilter exactly when $C$ is a singleton.

The set $\{x\}$ is a nonempty singleton, and $\{x\}\subseteq A$ holds exactly when $x\in A$.

For every $A\subseteq X$, exactly one of $x\in A$ and $x\in X\setminus A$ holds.

Applying [L1] to $C=\{x\}$ shows that $\mathcal U_x$ is the filter generated by $\{\{x\}\}$ and is an ultrafilter.

Equivalently, step 1.2 verifies the complementary-pair condition of [L2] directly.

By [F1], this ultrafilter is principal, and the displayed formula identifies it as the principal ultrafilter at $x$.

The family $\mathcal B_{\mathrm{tail}}$ is nonempty because it contains $T_0=\mathbb N$, and every $T_k$ is nonempty because $k\in T_k$ by reflexivity of $\le$.

For $k,\ell\in\mathbb N$, totality gives $k\le\ell$ or $\ell\le k$; in the first case $T_\ell\subseteq T_k\cap T_\ell$, and in the second $T_k\subseteq T_k\cap T_\ell$. Thus the tails are downward directed and none is empty.

Every finite list of natural numbers has a strict upper bound: the empty list is bounded by $0$, and if $b$ strictly bounds the first $r$ entries, totality compares $b$ with the last entry $s(r)$, after which the successor of the larger one strictly bounds all $\sigma(r)$ entries; induction proves the assertion for every length $r$.

If $T_k\subseteq A$, then $\mathbb N\setminus A\subseteq k=\{0,\ldots,k-1\}$, so the complement is contained in the range of the finite identity list $i\mapsto i$ on $k$.

Let $E:=\{r+r:r\in\mathbb N\}$. For every $k$, the natural $k+k$ belongs to $E\cap T_k$, because $k\le k+k$ by the order definition with gap $k$.

For every $k$, the successor $\sigma(k+k)=k+k+1$ does not belong to $E$: if $r+r=\sigma(k+k)$, then totality gives $r\le k$ or $k<r$ after separating the equality case; in the first case addition compatibility gives $r+r\le k+k$, contradicting $k+k<\sigma(k+k)$, while in the second it gives $k+k<k+r<r+r=\sigma(k+k)$, contradicting the immediacy of the successor.

For each $k$, if $n\in T_{\sigma(k)}$ then $k<n$ by [L4], so $n\neq k$; hence $T_{\sigma(k)}\subseteq\mathbb N\setminus\{k\}$ and $\mathbb N\setminus\{k\}\in\mathcal F_{\mathrm{Fr}}$.

For every $k$, one has $k\le k+k<\sigma(k+k)$, so step 1.6 gives an element of $T_k\setminus E$.

By steps 1.1 and 1.2, $\mathcal B_{\mathrm{tail}}$ is a filter base, and [L1] makes its upward closure $\mathcal F_{\mathrm{Fr}}$ a proper filter.

Conversely, if $\mathbb N\setminus A$ is contained in the range of a finite list, choose a strict upper bound $k$ for that list by step 1.3. Then no $n\ge k$ lies in $\mathbb N\setminus A$, so $T_k\subseteq A$ and $A\in\mathcal F_{\mathrm{Fr}}$.

Steps 1.4 and 2.3 show that $A\in\mathcal F_{\mathrm{Fr}}$ exactly when $\mathbb N\setminus A$ is finite, so the tail and cofinite descriptions agree.

Steps 1.5 and 2.1 show that every tail meets both $E$ and $\mathbb N\setminus E$. Therefore neither $E$ nor its complement contains a tail, so neither belongs to $\mathcal F_{\mathrm{Fr}}$.

Since $\mathcal F_{\mathrm{Fr}}$ contains neither member of the complementary pair $E,\mathbb N\setminus E$, [L2] shows that it is not an ultrafilter. Together with step 2.2, this proves that the Fréchet filter is proper but not ultra.

Let $\mathcal U$ be an arbitrary ultrafilter on $\mathbb N$ with $\mathcal F_{\mathrm{Fr}}\subseteq\mathcal U$; at least one such $\mathcal U$ exists by applying [L2] to $\mathcal F_{\mathrm{Fr}}$.

For every $n\in\mathbb N$, the set $\mathbb N\setminus\{n\}$ lies in $\mathcal U$.

By [L3], step 2.1 forces $\{n\}\notin\mathcal U$ for every $n\in\mathbb N$.

A principal ultrafilter at $n$ contains $\{n\}$, so step 3.1 shows that $\mathcal U$ is not principal and hence is free.

Since $\mathcal U$ was arbitrary, every ultrafilter extending the Fréchet filter is free, and step 1.1 supplies one by the ultrafilter lemma, with the choice cost stated in [L2].

By [L1], there is an index $i\in n$ with $s(i)\in\mathcal U$.

If distinct indices $i,j\in n$ both satisfied $s(i),s(j)\in\mathcal U$, then pairwise disjointness and intersection closure would give $\emptyset=s(i)\cap s(j)\in\mathcal U$, contradicting properness.

This selected cell is nonempty, because $s(i)=\emptyset$ would put $\emptyset$ in the proper filter $\mathcal U$.

Step 1.1 gives existence and step 1.2 gives uniqueness, while step 2.1 shows the selected cell is nonempty.

When the listed sets are nonempty and partition $X$, their union is $X\in\mathcal U$, so step 3.1 says that exactly one partition cell belongs to $\mathcal U$.

By [L1], $\mathcal U_0$ and $\mathcal U_1$ are filters on $X$.

The singleton $\{0\}$ belongs to $\mathcal U_0$ and the singleton $\{1\}$ belongs to $\mathcal U_1$, so both belong to $\mathcal U_0\cup\mathcal U_1$.

The two filters are not comparable: $\{0\}\in\mathcal U_0\setminus\mathcal U_1$ and $\{1\}\in\mathcal U_1\setminus\mathcal U_0$. Hence [L2] does not apply, and the example shows why its chain hypothesis is essential.

Neither principal ultrafilter contains $\emptyset$, so $\emptyset\notin\mathcal U_0\cup\mathcal U_1$.

If $\mathcal U_0\cup\mathcal U_1$ were a filter, intersection closure applied to $\{0\}$ and $\{1\}$ would put $\emptyset=\{0\}\cap\{1\}$ in the union, contradicting step 2.1. Thus the union is not a filter.

Therefore an arbitrary union of two filters, even two principal ultrafilters, need not be a filter.

By [L1], $\mathcal U_0$ and $\mathcal U_1$ are ultrafilters on $X$.

A subset $A\subseteq X$ lies in $\mathcal U_0\cap\mathcal U_1$ exactly when it contains both $0$ and $1$, which on this two-point set holds exactly when $A=X$. Thus $\mathcal U_0\cap\mathcal U_1=\{X\}$.

The family $\{X\}$ is a filter: it contains $X$, omits $\emptyset$, its only pairwise intersection is $X$, and its only superset inside $X$ is $X$.

Neither $\{0\}$ nor its complement $\{1\}$ belongs to $\{X\}$, so [L2] shows that this filter is not an ultrafilter.

Hence $\mathcal U_0\cap\mathcal U_1$ is a filter but not an ultrafilter, refuting the claim.

The family $\mathcal P(X)$ is a weak filter: it contains $X$ and $\emptyset$, and it is closed under intersections and under taking supersets inside $X$.

If a weak filter $\mathcal G$ contains $\emptyset$, then for every $A\subseteq X$ the inclusions $\emptyset\subseteq A\subseteq X$ and upward closure give $A\in\mathcal G$. Hence $\mathcal G=\mathcal P(X)$.

Thus $\mathcal P(X)$ is the unique improper weak filter. Since every weak filter is a subfamily of $\mathcal P(X)$, it is also the greatest and therefore the unique maximal weak filter.

If maximality were taken in the enlarged class, no proper filter could be maximal because it would be strictly contained in $\mathcal P(X)$. This differs from [F2] and refutes the claim that dropping properness leaves ultrafilters unchanged.