Log In

Uncountability of real numbers - a simple proof

Posted on: March 2nd, 2013 by
Comments Disabled

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.

Comments are closed.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}