Diagonalization Proofs and the Existence of Uncountable Sets

Many students encounter the proof that the cardinality of the power set of a set $S$ is strictly greater than the cardinality of $S$. The proof of this may at first appear somewhat contrived and lends itself to being forgotten easily. I will try to introduce the subject in a way that makes it seem more intuitive and also easier to remember.

First we consider the set $S$ of all binary sequences (strings of zeroes and ones), and we ask if $S$ is countable. It turns out that it isn't, and the most intuitive way to prove this is by contradiction. Thus, we shall suppose that $S$ is countable, pick an enumeration, and then show that there exists a binary sequence that is not in the enumeration.

Let $s_1, s_2, \ldots$ be an enumeration of $S$, and let $s_{ij}$ denote the $j$th term of the $i$th sequence.

Let $(t_k)$ be the sequence given by $t_k=0$ if $s_{kk}$=1 and $t_k=1$ if $s_{kk}=0$. By construction this is a binary sequence, and so must be in $S$, but it can't be in the above enumeration because it differs from $s_i$ in the $s_{ii}$ term.

This is our desired contradiction, and so it follows that $S$ is uncountable.

From this follows pretty easily the uncountability of the real numbers (by producing the appropriate injections and applying the Cantor-Bernstein Theorem).

In general, we have the following theorem:

Theorem. $|P(S)|>|S|$

Proof. It is fairly easy to see that $|P(S)| \geq |S|$. Suppose for contradiction that $|S| = |P(S)|$. Thus there exists a bijective function $f:S \rightarrow P(S)$. Similarly to the above argument, we will construct a set that cannot be in the range of this function. Let $A_0$ be the set consisting of all elements $n$ that satisfy $n \notin f(n)$. This is rather similar to what we did with the binary sequences - if an element is not contained in its image under $f$, we put it in the set, and otherwise we leave it out. This way our set differs from $f(n)$ for each $n$.

We thus suspect that $A_0$ cannot be in the range of $f$. Suppose it is. Then $A_0 = f(N)$ for some $N$. But then we can ask if $N\in A_0$, and we get the contradictions $N \in A_0 \rightarrow N \notin A_0$ (and vice versa).