A question on Cantor's second digitalization argument.

  • Thread starter Organic
  • Start date
1,208
0
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.

From Wikipedia, the free encyclopedia:
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.


Please someone show my mistake.


Thank you.


Organic
 
Last edited:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
41,712
876
It doesn't help to post the same question twice.
 
1,208
0
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
 

Related Threads for: A question on Cantor's second digitalization argument.

Replies
36
Views
8K
  • Posted
Replies
5
Views
2K
Replies
12
Views
4K
  • Posted
Replies
10
Views
2K
Replies
19
Views
729
Replies
22
Views
1K
  • Posted
Replies
9
Views
2K
Replies
9
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top