Cantor's Diagonalization Argument

R

is uncountable.

Proof
We'll show that $[0, 1] \subseteq R$ is uncountable. Let $f : N \to [0, 1]$ . We'll show $f$ is not onto. Recall that each $x \in [0, 1]$ has an infinite decimal representation:

x = 0. b_{1} b_{2} . . .

where each $b_{i} \in {0, . . ., 9}$ .

1 = 0.9999999 \dots

, so

1

can be represented this way.

Let's look at each $f (n)$ :

\begin{aligned} f (1) & = 0. a_{11} a_{12} a_{13} a_{14} \dots \\ f (2) & = 0. a_{22} a_{22} a_{23} a_{24} \dots \\ f (3) & = 0. a_{31} a_{32} a_{33} a_{34} \dots \\ f (4) & = 0. a_{41} a_{42} a_{43} a_{44} \dots \\ ⋮ \end{aligned}

For $n \in N$ , let $b_{n} = {\begin{cases} 7 & if a_{n n} \neq 7 \\ 3 & if a_{n n} = 7 \end{cases}$ (note: the numbers here don't matter. It just matters we change each number to some new number).

Now consider $x = 0. b_{1} b_{2} b_{3} b_{4} \dots$ . Clearly $x \in [0, 1]$ still. But since $b_{1} \neq a_{11}$ by our mapping, then $x \neq f (1)$ . Similarly since $b_{2} \neq a_{22}$ then $x \neq f (2)$ . Repeat this argument, so then $x \neq f (n)$ for all $n$ . Therefore, $f$ is not onto, completing the proof.
☐