The very first proof of uncountability of the reals was published by G. Cantor in 1874 - two years before the publication of his famous diagonalization process. Both proofs use the reductio ad absurum argument; even though, many consider the proofs constructive. We shall later see why that this may indeed be so.

For the proof, assume on the contrary that the real numbers could be counted, i.e., arranged in a sequence \{a_n\}, n = 1, 2, \ldots . We are going to exhibit a real number that is not included in that sequence thus obtaining a contradiction.

There are two possibilities:

First, if there are terms a_k and a_m, for some m, n, such that between the two there are no other terms of the sequence \{a_n\} a contradiction is immediate because between any two real numbers a, b there is always another one, say (a+b)/2. By our assumption, this one is not included into the sequence \{a_n\}.

Now, we may assume that between any two terms of the sequence there is at least one other term. This assumption will also lead to a contradiction. To see how, we shall define two sequences \{b_n\} and \{c_n\}, both constructed out of the terms of \{a_n\}.

For definiteness' sake, assume a_1 < a_2 and define b_1 = a_1 and c_{1}=a_2. The rest of the two sequences are formed recursively: for s > 1,

b_s is the first term of \{a_n\} that is between b_{s-1} and c_{s-1}.
c_s is the first term of \{a_n\} that is between b_{s} and c_{s-1}.

This construction insures that sequence b_n is increasing, whereas sequence c_n is decreasing. In addition, all the terms of the former are strictly less than all the terms of the latter. Furthermore, note that if b_n = a_k and b_{n+1} = a_m, then k < m; a similar statement holds for the sequence \{c_n\}.

Let L be the least upper bound of \{c_n\}. Note that c_k < L < b_m, for all k, m.

We are going to show that L is the real number we are looking for. In other words, L is not in the sequence \{a_n\}. Suppose otherwise. Then L = a_m for some m. Choose t such that b_t = a_k and c_t = a_r with k, r > m; this is possible because the bís and cís are always coming from deeper and deeper in the sequence \{a_n\}.

By construction of the b and c sequences, for every i ≤ max\{k, r\}, we have a_i \le c_t or a_i \ge b_t . But from the above, c_t < L < b_t, which is the promised contradiction that completes the proof.

References

  1. G. Cantor, Über eine Eigenschaft des Inbegriffes aller reelen algebraischen Zahlen, J. Reine Angew. Math. 77 (1874) 258Ė262.
  2. M. Krebs, T. Wright, On Cantorís First Uncountability Proof, Pickís Theorem, and the Irrationality of the Golden Ratio, Am. Math. Monthly, 117 (AugustĖSeptember 2010) 633-637