# A question on Cantor's second digitalization argument.

A question on Cantor's second diagonalization argument.

Hi,

Cantor used 2 diagonalization arguments.

On the first argument he showed that |N|=|Q|.

On the second argument he showed that |Q|<|R|.

I have some question on the second argument.

http://en.wikipedia.org/wiki/Cantor's_diagonal_argument

The proof by contradiction proceeds as follows:
• (1) Assume that the interval (0,1) is countably infinite.
• (2) We may then enumerate the numbers in this interval as a sequence, { r1, r2, r3, ... }
• (3) We shall now construct a real number x between 0 and 1 by considering the nth digit after the decimal point of the decimal expansion of rn. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows.
r1 = 0 . 0 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 0 ...
...
The digits we will consider are indicated in bold. From these digits we define the digits of x as follows.

o if the nth digit of rn is 0 then the nth digit of x is 1
o if the nth digit of rn is not 0 then the nth digit of x is 0
For the example above this will result in the following decimal expansion.
x = 0 . 1 0 0 1 0 0 1 ...
The number x is clearly a real number between 0 and 1.
• (4) However, it differs in the nth decimal place from rn, so x is not in the set { r1, r2, r3, ... }.
• (5) This set is therefore not an enumeration of all the reals in the interval (0,1).
• (6) This contradicts with (2), so the assumption (1) that the interval (0,1) is countably infinite must be false.

Note: Strictly speaking, this argument only shows that the number of decimal expansions of real numbers between 0 and 1 is not countably infinite. But since there are expansions such as 0.01999... and 0.02000... that represent the same real number, this does not immediately imply that the corresponding set of real numbers is also not countably infinite. This can be remedied by disallowing the decimal expansions that end with an infinite series of 9's. In that case it can be shown that for every real number there is a unique corresponding decimal expansion. It is easy to see that the proof then still works because the number x contains only 1's and 0's in its decimal expansion.

My question is:

The first assumption was that we have a bijection between |N| and |R| iff R list is complete.

Then Cantor showed that there is a way to construct a real number x between 0 and 1, that cannot be put in 1-1 correspondence with any natural number.

Therefore, there are more real numbers between 0 and 1 then all natural numbers.

Now I construct the list in another way.

...
r7' = 0 . 0 1 0 5 1 3 8 ...
r6' = 0 . 9 9 3 7 8 0 8 ...
r5' = 0 . 4 1 0 7 0 4 6 ...
r4' = 0 . 2 3 3 5 1 2 6 ... New list
r3' = 0 . 8 2 0 5 0 2 6 ...
r2' = 0 . 4 0 3 2 0 4 3 ...
r1' = 0 . 1 0 0 1 0 0 1 ...(= Cantor's switching function resultes)
----------------------
r1 = 0 . 0 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 ... Original list
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 0 ...
...

By constructing the above list I show that there are infinitely countably many r' numbers that are not covered by Cantor's switching function.

Therefore Cantor's digitalization's second argument doesn't hold.

Thank you.

Organic

Last edited:

Hurkyl
Staff Emeritus
Gold Member
Let's write down an enumeration of your list:

Code:
r1  = 0.0105110...
r1' = 0.1001001...
r2  = 0.4132043...
r2' = 0.4032043...
r3  = 0.8245026...
r3' = 0.8205026...
...
Then, just like any other enumeration, you apply Cantor's diagonal argument and you can generate a number that cannot appear in the list. In this case, 0.110010...

HallsofIvy
Homework Helper
It doesn't help to post the same question twice.

Hi HallsofIvy,

By complete I mean that there are no numbers left out not in R and not in N (means bijection between N and R).

The R list is arbitrary and it is one and only one list.
"New list" and "Original list" are the same one list.

All what I showed is that we can construct it in such a way that Cantor's function can never reach all of it.

Here it is again:
...
r7' = 0 . 0 1 0 5 1 3 8 ...
r6' = 0 . 9 9 3 7 8 0 8 ...
r5' = 0 . 4 1 0 7 0 4 6 ...
r4' = 0 . 2 3 3 5 1 2 6 ... "New list"
r3' = 0 . 8 2 0 5 0 2 6 ...
r2' = 0 . 4 0 3 2 0 4 3 ...
r1' = 0 . 1 0 0 1 0 0 1 ...(= Cantor's function resultes)
----------------------
r1 = 0 . 0 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 ... "Original list"
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 0 ...
...

You Wrote:
Let's write down an enumeration of your list:

r1 = 0.0105110...
r1' = 0.1001001...
r2 = 0.4132043...
r2' = 0.4032043...
r3 = 0.8245026...
r3' = 0.8205026...
...
Then I use r'', r''' ,r'''' ,... on top of your list.

Organic

Hurkyl
Staff Emeritus