Safekipedia

Cantor's diagonal argument

Explorer · ages 7 and underAdapted from Wikipedia
An illustration of Cantor's diagonal argument for the existence of uncountable sets: the set of binary sequences is uncountable. The sequence at the bottom cannot occur anywhere in the enumeration of sequences above.

What Is It?

Cantor's diagonal argument is a mathematical proof. It shows that some infinite sets cannot be matched one-to-one with the natural numbers. Some sets have more things in them than the counting numbers do.

These special sets are called uncountable sets. The study of how big infinite sets are is called the theory of cardinal numbers. Georg Cantor started this study.

Cantor shared this proof in 1891. It was not his first proof that the real numbers cannot be counted. He had an earlier one in 1874. The same method has helped in many other proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem.

Ideas like this can also lead to fun puzzles, such as Russell's paradox and Richard's paradox.

Lists That Never End

Cantor looked at a set called T. It holds all the endless sequences of binary digits. Each digit is either zero or one. Using a constructive proof of a lemma, he showed that you can always make a new sequence that is not on any list.

To make the new sequence, you pick the complementary digit. That means 0 becomes 1, and 1 becomes 0. The new sequence is different from every sequence on the list.

Cantor used a proof by contradiction to show that T is uncountable. If T could be counted, all its sequences would fit on one list. But the new sequence would still be missing from it. The real numbers were already known to be uncountable from Cantor's first uncountability proof. Cantor also matched T with the real numbers, using decimal fractions and a base number. This showed that they have the cardinality of the continuum.

The same idea also proves Cantor's theorem. For any set S, the power set is the group of all subsets of S. The power set cannot be matched with S itself. No function from S to its power set can be surjective.

Comparing Sizes

Cantor said two sets are the same size if every item in one can be paired with exactly one item in the other. He also compared sizes by asking if one set can be matched with part of another set, using the existence of injections. This way of comparing works like a preorder.

The natural numbers can be matched with binary sequences, so the natural numbers are not bigger. But they cannot be matched completely, so the binary sequences are uncountable. The same kind of thinking shows that a set and all its subsets cannot be matched one-to-one. This also uses proof by contradiction.

Quiz time!

3 questions about Cantor's diagonal argument

Question 1 of 3

What does Cantor's diagonal argument show?

Pictures

Illustration of the generalized diagonal argument: The set T={n∈ℕ:n∉f(n)} at the bottom cannot occur anywhere in the range of f:ℕ→𝒫(ℕ). The example mapping f happens to correspond to the example enumeration s in the picture above.

Keep exploring

This article is a child-friendly adaptation of the Wikipedia article on Cantor's diagonal argument, available under CC BY-SA 4.0.

Images from Wikimedia Commons. Tap any image to view credits and license.