In this article, I wish to show a simple elementary proof that there cannot exist any bijection between the set of real numbers and the set of natural numbers . 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 to . Note that the unit interval 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 to .
The proof is by contradiction. Suppose such a bijection exists, i.e. every real number is the real number for a unique natural number . Then I can write all the real numbers sequentially in paper. For the proof, it is convenient to write a number in in binary instead of decimals, eg. . Then the real numbers can be written in the form of an infinite dimensional matrix whose entries are either 0 or 1 as follows: the element of the matrix would correspond to the binary digit of the natural number.
Now consider the number formed by the diagonal entries. Now complement each entry and consider the number 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 real number. Then consider , the entry of . This number has to be both and , because it is the 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 have a unique representation by sequences of binary digits. This is not true since it is well known that . Perhaps a reference to this link can fix that gap.
What are your thoughts? Leave feedback.