# Real numbers are uncountable

One of the slickest proofs of all time is using Georg Cantor‘s 1891 diagonal argument in proving that the real numbers $\mathbb{R}$ constitute an uncountable set, that is, they cannot be put in a bijective correspondence with $\mathbb{N}$. Strictly speaking, Cantor original paper only proved that the set of all $0,1$-sequences is uncountable. However since it is easy to argue that the set of all such sequences and $\mathbb{R}$ have the same cardinality, indirectly we get a proof for the uncountable nature of the reals. Moreover, the argument given by Cantor in his proof can be easily modified to give a direct proof for the uncountability of the reals. This is what we do presently.

Theorem: $\mathbb{R}$ is uncountable.

Proof: We will accept that every real number $x$ has a decimal expansion, $x=N.x_1x_2\cdots$ and it is uniquely determined by $x$ if one agrees never to terminate the expansion with an infinite string of $9$‘s. The proof is based on contradiction, and so we suppose that $\mathbb{R}$ is not uncountable. Then it must be that $\mathbb{R}$ is countable and we can make a list of all the elements of $\mathbb{R}$ along with their decimal expansion as follows:

$x_1=N_1.x_{11}x_{12}x_{13}\cdots\\x_2=N_2.x_{21}x_{22}x_{23}\cdots\\x_3=N_3.x_{31}x_{32}x_{33}\cdots\\\vdots$

We now consider the real number $0.y_1y_2y_3\cdots$ which is defined by $y_i=1$ if $x_{ii}\ne 1$ and $y_i=2$ otherwise. It is clear that this number differs from every $x_i$ in the list in at least the $i$‘th position. Hence this list is incomplete, a contradiction.$\Box$