Mathematics

The Uncountability of the Continuum

An exploration of Georg Cantor's diagonal argument to prove that the set of real numbers between 0 and 1 cannot be listed in a complete sequence.

Scene 1 of 4

The Infinite List Hypothesis

[0,1] = \{x_1, x_2, x_3, \dots\}

Imagine we try to list every real number between zero and one. We align them in an infinite sequence, hoping that every single value appears somewhere on this list.

Step-by-step solver

(a) Assumption

Assume for contradiction that [0,1] is countable, meaning there is a surjection from the natural numbers to [0,1], listing all real numbers as x_1, x_2, ...

[0,1] = \{x_1, x_2, x_3, \dots\}

(b) Expansion

Write each number in its infinite decimal expansion, ensuring uniqueness by avoiding sequences ending in infinite 9s.

x_n = 0.d_{n,1} d_{n,2} d_{n,3} \dots

Construct a new number y with digits e_n that specifically differ from the diagonal entries d_{n,n} to ensure y is not equal to any x_n.

e_n = \begin{cases} 5 & \text{if } d_{n,n} \neq 5 \\ 6 & \text{if } d_{n,n} = 5 \end{cases}

(d) Contradiction

Since y differs from every x_n in at least one decimal position, y cannot be in our list, contradicting the assumption that the list was exhaustive.

y \notin \{x_1, x_2, x_3, \dots\} \implies [0,1] \text{ is uncountable}

Original question

Prove that the set of real numbers in the interval [0,1] is uncountable, using Cantor's diagonal argument.

Follow-up chat

Ask me anything about this lesson — I'll answer using what we just covered.