1549901369-Elements_of_Real_Analysis__Denlinger_

128 Chapter 2 • Sequences

rational numbers are listed more than once in the sequence f. By eliminating
the repetitions, we obtain a subsequence g off:

g: N---> Q (1-1 and onto).

This g is a 1-1 correspondence, showing that Q is countable. •

SOME UNCOUNTABLE SETS

Cantor further startled the mathematical world by proving the following
remarkable result, demonstrating once and for all that there is more than one
level of infinity.

Theorem 2.8. 7 The set IR of real numbers is uncountable. (It is impossible to
list the real numbers as a sequence.)

Proof. If the real numbers could be listed as a sequence, then the open
interval (0, 1) would be a subsequence. Thus, it suffices to prove that it is
impossible to list the elements of (0, 1) as a sequence. For contradiction, suppose
it is possible to list all the real numbers in (0, 1) as a sequence,

Each Xn has a decimal expansion. In the notation of Theorem 2.5.5, say

X1 = O.d11d12d13 ···din···

X2 = O.d21d22d23 · · · d2n · · ·

X3 = O.d31 d32d33 · · · d3n · · ·

Define a new decimal y = 0. e 1 e2e3 ···en··· by defining,

'efk E N, ek -:/= dkk, ek -:/= 0, and ek -:/= 9.

(16)

That is, each ek is different from dkk and is neither 0 nor 9. Then,

y -:/= x 1 , since y and x 1 differ in the first decimal place and e 1 -:/= 0 or 9;

y-:/= x2, since y and X2 differ in the 2nd decimal place and e 2 -:/= 0 or 9;