Lesson 3

Now we are ready to prove that the set of real numbers is uncountable. To do this, we will use Cantor's diagonal method (or argument), which we will later also use to show that a set cannot be in one-to-one correspondence with its power set.

Theorem (Cantor's Diagonal Argument, 1874). The set of real numbers is uncountable.

Proof. By the theorem above, it is enough to show that the set of infinite binary sequences is uncountable. To do this, assume that it is countable: let \(a_{1}, a_{2}, \dotsc\) be the renumbered sequences and let \(a_{i}=(a_{i1}, a_{i2}, \dotsc)\). Write all these sequences one below the other: \[\begin{align*}a_{1}&=a_{11}a_{12}a_{13}\dotsc\\ a_{2}&=a_{21}a_{22}a_{23}\dotsc\\ a_{3}&=a_{31}a_{32}a_{33}\dotsc\\\end{align*}\] Look at the sequence formed on the diagonal: \(a_{11}, a_{22}, \dotsc\) and consider the infinite sequence \(b=(b_{1}, b_{2}, \dotsc)\), such that \(b_{i}=a_{ii}\oplus 1\). On one hand, the sequence \(b\) must appear among \(a_{1}, a_{2}, \dotsc\). On the other hand, it cannot appear there: if \(b=a_{j}\) for some \(j\), then \(b_{j}=a_{jj}\), but \(b_{j}=a_{jj}\oplus 1\) (in other words, \(b\) differs from each of \(a_{i}\) in at least one position).