Proof that the Set of Real Numbers is Uncountable

Proof that 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: 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$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License