Real numbers are uncountable

We already showed that the rationals are countable, now we will show that the reels $\mathbb{R}$ are uncountable, meaning there is no one-to-one correspondence between the natural numbers $\mathbb{N}$ and the reels $\mathbb{R}$. The beautiful math proof is a classical example of Cantor’s Diagonal Argument and shows that you cannot enumerate the reels by a proof of contradiction. We will first prove the that the interval $(0,1)$ consisting of all reels between $0$ and $1$ (exclusive) is uncountable, and then generalize it to all reels.
So assume $(0,1)$ was countable, then there is a one-to-one correspondence $f:\mathbb{N} \rightarrow (0,1)$. This means we can enumerate the reels and write them in a table by writing $f(i)=.d_1 d_2 d_3 d_4 d_5 \ldots$ in the $i$-th row. Unfortunately, there’s a bit of ambiguity in the way we represent numbers that we need to resolve: Notice how $.5 = .49999\ldots, 0.1234 = 0.1233999\ldots$ are the same numbers with a different representation. To circumvent this we use the convention that the representation not containing the periodic $9$s is chosen whenever there is ambiguity. We need to find a number in $(0,1)$ that is not on the table to arrive at the contradiction that $f$ can indeed not be a one-to-one mapping.
We choose the number that consists of the digits of the diagonal of the table, and then negate each digit by choosing a digit at random that differs from the current one, from $0$ and from $9$. (We need it to be different from $0$ and $9$ to make sure the number we create is not just a different representation of an already existing one.) The below animation visualizes the process up to here.

The resulting number is in $(0,1)$, because it is neither $0=.00000\ldots$ nor $1=.99999\ldots$ by the way we chose the digits. It also obliges our convention of not using periodic $9$s as the representation, and is thus not just a different representation of another number (like $0.49999\ldots$ is for $.5$).
The number is aslo not among the numbers on the table (the range of $f$): Every $f(i)$ is different from our number at the $i$-th position. This means that $f$ “misses” the number and is not one-to-one, concluding the proof by showing our assumption does not hold.

Extending $(0,1)$ to $\mathbb{R}$

The proof easily extends to all real numbers, by noticing that $(0,1)$ and $\mathbb{R}$ have the same size. We make use of the tangent function $\tan$ which is bijective in $\left(-\frac{\pi}{2},\frac{\pi}{2}\right) \rightarrow \mathbb{R}$. Then, $g: (0,1) \rightarrow \mathbb{R}, x \mapsto \tan\left(\left(x-\frac{1}{2} \right) \pi \right)$ maps the interval $(0,1)$ onto $\mathbb{R}$.

The reels $\mathbb{R}$ have the same cardinality as the plane $\mathbb{R}^2$

A nice intuition for this fact is given by space-filling curves, like the Hilbert Curve or Peano Curve.

Share:

Get updates on new content.

No spam, no sales pitch, I promise. I don't like these myself.

Similar Work

Leave a Reply