Cantor’s diagonal argument is a beautiful proof of the uncountability of the real numbers.

First we need some definitions.

Two sets are said to be *one-to-one* if each member of the first set maps to exactly one member of the second set. We say a set maps *onto* another set if each member of the first set maps onto a unique member of the second set. If two sets are both one-to-one and onto, then we say they have *one-to-one correspondence*. For example, the set of uppercase letters and the set of lowercase letters have one-to-one correspondence.

We say a set is *countable* if it has a finite number of elements or if it has a one-to-one correspondence with the set of positive integers. Essentially, if you can count the members of the set, even if you’d have to count forever, the set is countable.

Cantor’s diagonal argument uses proof by contradiction. That means we’ll start with an assumption and then demonstrate how that assumption leads to a logical contradiction.

Assume the set of real numbers is countable. The set of real numbers is infinite so it must have one-to-one correspondence with the set of positive integers.

If the set of real numbers is countable, then it follows that the subset of real numbers from zero to one is also countable. (If you can count everything in the set, then you can count a subset of the set.)

Since we are assuming the set of real numbers is countable, it must be possible to create a numbered list the real numbers. (This sounds like counting!) Let this list be designated {s1, s2, s3, …}. Here is the start of one such list. The numbers chosen are not significant.

We must accept that this infinitely long list contains all real numbers between zero and one.

Next, let’s define a number *a* which will be formed by using the following rule:

The

n-th digit ofawill not be the same number as then-th digit ofs._{n}

Here is one possible construction of *a*. Each digit of *a* is chosen to be different than the bracketed number in that column.

We can clearly see that *a* is a real number in the range zero to one, so there must be a number *s _{n}* which equals

*a*. However, by definition, the n-th digit of

*a*cannot equal the n-th digit of

*s*. So

_{n}*a*is not a member of our list. We have just shown that the set of positive integers does not map

*onto*the set of real numbers. Thus the set of positive integers does not have one-to-one correspondence with the set of real numbers.

This is a contradiction with our original assumption that the set of real numbers is countable.

Thus the set of real numbers is not countable.