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 \mathrm{\varnothing }$ would contradict $C\mathrm{\ne }\mathrm{\varnothing }$.

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 $\mathrm{\varnothing }$ because $C\mathrm{\ne }\mathrm{\varnothing }$, and its only pair of members has $C\subseteq C\cap C$.

Its upward closure is $⟨\{C\}⟩=\{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\mathrm{\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⊈\{x\}$ because $y\mathrm{\notin }\{x\}$, and $C⊈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{t}\mathrm{a}\mathrm{i}\mathrm{l}}$ 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,\mathrm{\ell }\in \mathbb{N}$, totality gives $k\le \mathrm{\ell }$ or $\mathrm{\ell }\le k$; in the first case $T_{\mathrm{\ell }}\subseteq T_k\cap T_{\mathrm{\ell }}$, and in the second $T_k\subseteq T_k\cap T_{\mathrm{\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,\dots ,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\mathrm{\ne }k$; hence $T_{\sigma (k)}\subseteq \mathbb{N}\setminus \{k\}$ and $\mathbb{N}\setminus \{k\}\in {\mathcal{F}}_{\mathrm{F}\mathrm{r}}$.

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{t}\mathrm{a}\mathrm{i}\mathrm{l}}$ is a filter base, and [L1] makes its upward closure ${\mathcal{F}}_{\mathrm{F}\mathrm{r}}$ 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{F}\mathrm{r}}$.

Steps 1.4 and 2.3 show that $A\in {\mathcal{F}}_{\mathrm{F}\mathrm{r}}$ 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{F}\mathrm{r}}$.

Since ${\mathcal{F}}_{\mathrm{F}\mathrm{r}}$ 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{F}\mathrm{r}}\subseteq \mathcal{U}$; at least one such $\mathcal{U}$ exists by applying [L2] to ${\mathcal{F}}_{\mathrm{F}\mathrm{r}}$.

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

By [L3], step 2.1 forces $\{n\}\mathrm{\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 $\mathrm{\varnothing }=s(i)\cap s(j)\in \mathcal{U}$, contradicting properness.

This selected cell is nonempty, because $s(i)=\mathrm{\varnothing }$ would put $\mathrm{\varnothing }$ 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 $\mathrm{\varnothing }$, so $\mathrm{\varnothing }\mathrm{\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 $\mathrm{\varnothing }=\{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 $\mathrm{\varnothing }$, 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 $\mathrm{\varnothing }$, and it is closed under intersections and under taking supersets inside $X$.

If a weak filter $\mathcal{G}$ contains $\mathrm{\varnothing }$, then for every $A\subseteq X$ the inclusions $\mathrm{\varnothing }\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.