The Set of all Subsets of Natural Numbers is Uncountable

Theorem 1: The set $\mathcal P (\mathbb{N})$ of all subsets of $\mathbb{N}$ is uncountable.

In the proof below, we use the famous diagonalization argument to show that the set of all subsets of $\mathbb{N}$ is uncountable.

• Proof: Suppose that $\mathcal P (\mathbb{N})$ is countable.

• We can denote each set $A \subseteq \mathbb{N}$ by a decimal number of the form:

(1)

\begin{align} \quad 0.x_0x_1...x_n... \end{align}

• where each $x_n \in \{ 0, 1 \}$ and such that $x_n = 0$ if $n \in A$ and $x_n = 1$ if $n \not \in A$. For example, the set $\{ 1, 3, 4, 5, 6 \}$ has decimal representation $0.1011110...$. Now since we assume that $\mathcal P (\mathbb{N})$ is countable, there exists a bijective function $f : \mathbb{N} \to \mathcal P(\mathbb{N})$ defined for all $n \in \mathbb{N}$ by $f(n) = A_n$. We list the sets $\{ A_1, A_2, ..., A_n, ... \}$ and their decimal representations as follows:

(2)

\begin{align} \quad A_1, \: & 0.x_{1,1}x_{1,2} \cdots x_{1,n} \cdots \\ \quad A_2, \: & 0.x_{2,1}x_{2,2} \cdots x_{2,n} \cdots \\ \quad & \vdots \\ \quad A_n, \: & 0.x_{n,1}x_{n,2} \cdots x_{n,n} \cdots \\ \quad & \vdots \end{align}

• Now construct a decimal number $x = 0.x_1x_2...x_n...$ as follows. We let $x_1 = 0$ if $x_{1,1} = 1$ and we let $x_1 = 1$ if $x_{1,1} = 0$. We let $x_2 = 0$ if $x_{2,2} = 1$ and we let $x_2 = 1$ if $x_{2,2} = 0$. In general, we let $x_n = 0$ if $x_{n,n} = 1$ and we let $x_n = 1$ if $x_{n,n} = 0$. Then $X$ differs from all of the decimal numbers in the list above in at least one decimal spot. So the decimal $x$ corresponds to a subset $X$ of $\mathbb{N}$ that is not on the list above. This is a contradiction since $f$ is assumed to be a bijection.

• Therefore the set $\mathcal P(\mathbb{N})$ is uncountable. $\blacksquare$