The Set of Real Numbers is Uncountable

Theorem 1: The set of numbers in the interval, $[0, 1]$, is uncountable. That is, there exists no bijection from $\mathbb{N}$ to $[0, 1]$.

The argument in the proof below is sometimes called a "Diagonalization Argument", and is used in many instances to prove certain sets are uncountable.

• Proof: Suppose that $[0, 1]$ is countable. Clearly $[0, 1]$ is not a finite set, so we are assuming that $[0, 1]$ is countably infinite.

• Then there exists a bijection from $\mathbb{N}$ to $[0, 1]$. In other words, we can create an infinite list which contains every real number. Write each number in the list in decimal notation. Such a list might look something like:

(1)

\begin{align} \quad 1 & \quad 0.02342424209059039434934... \\ \quad 2 & \quad 0.32434293429429492439242... \\ \quad 3 & \quad 0.50000000000000000000000... \\ \quad 4 & \quad 0.20342304920940294029490... \\ \quad \vdots & \quad \vdots \end{align}

• Let $N$ be the number obtain obtained as follows. For each $n \in \mathbb{N}$, let the $n^{\mathrm{th}}$ decimal spot of $N$ be equal to the $n^{\mathrm{th}}$ decimal spot of $n^{\mathrm{th}}$ number in the list $+ 1$ if that number is less than $9$, and let it be $0$ if that number is equal to $9$. In the list above, we would have $N = 0.1315...$.

• By construction, $N$ is different from every number in our list and so our list is incomplete. But this contradicts the existence of a bijection from $\mathbb{N}$ to $[0, 1]$. Hence $[0, 1]$ must be uncountable. $\blacksquare$

Corollary 2: The set of real numbers, $\mathbb{R}$, is uncountable.

• Proof: Since $[0, 1]$ is uncountable and $[0, 1] \subset \mathbb{R}$ we have that $\mathbb{R}$ is uncountable. $\blacksquare$

Corollary 3: The set of irrational numbers is uncountable.

• Proof: The set of irrational numbers is $\mathbb{R} \setminus \mathbb{Q}$. We know that the set $\mathbb{Q}$ is countable and the set $\mathbb{R}$ is uncountable. Therefore the set difference $\mathbb{R} \setminus \mathbb{Q}$ is uncountable. $\blacksquare$