- #176
cantormath
- 4
- 0
I don't see the arguement
Cantor's Diagonalization Argument
Theorem-The interval [0,1] is not countably infinite.
Proof:-The proof by contradiction proceeds as follows:
Assume (for the sake of argument) that the interval [0,1] is countably infinite. We may then enumerate all numbers in this interval as a sequence, ( r1, r2, r3, ... ) We already know that each of these numbers may be represented as a decimal expansion. We arrange the numbers in a list (they do not need to be in order). In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we chose the one ending in nines. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows:
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
We shall now construct a real number x in [0,1] by considering the kth digit after the decimal point of the decimal expansion of rk.
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
The digits we will consider are indicated in bold and illustrate why this is called the diagonal proof. From these digits we define the digits of x as follows.
if the kth digit of rk is 5 then the kth digit of x is 4
if the kth digit of rk is not 5 then the kth digit of x is 5
For the example above this will result in the following decimal expansion.
x = 0 . 4 5 5 5 5 5 4 ...
The number x is a real number (we know that all decimal expansions represent real numbers) in [0,1] (clearly). Hence we must have rn = x for some n, since we have assumped that ( r1, r2, r3, ... ) enumerates all real numbers in [0, 1]. However, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the nth decimal place from rn, so x is not in the sequence ( r1, r2, r3, ... ). This sequence is therefore not an enumeration of the set of all reals in the interval [0,1]. This is a contradiction.
Hence the assumption that the interval [0,1] is countably infinite must be false.
Q.E.D.
It is a direct corollary of this result that the set R of all real numbers is uncountable. If R were countable, we could enumerate all of the real numbers in a sequence, and then get a sequence enumerating [0, 1] by removing all of the real numbers outside this interval. But we have just shown that this latter list cannot exist. Alternatively, we could show that [0, 1] and R are the same size by constructing a bijection between them.
Cantor's Diagonalization Argument
Theorem-The interval [0,1] is not countably infinite.
Proof:-The proof by contradiction proceeds as follows:
Assume (for the sake of argument) that the interval [0,1] is countably infinite. We may then enumerate all numbers in this interval as a sequence, ( r1, r2, r3, ... ) We already know that each of these numbers may be represented as a decimal expansion. We arrange the numbers in a list (they do not need to be in order). In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we chose the one ending in nines. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows:
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
We shall now construct a real number x in [0,1] by considering the kth digit after the decimal point of the decimal expansion of rk.
r1 = 0 . 5 1 0 5 1 1 0 ...
r2 = 0 . 4 1 3 2 0 4 3 ...
r3 = 0 . 8 2 4 5 0 2 6 ...
r4 = 0 . 2 3 3 0 1 2 6 ...
r5 = 0 . 4 1 0 7 2 4 6 ...
r6 = 0 . 9 9 3 7 8 3 8 ...
r7 = 0 . 0 1 0 5 1 3 5 ...
...
The digits we will consider are indicated in bold and illustrate why this is called the diagonal proof. From these digits we define the digits of x as follows.
if the kth digit of rk is 5 then the kth digit of x is 4
if the kth digit of rk is not 5 then the kth digit of x is 5
For the example above this will result in the following decimal expansion.
x = 0 . 4 5 5 5 5 5 4 ...
The number x is a real number (we know that all decimal expansions represent real numbers) in [0,1] (clearly). Hence we must have rn = x for some n, since we have assumped that ( r1, r2, r3, ... ) enumerates all real numbers in [0, 1]. However, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the nth decimal place from rn, so x is not in the sequence ( r1, r2, r3, ... ). This sequence is therefore not an enumeration of the set of all reals in the interval [0,1]. This is a contradiction.
Hence the assumption that the interval [0,1] is countably infinite must be false.
Q.E.D.
It is a direct corollary of this result that the set R of all real numbers is uncountable. If R were countable, we could enumerate all of the real numbers in a sequence, and then get a sequence enumerating [0, 1] by removing all of the real numbers outside this interval. But we have just shown that this latter list cannot exist. Alternatively, we could show that [0, 1] and R are the same size by constructing a bijection between them.
Last edited:
