Cantor's diagonalization argument. Show that the unit

Chapter , Problem 4

(choose chapter or problem)

Cantor's diagonalization argument. Show that the unit interval [0, 1] is uncountable. i.e., its elements cannot be arranged in a sequence. Solution. Any number x in [0. 1] can be represented in terms of its decimal expansion. e.g. , 1/3 = 0.3333 . Note that most numbers have a unique decimal expansion, but there are a few exceptions. For example, 1 /2 can be represented as 0.5000 . . or as 0.49999 . '. It can be shown that this is the only kind of exception, i.e .. decimal expansions that end with an infinite string of zeroes or an infinite string of nines. Suppose, to obtain a contradiction, that the elements of [0, :1.] can be arrangedin a sequence Xl , X2, X3, .. , so that every element of [0, 1] appears in the sequence. Consider the decimal expansion of Xn : where each digit a belongs to {O, 1, ... , 9}. Consider now a number y constructed as follows. The nth digit of y can be 1 or 2, and is chosen so that it is different from the nth digit of Xn . Note that y has a unique decimal expansion since it does not end with an infinite sequence of zeroes or nines. The number y differs from each Xn , since it has a different nth digit. Therefore, the sequence Xl , X2, does not exhaust the elements of [0, 1] , contrary to what was assumed. The contradiction establishes that the set [0, 1] is uncountable.