Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 38 ยท Countable and Uncountable Sets

Cantor's Diagonal Argument

Follow Cantor's diagonal proof that the real numbers between 0 and 1 cannot be listed, and watch the diagonal construction work in Python.

So far every infinite set we met, โ„•, โ„ค, โ„š, turned out to have cardinality โ„ตโ‚€. You might start to suspect that all infinite sets are the same size. In 1874 Cantor proved otherwise, and in 1891 he gave the slicker proof you will see here, now called the diagonal argument. It shows that the real numbers cannot be listed, so there are strictly more of them than natural numbers.

It is one of the most influential proofs in mathematics, and the same trick reappears in logic, computer science and the theory of computation.

The claim

Theorem. The interval (0, 1) of real numbers is uncountable.

We prove it by contradiction. Suppose some list rโ‚, rโ‚‚, rโ‚ƒ, ... contains every real number in (0, 1). We will build a real number in (0, 1) that is not on the list.

Decimal expansions

Every real number in (0, 1) has a decimal expansion 0.dโ‚dโ‚‚dโ‚ƒ.... A small wrinkle: some numbers have two expansions, such as 0.5000... = 0.4999.... To avoid trouble, always choose the expansion that does not end in all 9s. Then each real in (0, 1) has exactly one expansion.

Write the supposed list in full:

Text
rโ‚ = 0. 3 1 4 1 5 9 ...
rโ‚‚ = 0. 5 0 0 0 0 0 ...
rโ‚ƒ = 0. 7 1 8 2 8 1 ...
rโ‚„ = 0. 4 1 4 2 1 3 ...
rโ‚… = 0. 1 6 1 8 0 3 ...

The diagonal construction

Look at the diagonal digits: the 1st digit of rโ‚, the 2nd digit of rโ‚‚, the 3rd of rโ‚ƒ, and so on. Build a new number x = 0.eโ‚eโ‚‚eโ‚ƒ... by changing each diagonal digit:

  • if the n-th digit of rโ‚™ is 5, let eโ‚™ = 6;
  • otherwise let eโ‚™ = 5.

Using only the digits 5 and 6 guarantees that the expansion of x has no zeros or trailing 9s, so it is the unique expansion of a number in (0, 1).

Now x differs from rโ‚ in the first digit, from rโ‚‚ in the second digit, from rโ‚™ in the n-th digit. Because of the uniqueness of expansions, x โ‰  rโ‚™ for every n. So x is a real number in (0, 1) missing from the list. Contradiction. No list can contain every real number.

flowchart LR
  L["Assume a complete list rโ‚, rโ‚‚, rโ‚ƒ, ..."] --> D["Read the diagonal digits"]
  D --> X["Change every diagonal digit to get x"]
  X --> C["x differs from every rโ‚™ at digit n"]
  C --> K["x is not on the list: contradiction"]

The structure of the proof by contradiction.

Python Run the diagonal construction on a list of decimals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the argument works for any list. A different list gives a different x, but there is always a missing number. That is what makes the proof so strong: it does not matter how cleverly the list was built.

The same idea with sequences of bits

Here is the argument without decimals. Let S be the set of all infinite binary sequences (functions โ„• โ†’ {0, 1}). Suppose sโ‚€, sโ‚, sโ‚‚, ... lists some of them. Define a new sequence t by t(n) = 1 - sโ‚™(n): flip the n-th bit of the n-th sequence. Then t differs from each sโ‚™ at position n, so it is not on the list. Hence S is uncountable.

Python Flip the diagonal of bit sequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binary sequences are the same as subsets of โ„• (the set of positions where the bit is 1). So this argument shows that P(โ„•) is uncountable. The next lesson generalizes it to every set.

Common objections

"Just add x to the list." Then the new list has a different diagonal and the argument builds a new missing number. You can never finish, which is the point.

"But the rationals are also dense, so why can they be listed?" The listing of โ„š works because every rational is reached at some finite position. The diagonal number is not rational (in general), so it is no counterexample there. For the reals, the argument applies to any list.

"Does the real number x really exist?" Yes: any infinite string of digits defines a real number. It is a specific number once the list is fixed.

What we learned

Real numbers cannot be put in a list, so |โ„•| < |(0, 1)|. In the lesson on the continuum you will see that (0, 1) has the same cardinality as the whole real line.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the diagonal argument, what is the n-th digit of the new number x?

    That is what guarantees that x is different from rโ‚™ for every n.
  2. 2. Why does the construction use only the digits 5 and 6 for x?

    Numbers like 0.5 = 0.4999... have two expansions. Using only 5s and 6s ensures x's expansion is the only one, so differing in a digit really means a different number.
  3. 3. What does the diagonal argument prove?

    It shows that any proposed list of reals in (0, 1) misses some real, so (0, 1) is uncountable.
  4. 4. Infinite binary sequences correspond to which kind of set?

    A binary sequence marks, for each n, whether n is in the subset. So sequences correspond to subsets of โ„•, and there are uncountably many.

Summary

  • The diagonal argument shows no list of real numbers can include every real in (0, 1).
  • Build x by changing the n-th digit of the n-th listed number; avoid 0 and 9 digits so expansions are unique.
  • The same construction shows that the set of infinite binary sequences, which equals P(โ„•), is uncountable.
  • So there are infinite sets of different sizes: โ„ตโ‚€ < |โ„|.

Next: Power Sets and Cantor's Theorem