A nice diagonalization proof

We know from Cantor’s Theorem that the cardinality of the power set $P(X)$ of a set $X$ is strictly greater than the cardinality of the set $X$, a theorem Cantor proved using a beautiful diagonal argument.

We show here how a diagonal argument can be used to prove a basic result from measure theory: a $\sigma$-field cannot be countably infinite (it is either finite or uncountably infinite). It is satisfying to have a proof echoing Cantor’s original given the similarity between the problems: a $\sigma$-field is basically a sufficiently nicely structured subset of a power set.

Definition

Let $X$ be a set, $P(X)$ its power set. A subset $\mathcal{F} \subset P(X)$ is a $\sigma$-field if and only if:

1) $X \in \mathcal{F}$,

2) $\mathcal{F}$ is closed under countable unions, and

3) $\mathcal{F}$ is closed under complementation.

An easy example of a $\sigma$-field is $\{\emptyset, X \}$. This example also shows that you can have a finite $\sigma$-field even when $X$ is uncountable.

We will also use the property that $\sigma$-fields are closed under countable intersections.

Proof setup

We will suppose for the sake of contradiction that there is a countably infinite $\sigma$-field that we will call $\mathcal{F}$.

Defining Atoms

We know at least one set containing $x$ in $\mathcal{F}$ exists for each $x$, namely $X$ itself, by property 1) of a $\sigma$-field.

We construct, for each $x \in X$, the smallest set $A_x$ in $\mathcal{F}$ containing $x$, sets that we will call “atoms”.

We do this by starting with a fixed element $x \in X$, taking every set $F$ in the $\sigma$-field $\mathcal{F}$ that contains $x$, and taking the intersection of all of those sets. In dense notation:

$$ A_x = \bigcap \{ F \in \mathcal{F} : x \in F \} $$

Crucially, the result of this intersection is itself in $\mathcal{F}$ because $\mathcal{F}$ is assumed to be countably infinite, and $\sigma$-fields are closed under countable intersections.

The atoms themselves can be of any size, even uncountable. What matters is that the number of distinct atoms is either finite or infinite. We will see that we can rule out the finite case given our assumptions and get the desired contradiction through a diagonal argument in the infinite case, but first we need some results on atoms.

> Atoms are disjoint

The atoms $A_x$ are disjoint: if $A_x \cap A_y \neq \emptyset$, then $A_x = A_y$. To see why, suppose $A_x \cap A_y \neq \emptyset$. Then we have at least one $a$ in both atoms. We must have $a$ in every set $F$ that contains $x$, since we took their intersection to create $A_x$. So $A_a \subseteq A_x$, $A_a \subseteq A_y$.

Next we need to show that $x$ and $y$ are in every set containing $a.$ Suppose for the sake of contradiction that some $F \in \mathcal{F}$ contains $a$ but not $x$. Then $x \in X \setminus F$. We have $X \setminus F \in \mathcal{F}$ from Property 3) of a $\sigma$-field (closure under complementation). Since $X \setminus F \in \mathcal{F}$ and $X \setminus F$ contains $x$, we have $A_x \subseteq X \setminus F$ because $A_x$ is the intersection of all sets containing $x$. We showed in the paragraph above that $a \in A_x$ and here that $A_x \subseteq X \setminus F$, so $a \in X \setminus F$. But we assumed $a \in F$, so $a \notin X \setminus F$, giving us our contradiction. Mutatis mutandis with $y$. We have shown that we also have $A_a \supseteq A_x$, $A_a \supseteq A_y$.

Combining the results of both paragraphs above, we have $A_a = A_x = A_y$.

> Every set in $\mathcal{F}$ is a union of atoms

We can create any $F \in \mathcal{F}$ by taking the union of the atoms containing each element $x \in F$. This union clearly contains $F$, but why could it not give something larger than $F$? Each $A_x \subseteq F$ because $F$ is one of the sets in the intersection defining $A_x$, so the union is also contained in $F$.

Case 1: Finitely many distinct atoms

Since every set in $\mathcal{F}$ is a union of atoms, and there are only finitely many ways to union finitely many atoms, $\mathcal{F}$ must be finite, contradicting our assumption that it is countably infinite.

Case 2: Infinitely many distinct atoms

If there are infinitely many distinct atoms $A_1, A_2, A_3, \ldots$, we can enumerate them as they are a subset of the (supposedly) countable $\mathcal{F}$. We can also enumerate the $F \in \mathcal{F}$.

For each $n$, we ask whether $A_n \subseteq F_n$: we look at the $n$-th atom and the $n$-th set. We then flip this relationship: we include atom $A_n$ in $D$ if and only if $A_n$ is not contained in $F_n$.

We can visualize this as a matrix where each cell records whether $A_m \subseteq F_n$. The diagonal entries (bold) get flipped to construct $D$, guaranteeing that $D$ differs from every $F_n$ at position $n$.

	$$A_1$$	$$A_2$$	$$A_3$$	$$A_4$$	$$\ldots$$
$$F_1$$	yes	no	yes	no	$$\ldots$$
$$F_2$$	yes	no	no	yes	$$\ldots$$
$$F_3$$	no	yes	yes	yes	$$\ldots$$
$$F_4$$	no	no	yes	no	$$\ldots$$

$$D$$	no	yes	no	yes	$$\ldots$$

This $D$ is in $\mathcal{F}$ because it is a countable union of atoms, each in $\mathcal{F}$. But we will show that $D \neq F_m$ for any $m$.

If $A_m \not\subseteq F_m$, then $A_m \subseteq D$ by construction and $D \neq F_m$.

If $A_m \subseteq F_m$, then $A_m$ is not part of the union defining $D$. Since atoms are disjoint, $A_m \cap D = \emptyset$. But $A_m \subseteq F_m$ and $A_m \neq \emptyset$, so $F_m$ contains elements that $D$ does not. Thus $D \neq F_m$.

We have constructed a set $D$ that is in $\mathcal{F}$ but cannot be in the enumeration of $F \in \mathcal{F}$, contradicting the assumption that $\mathcal{F}$ is countably infinite.