TheoremProved

Uncountability of the reals (Cantor's diagonal argument)

Statement

The set of real numbers is uncountable: there is no bijection between $\mathbb{N}$ and $\mathbb{R}$ — indeed none even between $\mathbb{N}$ and the interval $(0,1)$ .

Why is it true?

If you tried to list every real number in $(0,1)$ as an infinite sequence $x_1,x_2,x_3,\dots$ , you could always build a new number that differs from the $n$ -th listed number at its $n$ -th decimal digit — so this new number is never on the list, and no list can ever be complete.

Proof sketch

Suppose for contradiction that $x_1,x_2,\dots$ enumerates every real number in $(0,1)$ via decimal expansions; define $y=0.y_1y_2y_3\dots$ by choosing $y_n$ to differ from the $n$ -th digit of $x_n$ (e.g. $y_n=5$ if that digit is not $5$ , else $y_n=6$ , avoiding the $\dots999\dots=\dots000\dots$ ambiguity); then $y\in(0,1)$ but $y\neq x_n$ for every $n$ (they differ at digit $n$ ), contradicting the assumption that the list was complete.

Proved by

proved 1891Georg Cantor

Topics that use this theorem

Functions and cardinality

Related theorems

Cantor–Schröder–Bernstein theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Georg Cantor (1891). Über eine elementare Frage der Mannigfaltigkeitslehre
Paul R. Halmos (1974). Naive Set Theory