# Cantor’s diagonal argument

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.

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 of a will not be the same number as the n-th digit of sn.

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 sn which equals a. However, by definition, the n-th digit of a cannot equal the n-th digit of sn. So 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.