## Uncountability of real numbers - a simple proof

Posted on: March 2nd, 2013 by

In this article, I wish to show a simple elementary proof that there cannot exist any bijection between the set of real numbers $\mathcal{R}$ and the set of natural numbers $\mathcal{N}$. This proof is popularly known as Cantor's diagonal proof.

Here's the proof. Firstly I claim that there exists a bijection from the unit interval $(0,1)$ to $\mathcal{R}$. Note that the unit interval   $(0,1)$ is the set of all real numbers between 0 and 1. I will leave that proof as a simple exercise. Now I will show that there cannot exist a bijection from $(0,1)$ to $\mathcal{N}$.

The proof is by contradiction. Suppose such a bijection exists, i.e.  every real number is the $i-th$ real number for a unique natural number $i$. Then I can write all the real numbers sequentially in paper. For the proof, it is convenient to write a number in  $(0,1)$ in binary instead of decimals, eg. $0.01101001101\dots$. Then the real numbers can be written in the form of an infinite dimensional matrix $M$ whose entries are either 0 or 1 as follows: the $(i,j)-th$ element $M_{ij}$ of the matrix would correspond to the $j-th$ binary digit of the $i-th$ natural number.

Now consider the number $0.(M_{11})(M_{22})(M_{33})(M_{44})\dots$ formed by the diagonal entries. Now complement each entry and consider the number $0.(\bar{M_{11}})(\bar{M_{22}})(\bar{M_{33}})(\bar{M_{44}})\dots$ obtained by replacing 1's by 0's and vice versa in the binary expansion of the original real number. Suppose this number is the $j-th$ real number. Then consider  $M_{jj}$, the $(j,j)-th$ entry of $M$. This number has to be both $0$ and $1$, because it is the $j-th$ binary digit of both the diagonal real number and it's complement. This is a contradiction.

The more astute reader will notice that there are some gaps in the proof. For example, I implcitly assumed that the real numbers in $(0,1)$ have a unique representation by sequences of binary digits. This is not true since it is well known that $0.01111\dots = 0.10000\dots$. Perhaps a reference to this link can fix that gap.

What are your thoughts? Leave feedback.