Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Uncountability and Cantor's diagonal argument

Not every infinite set can be listed in a sequence. Cantor's diagonal argument proves that the real numbers in an interval such as $(0,1)$ are uncountable.

Suppose a complete list existed

Assume every number in $(0,1)$ could be written in a sequence of decimal expansions:

r1 = 0.a11 a12 a13 ...
r2 = 0.a21 a22 a23 ...
r3 = 0.a31 a32 a33 ...
...

Construct a missing number

Choose a new decimal number whose $n$th digit differs from the $n$th digit of $r_n$, avoiding ambiguous repeating-9 representations.

The constructed number differs from $r_1$ in its first digit, from $r_2$ in its second digit, and in general from $r_n$ in digit $n$.

It therefore cannot appear anywhere in the assumed complete list.

Consequence

The assumption that the reals can be enumerated leads to a contradiction. Hence

$$|\mathbb R|>|\mathbb N|.$$

Infinite sets can therefore have genuinely different cardinalities.

Cantor's theorem

More generally, no set has the same cardinality as its own power set:

$$|A|<|\mathcal P(A)|.$$

This produces an unending hierarchy of larger infinities.