Cantor's Diagonal Argument, math that surprises you lesson

The positive integers, the pairs of positive integers and the rational numbers can all be put into one numbered list. Can the real numbers between $0$ and $1$ be listed too? This page presents Cantor’s diagonal argument, which takes any proposed list, uses its own digits to build a number between $0$ and $1$ that the list misses, and so shows that no list can contain them all. It also explains why the new number is built from the digits $1$ and $2$ only.

Key terms

Cantor’s diagonal argument

Definition Cantor’s diagonal argument proves that the real numbers strictly between $0$ and $1$ cannot all be placed in one numbered list. Suppose someone offers a list $r_1, r_2, r_3, \dots$ of numbers in this interval, any list at all, and claims that it is complete. Write each row as a decimal expansion

r_n = 0.d_{n1} d_{n2} d_{n3} \ldots,

so that $d_{nk}$ is the $k$ th digit after the point in row $n$ , and write a decimal that stops, such as $0.5$ , with endless zeros. The digits $d_{11}, d_{22}, d_{33}, \dots$ form the diagonal. Build a new number $c = 0.c_1 c_2 c_3 \ldots$ by the rule

c_n = \begin{cases} 2 & \text{if } d_{nn} = 1, \\ 1 & \text{otherwise.} \end{cases}

Then $c$ differs from row $n$ in the $n$ th digit, for every $n$ . Because $c$ uses only the digits $1$ and $2$ , no other decimal expansion names the same number, so a different digit means a different number, and $c \ne r_n$ for every $n$ . Also $1/9 \le c \le 2/9$ , so $c$ lies strictly between $0$ and $1$ . The list misses a number of the interval, which contradicts the claim that it is complete. Since the list was arbitrary, no list contains all the real numbers between $0$ and $1$ , and this set is uncountable. Georg Cantor published the argument in 1891.

In plain words Whatever list you are handed, read off its diagonal and write a number that disagrees with the first row in the first digit, with the second row in the second digit, and so on forever. That number lies between $0$ and $1$ but sits in no row, so the list was not complete after all.

Example Suppose the list begins with these four rows, with the diagonal digits in bold.

\begin{aligned} r_1 &= 0.\mathbf{1}3400\ldots \\[0.4em] r_2 &= 0.2\mathbf{7}100\ldots \\[0.4em] r_3 &= 0.45\mathbf{1}00\ldots \\[0.4em] r_4 &= 0.789\mathbf{0}0\ldots \end{aligned}

The diagonal digits $1, 7, 1, 0$ become $2, 1, 2, 1$ , so $c = 0.2121\ldots$ , and its later digits come from later rows in the same way. The number $c$ differs from $r_1$ in the first digit, from $r_2$ in the second, from $r_3$ in the third and from $r_4$ in the fourth. If someone suggests that $c$ is row one million, there is no need to look at the other digits of that row. The millionth digit of $c$ was chosen to differ from the millionth digit of row one million, so $c$ is not that row either.

Decimal expansion

Definition A decimal expansion $0.d_1 d_2 d_3 \ldots$ , with each digit $d_k$ one of $0, 1, \dots, 9$ , names the real number

\sum_{k=1}^{\infty} \frac{d_k}{10^k},

the number that the truncations $0.d_1$ , $0.d_1 d_2$ , $0.d_1 d_2 d_3$ and so on approach. Every real number from $0$ to $1$ has at least one decimal expansion of this form. Two different expansions can name the same number in only one way. They agree before some place, and at that place one has a digit $a$ followed by endless 9s while the other has the digit $a + 1$ followed by endless 0s, as in $0.24999\ldots = 0.25000\ldots$ . So an expansion that ends neither in endless 0s nor in endless 9s is the only expansion of its number.

In plain words A decimal expansion is an endless string of digits after the point. Most numbers have just one, but a positive number that can be written with finitely many digits, such as $0.25$ , also has a second one that ends in endless 9s.

Example The expansion $0.111\ldots$ is the geometric series $1/10 + 1/100 + 1/1000 + \dots$ , in which each term is a tenth of the one before, so its sum is

\frac{1/10}{1 - 1/10} = \frac{1}{9}.

Doubling every digit gives $0.222\ldots = 2/9$ . A number $c$ whose digits are all $1$ or $2$ has each digit at least $1$ and at most $2$ , so $1/9 \le c \le 2/9$ , and such a number lies strictly between $0$ and $1$ . It has no second expansion, because its expansion ends neither in endless 0s nor in endless 9s. By contrast $0.24999\ldots = 0.24 + 0.00999\ldots = 0.24 + 0.01 = 0.25$ , the same kind of pair as in Why 0.999… Equals 1.

Proof by contradiction

Definition A proof by contradiction proves a statement by assuming that it is false and deducing from that assumption, by valid steps, something impossible, such as a statement together with its opposite. Valid steps from a true assumption never lead to something false, so the assumption must be false, and the statement is true. In Cantor’s argument the assumption is that some list contains every real number between $0$ and $1$ . The contradiction is the number $c$ , which lies between $0$ and $1$ , so it should be in the list, and yet differs from every row. Nothing about the list was used except that it is a numbered list of such numbers, so the contradiction rules out every possible list, including lists that no formula or computer could produce, and not only the lists someone has tried.

In plain words To show that something cannot happen, suppose that it does and follow the consequences until they contradict each other. The diagonal argument can also be read directly, as a recipe that takes any list and produces a number the list misses.

Example There is no largest positive integer. Suppose $N$ were the largest one. Then $N + 1$ is also a positive integer and $N + 1 > N$ , which contradicts the choice of $N$ , so no largest positive integer exists. The same pattern shows that there is no smallest positive rational number, since half of a positive rational number is a smaller one.

Uncountable set

Definition A set is uncountable when it is not countable, that is, when it is infinite and there is no one-to-one correspondence between it and the positive integers. Equivalently, the set is not empty and every endless list $a_1, a_2, a_3, \dots$ made of its elements misses at least one of them. Every subset of a countable set, meaning every set made of some of its elements, is countable, so any set that contains an uncountable set is uncountable as well. The diagonal argument shows that the set of real numbers between $0$ and $1$ is uncountable, so the set of all real numbers is uncountable too.

In plain words An uncountable set is too large to be numbered, even with all the positive integers, so infinite sets do not all have the same size. The claim is about the ideal set of all real numbers in the interval, not about the finitely many points or pixels that any drawing of it shows.

Example The rational numbers between $0$ and $1$ form a countable set, as the diagonal enumeration of fractions shows. If the irrational numbers between $0$ and $1$ were countable too, with lists $s_1, s_2, \dots$ of the irrational ones and $q_1, q_2, \dots$ of the rational ones, then

s_1, \; q_1, \; s_2, \; q_2, \; \dots

would list every real number between $0$ and $1$ , which the diagonal argument rules out. So the irrational numbers between $0$ and $1$ form an uncountable set, while the rational numbers there form a countable one. Every interval of positive length between $0$ and $1$ contains numbers of both kinds, so the difference between the two sets is one of size, not of position on the line.

Check yourself

A list begins with the following five rows. Find the first five digits of the diagonal number $c$ , and name a place where $c$ differs from $r_4$ .

\begin{aligned} r_1 &= 0.500000\ldots \\[0.4em] r_2 &= 0.314159\ldots \\[0.4em] r_3 &= 0.111111\ldots \\[0.4em] r_4 &= 0.121212\ldots \\[0.4em] r_5 &= 0.718281\ldots \end{aligned}

Show the answer

The diagonal digits are the first digit of $r_1$ , the second of $r_2$ and so on, which gives $5, 1, 1, 2, 8$ . The rule turns $1$ into $2$ and every other digit into $1$ , so the new digits are $1, 2, 2, 1, 1$ and

c = 0.12211\ldots

The rule guarantees a difference from $r_4$ in the fourth digit, where $c$ has $1$ and $r_4$ has $2$ . Here the two numbers happen to differ in the third digit as well, but the fourth place is the one the construction controls for every possible row $4$ .

Change the rule so that the new digit is $9$ when the diagonal digit is $0$ , and $0$ otherwise. Apply it to the list whose first row is $0.1000\ldots$ and whose row $n$ , for $n \ge 2$ , is $1/2^{n-1}$ , so the list continues $0.5$ , $0.25$ , $0.125$ , $0.0625$ and so on. What number does the changed rule build, and is it missing from the list? What does the rule with the digits $1$ and $2$ build?

Show the answer

The number $1/2^{n-1}$ equals $5^{n-1}/10^{n-1}$ , so it has exactly $n - 1$ digits after the point, and its $n$ th digit is $0$ . The diagonal is therefore $1, 0, 0, 0, \dots$ , and the changed rule gives the digits $0, 9, 9, 9, \dots$ , which build

0.0999\ldots = 0.1.

This is the first row. The new expansion differs from every row in the diagonal place, including from $0.1000\ldots$ in the first digit, and yet the number it names is in the list, because $0.0999\ldots$ and $0.1000\ldots$ are two expansions of one number. The digit test is only valid when the new expansion is the only expansion of its number.

The rule with the digits $1$ and $2$ gives $2, 1, 1, 1, \dots$ , so it builds $0.2111\ldots = 19/90$ . This expansion ends neither in endless 0s nor in endless 9s, so it is the only one this number has, and it does not stop. Every row of the list is a decimal that stops, so $19/90$ really is missing.

Someone repairs the list from the first question by putting $c = 0.12211\ldots$ at the top and moving every other row down one place. Find the first six digits of the new diagonal number, and explain why no repair of this kind can succeed.

Show the answer

The new rows are $c, r_1, r_2, r_3, r_4, r_5, \dots$ , so the new diagonal takes the first digit of $c$ , the second digit of $r_1$ , the third of $r_2$ , the fourth of $r_3$ , the fifth of $r_4$ and the sixth of $r_5$ . These are $1, 0, 4, 1, 1, 1$ , and the rule gives

c' = 0.211222\ldots

This number is missing from the repaired list for the same reason as before, and it differs from $c$ already in the first digit. Any repair, whether it adds one number, finitely many or a whole numbered list of them, produces another numbered list, and the diagonal argument applies to every numbered list. So each repair is answered by a new missing number, and the real numbers between $0$ and $1$ stay uncountable.

Cantor's Diagonal Argument

Video 1, chapter 21

Key terms