# 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

HallsofIvy
Homework Helper
Uh, that you didn't understand Cantor's argument?

In the first, place, it is not an "assumption" that "we have a bijection between |N| and |R| iff R list is complete." Since N is countable, any bijection must be a complete list. It is incorrect to say (as you may be) that Cantor is saying that there is no bijection because that particular list is not complete- the list was arbitrary. What Cantor showed was that ANY list must be incomplete.

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

You appear to have constructed the same list except that you have replace the "diagonal" digit by something that is neither the original digit nor Cantor's new digit. What is your point? There is no reason to believe you HAVE a "new" list. It is quite possible that the numbers you have in the new list were already somewhere in the old list- you don't know. An important point about going specifically down the "diagonal" in Cantor's proof is showing the the resulting new number CAN'T be in the list anywhere- because it differs from the nth number in the nth digit.

In any case, Cantor did NOT say "if the number is not 1, replace it by 1, if it is 1 replace it by 0". He only needs to set up some regular scheme for replacing each digit by some other digit in a clear way. In fact, what that shows is that, given any list, not only does there exist A number not on the list, but in fact, there exist an infinite number of real numbers not on the list.

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

Last edited:
Hurkyl
Staff Emeritus
Gold Member
Then I use r'', r''' ,r'''' ,... on top of your list.

And the diagonal argument applies to each of those as well.

Hi Hyrkyl,

As I see I it, we Don't need r'' ,r''' , r'''' ,... and so on.

r' is enough to show that Coator's argument can't work, if we construct the list as I did.

There are always countably many numbers that Cantor's function does not reach.

More than that, because it is an arbitrery list, there is no first number in the list, and this is how I constructed it.

It always goes to infinity in both directions but only a part of it is in the the range of Contor's function:
...
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 ... "Out of Contor's function range"
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 ... "In range"
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 ...
...

Please show me what mathematical logic forces me to define the first row to the checked list ?

(Dear Hurkyl please close or delete the other thread with the wrong name "digitalization" instead of "diagonalization", thank you)

Organic

Last edited:
Hurkyl
Staff Emeritus
Gold Member
See step (2) in the proof you wrote in the original post:

• (2) We may then enumerate the numbers in this interval as a sequence, { r1, r2, r3, ... }

This is a key step to the diagonal argument that you are neglecting.

You have a (countable) list, r' of decimals in the interval (0, 1). Your list may be enumerated as a sequence {s1, s2, s3, ...}, and the sequence s has exactly the same elements as r' does. Steps (3)-(5) prove the existance of a decimal, x, in (0, 1) that is not in the enumeration s, thus x must also not be in r'.

(a previous post gives an example of such a sequence s)

No matter how much effort you make in creating (countable) lists structured in complicated ways trying to circumvent this proof, step (2) always allows the list to be rewritten as a sequence and the proof holds.

HallsofIvy
Homework Helper
In other words, you don't understand the word "countable", you don't understand the word "list", and you don't understand Cantor's proof.

Thank you Hurkyl and HallsofIvy,

Cantor's proof holds because one and only one reason.

It compares between a list of numbers that have finite number of digits or infinitely many digits (with repetitions over scale, therefore they are Q numbers), and a list of numbers with infinitely many digits without repetitions over scales (irrational numbers).

If we take a list of all Q numbers with infinitely many digits and use Cantor's function, can we clearly show that we always get as a result an irrational number ?

Thank you.

Organic

Last edited:
Hurkyl
Staff Emeritus
Gold Member
Cantor's proof holds because one and only one reason.

It compares between a list of numbers that have finite number of digits or infinitely many digits (with repetitions over scale, therefore they are Q numbers), and a list of numbers with infinitely many digits without repetitions over scales (irrational numbers).

The (second) diagonalization argument has nothing to do with rational and irrational numbers.

If we take a list of all Q numbers with infinitely many digits and use Cantor's function, can we clearly show that we always get as a result an irrational number ?

If we take a list of all rational numbers and we use the diagonal argument to prove the existance of a real number not on that list, then of course that number has to be irrational.

Hi Hurkyl,

My question is: can we prove that the new number can never be a rational number ?

I mean no repetitions over scales.

I can construct a list of infinitely many rational numbers and than I can show that there is a new rational numbet, which is not in the list.

For example:

0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
0 . 3 0 2 3 0 2 3 0 2 3 0 2 ...
0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
0 . 7 8 1 1 1 7 8 1 1 1 7 8 ...
0 . 7 4 3 3 3 0 7 4 3 3 3 0 ...
0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
0 . 1 2 3 0 1 2 3 0 1 2 3 0 ...
0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
...
...
...

In this case x = 0.010101010101... , which is a new rational number not in the list of infinitely many rational numbers.

Therefore (by Cantor's first and second agruments) there are more rational numbers than rational numbers.

If we add this number to the list, we can rearenge the list in such a way that define a new rational number not in the list, and so on and so on.

Can you prove that the number of rearengments is finite ?

Thank you.

Organic

Last edited:
Hurkyl
Staff Emeritus
Gold Member
Therefore (by Cantor's first and second agruments) there are more rational numbers than rational numbers.

How does that follow?

Are you assuming that the list you provided contains every rational number? Why would you think that?

Cantor's first diagonal argument constructs a specific list of the rational numbers that is not the list you provided.

Hi Hurkyl,

My list is a decimal representation of any rational number in Cantor's first argument spesific list.

For example:

0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
0 . 7 8 1 1 1 7 8 1 1 1 7 8 ...
2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
...
...
...

Every non-zero decimal digit can be any number between 1 to 9.

Organic

Last edited:
HallsofIvy
Homework Helper
In this case x = 0.010101010101... , which is a new rational number not in the list of infinitely many rational numbers.

Therefore (by Cantor's first and second agruments) there are more rational numbers than rational numbers.
No, it proves that there are more rational numbers than were on your list. I can play that game too: 1, 2, 3, 4, ..., the list of all natural numbers, is a list of rational numbers. The number 1/2 is not on it! That proves nothing at all.

The point of Cantor's argument was to say "suppose we have a list of all real numbers" and then show that that leads to a contradiction.

If you are going to try to do the same thing with rational numbers- assume a list of all rational numbers and then construct a rational number that is not on it, the onus is on you to show that that number IS rational.

My list is a decimal representation of any rational number in Cantor's first argument spesific list.

This makes no sense at all. You haven't given a list, you give a few numbers, (not well defined, in fact it is not even clear that the numbers on the list ARE rational numbers) and no general formula for putting numbers on the list.

Hurkyl
Staff Emeritus
Gold Member
My list is a decimal representation of any rational number in Cantor's first argument spesific list.

Really?

(If you only answer one of these questions, do it for 10/99)

Hi Hurkyl ,Hi HallsofIvy,

The main idea of Cnator's second argument is to show that the real numbers list can never be a complete list.

If we have to correct the list by adding to it infinitely many Cantor's function results, it means that there can never be a bijection between |R| and |N|.

Cantor's first argument clearly shows that there is a bijection between |N| and |Q|.

There is no problem to represent any rational number by its decimal form.

And Q numbers decimal's form is finite or it is infinitely many digits with repetitions over scales.

But when we use Cantor's second argument on the decimal representations of Q numbers, we find exactly the same results as Cantor found between |N| and |R|.

|N|=|Q| by Cantor's first argument, but |N|<|Q| by Cantor's second argument.

My list is a decimal representation of any rational number in Cantor's first argument specific list.

For example:

0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
0 . 5 5 9 0 6 5 5 9 0 6 5 5 ...
0 . 3 3 3 3 3 3 3 3 3 3 3 3 ...
2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
...
...
...

Hurkyl, every non-zero decimal digit can be any number between 1 to 9, Because I use Cantor's function where the rules are:

A) Every 0 in the original diagonal number is turned to 1 in Cantor's new number.

B) Every non-zero in the original diagonal number is turned to 0 in Cantor's new number.

So, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.

Organic

Last edited:
jcsd
Gold Member
You miss understand the argument, what Cantor showed is that given any list of any size natural numbers vs irrational numbers between 1 and 0 it is always possible to prove that there are irrational numebsr not contained on the list, the reverse is not true however.

Hi jcsd,

Thank you.

Organic

Hurkyl
Staff Emeritus
Gold Member
If we have to correct the list by adding to it infinitely many Cantor's function results, it means that there can never be a bijection between |R| and |N|.

There is no bijection between |N| and |R| because every function from |N| to |R| is missing at least one real number.

Your use of the phrase "can never" seems to imply you think that, in the mathematical sense, something might not exist now but it could exist in the future. That is an incorrect interpretation of mathematics. A mathematical statement that is true now will be true 100 years from now and was true 1000 years ago; all that changes is what we've discovered.

So, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.

So tell me, where does 10/99 appear in your list?

Hi Hurkyl,

you wrote:
Your use of the phrase "can never" seems to imply you think that, in the mathematical sense, something might not exist now but it could exist in the future. That is an incorrect interpretation of mathematics. A mathematical statement that is true now will be true 100 years from now and was true 1000 years ago; all that changes is what we've discovered.
Well, I think it is depended on your point of view, which in this case is Platonism, which says that mathematics only discover timeless objective truth.

Let us say that I take this point of view, so I can easily change what I wrote to fit it to the Platonism point of view.

Here it is (and also added 10/99 to my list):

The main idea of Cnator's second argument is to show that the real numbers list can never be a complete list.

If we have to correct the list by adding to it infinitely many Cantor's function results, it means that there is no bijection between |R| and |N|.

Cantor's first argument clearly shows that there is a bijection between |N| and |Q|.

There is no problem to represent any rational number by its decimal form.

And Q numbers decimal's form is finite or it is infinitely many digits with repetitions over scales.

But when we use Cantor's second argument on the decimal representations of Q numbers, we find exactly the same results as Cantor found between |N| and |R|.

|N|=|Q| by Cantor's first argument, but |N|<|Q| by Cantor's second argument.

My list is a decimal representation of any rational number in Cantor's first argument specific list.

For example:

0 . 1 7 1 1 3 1 7 1 1 3 1 7 ...
1 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 4 2 1 3 4 2 1 3 4 2 1 3 ...
0 . 1 0 1 0 1 0 1 0 1 0 1 0 ...
0 . 3 3 3 3 3 3 3 3 3 3 3 3 ...
2 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 3 5 4 9 5 5 1 3 5 4 9 5 ...
3 . 0 0 0 0 0 0 0 0 0 0 0 0 ...
0 . 6 4 1 6 4 1 6 4 1 6 4 1 ...
0 . 3 0 2 0 3 0 2 0 3 0 2 0 ...
0 . 6 1 3 6 1 3 6 1 3 6 1 3 ...
0 . 2 7 1 0 2 7 1 0 2 7 1 0 ...
...
...
...

In this case Cantor's function result is 0.0101010101010101.... which is not in the list.

Every non-zero decimal digit can be any number between 1 to 9, Because I use Cantor's function where the rules are:

A) Every 0 in the original diagonal number is turned to 1 in Cantor's new number.

B) Every non-zero in the original diagonal number is turned to 0 in Cantor's new number.

For example, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.

Organic

Last edited by Organic on 10-21

Last edited:
HallsofIvy
Homework Helper
For example, there is no problem to use 0.333333... in the list because 3 (or any digit between 1 to 9) is always turned to 0, therefore our new number can always be a rational number.
You keep claiming "therefore our new number can always be a rational number" but you have given no proof of that. HOW can you prove that the new number WILL (not can) always be a rational number? Each digit of the new number is dependent upon the corresponding digit of a DIFFERENT rational number. HOW do you prove that those digits will either eventually be all zeroes or eventually repeat? That seems very unlikely to me.

For example, if the list of rational numbers between 0 and 1 starts (this is based on the standard listing used in the proof that rational numbers are countable):
0.50000...
0.33333...
0.66666...
0.25000...
0.50000...
0.75000...
0.40000...
0.16666...
0.60000...
etc.

then your function (set the digit to 1 if the original digit is 0, otherwise to 0) gives 0.000111101 etc. I see no evidence that this will eventually repeat. Since you are claiming that it will, it your responsibility to prove that.

By the way, please do not start getting "mystical" and appealing to different philosophies of mathematics. One's philosophy of mathematics has no bearing on how one proves theorems (with the possible exception of those weird "Brouwer-Constructionists!). I am certainly not a "Platonist" but I understood Hurkyl's statements completely.

If you add .101010101010... ("10/99") to your list, then by changing the nth digit you are guaranteeing that the new diagonal number formed will NOT be .101010... no matter where you put it in the list.
What if your list contains, at some point:
A=.110110110...
B=.00110110110...
C=.111011101110...
D=.000111011101110...
...
where going from A to C you simply use an additional 1 in the pattern and from A to B, from C to D, from E to F etc. you append as many zeros to the FRONT OF THE NUMBER (not within the pattern) as there are leading 1's in the number to get the next number. These are all clearly rational.
doing a straight diagonal change on this one will give:
.010010001000010000010000001...
Which is irrational. Of course we could reorder things to try to avoid this. Also, if we just say arbitrarily change the digits on the diagonal to any other digits that will certainly complicate the argument.
Just some things to think about...
Aaron

Hurkyl
Staff Emeritus
Gold Member
Well, I think it is depended on your point of view, which in this case is Platonism, which says that mathematics only discover timeless objective truth.

It does not depend on a point of view; it depends on the axiomatic definition of the quantifier "there exists".

My list is a decimal representation of any rational number in Cantor's first argument specific list.

Sorry, I meant to ask where 1/99 appears in the list.

Hi Hurkyl,

.010101010... (1/99) is not in the list exactly as Cantor's function real number result is not in the list.

Therefore in both cases (R list or Q list) we have to add Cantor's function resutltes to the list.

Therefore the list is not complete and we can come to the conclusion that |N|<|R| or |N|<|Q|.

Organic.

Last edited:
Hi Hurkyl,

If my original number is for example : 0.101010301010.... then by using the rule that changes any 0 to 1 and any non-zero to 0 I define the new number 0.01010101010... which is not in the list.

0.101010301010.... is not a rational number because it has not the exact repetition's pattern over scales, therefore it is not in the list.

So, in this case 0.01010101010... is the Cantor's function results which is not in the list and have to be added to the list.

This is the exact state between Cnator's function some result and the R list.

And I have found that this sate holds for Q list.

Therefore we can come to the conclusion that Cantor's second argument |N|<|R| but also |N|<|Q|.

Organic

Hi synergy, Hi HallsofIvy,

Fact number 1: We can represent all rational numbers in their decimal form.

Fact number 2: Any rational number, which is represented in its decimal form, has aleph0 digits.

Therefore there are no limits to the number of ways that Q list can be rearranged to give us some new Q number (which is not in the list) as a Cantor's function result.

Therefore |N|<|Q| by Cantor's second argument.

Organic

Last edited: