[Overview] [Previous] [Next]

Diagonalization

In mathematics (not in computer science!), real numbers are defined to have an infinite number of digits to the right of the decimal point. Thus, trancendental numbers such as pi and e, as well as rational numbers such as 2.000000... and 0.171717... are real numbers.

Theorem. The real numbers are not denumerable; there are more real numbers than there are natural numbers.

We will consider only the real numbers between 0 and 1, or more exactly, the set {x: 0 x < 1}.

To show that these real numbers are not denumerable, we can't just demonstrate an attempted correspondence that doesn't work; we need to show that no possible correspondence can work. We do this by a technique called diagonalization.

Proof. Suppose that there exists a one-to-one correspondence between the natural numbers an the real numbers. Then list the natural numbers and their corresponding real numbers as shown:

   1   . 1 4 1 5 9 2 ...
   2   . 1 7 1 7 1 7 ...
   3   . 7 1 8 2 8 4 ...
   4   . 2 5 0 0 0 0 ...
   ...

(The actual real numbers shown are for illustrative purposes only; to be more formal we should represent these numbers in some more abstract way, such as .d_1,1d_1,2d_1,3d_1,4...)

We claim this correspondence is complete, so every real number must be found somewhere in the right column. Now consider some number whose first digit (after the decimal point) is different from the first digit of the first real number (the 1 shown in boldface above); whose second digit differs from the second digit of the second real number (7); whose third digit differs from the third digit of the third real number (8); and so on. For example, the real number we are constructing might start out .2855... (since 21, 87, 58, 50, and so on.

We constructed this real number so that it differs from every real number in the right-hand column by at least one digit. Thus, the number does not appear in the right-hand column. Since this argument applies to any arbitrary correspondence between the natural numbers and the reals, no one-to-one correspondence is possible, and the real numbers are not denumerable. Q.E.D.