Cantor's diagonal argument

Now consider the special case $S={\mathbb{N}}$. For convenience of notation, we may represent a function $f: {\mathbb{N}}\rightarrow \{0,1\}$ by a sequence of binary digits. For example, $1011101\cdots$ corresponds to the function $f$ such that $f(0)=1$, $f(1)=0$, $f(2)=1$, $f(3)=1$, $f(4)=1$, $f(5)=0$, $f(6)=1$, and so on.

Lemma 5   There is no bijection between ${\mathbb{N}}$ and the set $\{0,1\}^{\mathbb{N}}$ of functions $f: {\mathbb{N}}\rightarrow \{0,1\}$.

Proof. The proof is by contradiction. Suppose, there is such a bijection, such as

$$0 \longrightarrow {\mathbf 1}011101\cdots$$

$$1 \longrightarrow 0{\mathbf 0}11010\cdots$$

$$2 \longrightarrow 11{\mathbf 0}0011\cdots$$

$$3 \longrightarrow 001{\mathbf 1}111\cdots$$

$$4 \longrightarrow 1110{\mathbf 1}01\cdots$$

$$5 \longrightarrow 10000{\mathbf 1}0\cdots$$

$$6 \longrightarrow 101011{\mathbf 0}\cdots$$

$$\vdots$$
Then

$$0110001\cdots$$

where the final sequence has been obtained by complementing the binary digits of the (highlighted) diagonal sequence, will not be in the list, since that last sequence differs from each sequence in the list at least in the highlighted digit. This contradicts the assumption that the mapping was a bijection. $\qedsymbol$

Theorem 6   $\aleph_0 < 2^{\aleph_0}$.

Proof. There exists an injection ${\mathbb{N}}\rightarrow \{0,1\}^{\mathbb{N}}$, for instance

$$0 \longrightarrow 1000000\cdots$$

$$1 \longrightarrow 0100000\cdots$$

$$2 \longrightarrow 0010000\cdots$$

$$3 \longrightarrow 0001000\cdots$$

$$4 \longrightarrow 0000100\cdots$$

$$5 \longrightarrow 0000010\cdots$$

$$6 \longrightarrow 0000001\cdots$$

$$\vdots$$

so $\char93 {\mathbb{N}}\le \char93 \{0,1\}^{\mathbb{N}}$; in other words $\aleph_0 \le 2^{\aleph_0}$. But Lemma 5 shows that $\char93 {\mathbb{N}}\not= \char93 \{0,1\}^{\mathbb{N}}$, so $\aleph_0 \not= 2^{\aleph_0}$. Combining these shows that $\aleph_0 < 2^{\aleph_0}$. $\qedsymbol$

A similar proof shows that $\aleph < 2^\aleph$ for every cardinal number $\aleph$. In other words, the power set ${\mathcal P}(S)$ of a set $S$ is always strictly bigger than $S$.