Cantor's Diagonal Argument

Some infinities are bigger than others — and diagonalization is the proof.

The idea

Cantor's diagonal argument proves that some infinite sets are too large to be listed. Two finite sets have the same size when their elements can be paired off one for one, and the test applies equally to infinite sets. Call a set countable when its elements can be paired off with $1, 2, 3, \dots$ — equivalently, when they can be arranged in a single list $a_1, a_2, a_3, \dots$ in which every element eventually appears — and uncountable when no such list exists.

It is not obvious that any set is uncountable. The integers are countable, listed $0, 1, -1, 2, -2, \dots$, and so are the rationals, although they crowd densely into every interval of the line.

The diagonal argument establishes uncountability by refuting an arbitrary proposed list rather than any particular one. Suppose the entries $a_1, a_2, a_3, \dots$ are themselves infinite sequences of digits, and write them as the rows of a table. Build a new sequence whose first digit differs from the first digit of $a_1$, whose second digit differs from the second digit of $a_2$, and in general whose $n$-th digit differs from the $n$-th digit of $a_n$. The new sequence disagrees with every row somewhere, so it is not on the list. Since the list was arbitrary, no list can be complete.

Ways to work on it

• Walkthrough. Why |ℝ| > |ℕ| — via the diagonal trick.
• Practice. Quick yes/no on which sets are countable.
• Hardest. Decide countable or uncountable for trickier sets.

Not sure where to start? Take the ten-question placement test.