# Cantor's diagonal argument is wrong

Show 40 post(s) from this thread on one page
Page 1 of 3 123 Last
• March 10th 2013, 09:11 PM
Nylo
Cantor's diagonal argument is wrong
Hi all,

First of all, apologies if I make any grammar or vocabulary mistakes as English is not my native language.

In this post, I will demonstrate that Cantor's diagonal argument, which is the best known and accepted as the most elegant demonstration that Reals are not countable, i.e. that the cardinality of the Reals set is greater than that of the Naturals, is actually wrong. I'm not 100% sure about his conclusion being wrong, but the process he follows to reach it certainly is. It may look elegant, but it is wrong and misleading.

For those of you that are not familiar with this demonstration or have long forgotten the details, here is a link to the wikipedia page about it. From now on, all my references to the Cantor's demonstration will refer to the way it is explained in that wikipedia page.

All of Cantor's demonstration is based on, no matter which function f we have created between the naturals and T (defined as the set of all possible infinite sequences of 0s and 1s), if he can find one sequence of 0s and 1s that would not exist in the image of the function, then it follows that the function is not bijective. And he then goes on to provide a method for finding such a sequence. And he says: given that I have been able to find such a sequence, the function cannot be bijective.

Now, this is the key: the method he provides to find such a sequence is fatally flawed.

In order to find his s0 sequence of zeroes and ones, Cantor's method consists on establishing a small difference with the images of each and every natural number. With each and every sn. In particular, for a generic sn, he establishes the difference in the nth digit of the sequence. Now, the obvious problem is that in order to actually find that sequence, he needs to do an infinite number of comparisons with an infinite number of terms of which he knows nothing a priori, as the sequence of sequences of 0s and 1s does not need to be in any specific order. And he has not demonstrated that it is possible to actually do such a thing in order to actually find such a s0
sequence, when the number of operations required to do such a thing is literally endless.

Well, it may be an interesting concept, but it is unreal, and I can demonstrate that such a thing cannot be done, by providing another absolutely clear example. By following Cantor's way of reasoning, I would be able to demonstrate that the Naturals themselves, are not countable! Which is obviously wrong. But I could show it to be right only by accepting that I can find a number for which I need to do an infinite number of operations. Given a sequence of ALL natural numbers, I will show the way to obtain a natural number which does not belong to the sequence. Absurd? Well, if it's not absurd for Cantor...

Cantor goes one by one through all the sequences of 1s and 0s establishing a difference with each of them, and in each individual step of that process, he has certainly found a sequence that belongs to T and is different from all sequences already examined. That's not enough to claim that, after finishing with the infinite ammount of them, he will still have a sequence that belongs to T and is different from all others, even if such a thing is true for any finite number of sequences. In the example I'm about to provide, for a sequence of all natural numbers, I will show exactly the same. In each step of the process, I will have found a number which is certainly natural and is certainly different from all the naturals already examined. If the fact that this is true for any finite number of naturals examined allowed me to say that it is also true for the infinity of them, then by Cantor's reasoning I would have found that the naturals are not countable. And that's why Cantor's argument is wrong.

Let Sn be my sequence of ALL naturals, all different. How will I calculate a natural (S0) that doesn't belong to the sequence? Like Cantor, I am going to do so in steps, each of them involving one natural of the sequence and one operation. I will call S0,n the nth step to calculate my final S0. Cantor does exactly the same, only for him, his s0,n is also the nth digit of his s0 final sequence, but anyway it is a term that requires a calculation, and he cannot get his final s0 without that calculation.

For me, S0,n = max (S0,n-1 -1; Sn) +1. Or in other words, in each step, I check if the next Natural involved is equal or bigger than my previous result, and in case it is, my new result will be equal to the new Natural involved, plus 1. Otherwise I keep the same result as in the previous step.

With this procedure, for ANY finite n number of Naturals examined, I will certainly have found a Natural that is different (bigger) from all of the Si of the sequence, with i <= n. Now if, from this, like Cantor does, I could conclude that the same is true for the infinity of terms that my infinite sequence contains, I would have described a way to find one Natural number which is bigger that ALL of the naturals of this infinite sequence which was meant to contain them all. I would have found one natural which is bigger than all others in the sequence. So this natural I would have found would not exist within my sequence. And therefore by Cantor's reasoning, no function N -> N could be bijective.

WRONG! You cannot claim such a thing! You cannot pretend that you can find a number which, in fact, you cannot find, because finding it requires an infinite number of operations and is, therefore, impossible! Infinite means it never ends! I'm sorry Cantor, but life on earth and the Universe itself would have long ended before your method could find s0. That's because to establish a difference with every sequence of the infinite number of them, you also need to do so with the LAST one. And there is not such a thing as a last element in an infinite sequence. You can do NO OPERATION THAT REQUIRES THEM ALL. You can only do that with a finite number of terms. You cannot with an infinite number of them, unless the sequence trends towards some value known in advance and in a particular way, and this is not the case that you are dealing with. It's, actually, like trying to find a natural number that is bigger than all other natural numbers. Impossible. You cannot claim that such a thing exists, like you do. It doesn't.

And here ends my demonstration that Cantor's diagonal argument is wrong, and it is so by accepting a wrong premise, that his announced s0 does, in fact, exist.

• March 11th 2013, 05:36 AM
zzephod
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Nylo
Hi all,

First of all, apologies if I make any grammar or vocabulary mistakes as English is not my native language.

In this post, I will demonstrate that Cantor's diagonal argument, which is the best known and accepted as the most elegant demonstration that Reals are not countable, i.e. that the cardinality of the Reals set is greater than that of the Naturals, is actually wrong. I'm not 100% sure about his conclusion being wrong, but the process he follows to reach it certainly is. It may look elegant, but it is wrong and misleading.

For those of you that are not familiar with this demonstration or have long forgotten the details, here is a link to the wikipedia page about it. From now on, all my references to the Cantor's demonstration will refer to the way it is explained in that wikipedia page.

All of Cantor's demonstration is based on, no matter which function f we have created between the naturals and T (defined as the set of all possible infinite sequences of 0s and 1s), if he can find one sequence of 0s and 1s that would not exist in the image of the function, then it follows that the function is not bijective. And he then goes on to provide a method for finding such a sequence. And he says: given that I have been able to find such a sequence, the function cannot be bijective.

Now, this is the key: the method he provides to find such a sequence is fatally flawed.

In order to find his s0 sequence of zeroes and ones, Cantor's method consists on establishing a small difference with the images of each and every natural number. With each and every sn. In particular, for a generic sn, he establishes the difference in the nth digit of the sequence. Now, the obvious problem is that in order to actually find that sequence, he needs to do an infinite number of comparisons with an infinite number of terms of which he knows nothing a priori, as the sequence of sequences of 0s and 1s does not need to be in any specific order. And he has not demonstrated that it is possible to actually do such a thing in order to actually find such a s0
sequence, when the number of operations required to do such a thing is literally endless.

Well, it may be an interesting concept, but it is unreal, and I can demonstrate that such a thing cannot be done, by providing another absolutely clear example. By following Cantor's way of reasoning, I would be able to demonstrate that the Naturals themselves, are not countable! Which is obviously wrong. But I could show it to be right only by accepting that I can find a number for which I need to do an infinite number of operations. Given a sequence of ALL natural numbers, I will show the way to obtain a natural number which does not belong to the sequence. Absurd? Well, if it's not absurd for Cantor...

Cantor goes one by one through all the sequences of 1s and 0s establishing a difference with each of them, and in each individual step of that process, he has certainly found a sequence that belongs to T and is different from all sequences already examined. That's not enough to claim that, after finishing with the infinite ammount of them, he will still have a sequence that belongs to T and is different from all others, even if such a thing is true for any finite number of sequences. In the example I'm about to provide, for a sequence of all natural numbers, I will show exactly the same. In each step of the process, I will have found a number which is certainly natural and is certainly different from all the naturals already examined. If the fact that this is true for any finite number of naturals examined allowed me to say that it is also true for the infinity of them, then by Cantor's reasoning I would have found that the naturals are not countable. And that's why Cantor's argument is wrong.

Let Sn be my sequence of ALL naturals, all different. How will I calculate a natural (S0) that doesn't belong to the sequence? Like Cantor, I am going to do so in steps, each of them involving one natural of the sequence and one operation. I will call S0,n the nth step to calculate my final S0. Cantor does exactly the same, only for him, his s0,n is also the nth digit of his s0 final sequence, but anyway it is a term that requires a calculation, and he cannot get his final s0 without that calculation.

For me, S0,n = max (S0,n-1 -1; Sn) +1. Or in other words, in each step, I check if the next Natural involved is equal or bigger than my previous result, and in case it is, my new result will be equal to the new Natural involved, plus 1. Otherwise I keep the same result as in the previous step.

With this procedure, for ANY finite n number of Naturals examined, I will certainly have found a Natural that is different (bigger) from all of the Si of the sequence, with i <= n. Now if, from this, like Cantor does, I could conclude that the same is true for the infinity of terms that my infinite sequence contains, I would have described a way to find one Natural number which is bigger that ALL of the naturals of this infinite sequence which was meant to contain them all. I would have found one natural which is bigger than all others in the sequence. So this natural I would have found would not exist within my sequence. And therefore by Cantor's reasoning, no function N -> N could be bijective.

WRONG! You cannot claim such a thing! You cannot pretend that you can find a number which, in fact, you cannot find, because finding it requires an infinite number of operations and is, therefore, impossible! Infinite means it never ends! I'm sorry Cantor, but life on earth and the Universe itself would have long ended before your method could find s0. That's because to establish a difference with every sequence of the infinite number of them, you also need to do so with the LAST one. And there is not such a thing as a last element in an infinite sequence. You can do NO OPERATION THAT REQUIRES THEM ALL. You can only do that with a finite number of terms. You cannot with an infinite number of them, unless the sequence trends towards some value known in advance and in a particular way, and this is not the case that you are dealing with. It's, actually, like trying to find a natural number that is bigger than all other natural numbers. Impossible. You cannot claim that such a thing exists, like you do. It doesn't.

And here ends my demonstration that Cantor's diagonal argument is wrong, and it is so by accepting a wrong premise, that his announced s0 does, in fact, exist.

And still you are wrong.

Cantor's diagonal argument, given the assumption that the reals are enumerable, produces a convergent sequence of reals (which happen to be rational but that is not important) the limit of which is not in the assumed enumeration. By the construction of the reals this limit is in the reals.

Your argument fails because you do not have the completeness properties of the reals to fall back upon.
.
• March 11th 2013, 06:44 AM
Nylo
Re: Cantor's diagonal argument is wrong
Hi zzephod,

Notice that I don't reject that Cantor's s0 would be real. It certainly would. But to prove that it is not in the sequence, you need to do an infinite operation. What this means is that, no matter how good your approximation to s0 is, how close you get to s0, you will always find that your approximation DOES EXIST in the sequence. There are always more rows at the bottom. And given that you will never be able to know s0 exactly, you will never be able to claim having found a sequence which was not in the original sequence of sequences.

Look at this example. Imagine that I build my infinite sequence of sequences this way:

s2 = 1,0,0,0,0,0,0,0... (same)
s3 = 1,1,0,0,0,0,0,0... (same)

and each new sn just adds a new 1. The last element of that sequence would be, basically, all 1s, that would be the "limit". A limit that we never reach, as the list is endless, but that doesn't matter to Cantor, who insists on finding a diagonal which cannot be found, because an infinite sequence of sequences with infinite digits produces a Matrix that is not necessarily square. In fact, it is shapeless. It's like pretending that an infinite plane's shape is square, or finding what is the diagonal of an infinite plane. Cantor's method would produce an s0 that he would claim to be the diagonal, but that's only true if the matrix is square and that's something that makes no sense to claim. Cantor's s0 would look like this, given the above sequence, after he has finished:

s0= 1,1,1,1,1,1,1,1,1,1,1,1,1.... (ad infinitum) ...1,1,0. And he would say, as this is the oposite of the diagonal, it is none of the sequences of my sequence. But wait! What do you mean, that it is none of them? If I have built the sequence in the way that I said, s0 of course exists in my sequence. My sequence includes all possible sequences of 1s followed by 0s, including all 1s and all 0s. So s0 is a particular case, and it IS there. The problem is that in this case Cantor would not have found the diagonal, as my matrix is not square. He would think it is, but it isn't. This matrix I have created has strictly 1 more rows than columns, despite both the number of rows and columns being infinite. Indeed, for a sequence of any fixed number of digits n, the number of combinations of 1s followed by 0s is n+1.

Cantor's method can only work if, in the infinite sequence of infinite sequences, both infinites are exactly the same number, making the resulting matrix perfectly square. He has no basis to claim such a thing. Two infinites cannot be compared unless you reach them as limits of algebraic expresions that you can compare. And what is it that allows Cantor to claim that those two infinites are exactly the same number in any sequence that I may propose? I've just proposed one that wasn't.

Regards.
• March 11th 2013, 09:46 AM
Zeno
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Nylo
Cantor's method can only work if, in the infinite sequence of infinite sequences, both infinites are exactly the same number, making the resulting matrix perfectly square.

I agree with you on this Nylo.

In fact, I have a similar but different proof of Cantor's fallacy.

For example consider the following list of 2-digit binary numbers

$\begin{array}{cc} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ \end{array}$

Take note that this is a "complete list". It contains every possible 2-digit binary number. There simply are no more. So it's a complete list. But it's also clearly not a square list.

Now if we go down this list diagonally can we produce a new number that is not on the list? The answer is no, we can't.

We start with the first column of the first row and change that 0 to a 1 to make our new number different from that row.
then we move down to the second column second row and change that 1 to a 0 to make our new number different from that row.

Have we then produced a new number that isn't already on our list? No we haven't. The number we produced is 10 which is the very next number on our list.

It's already on the list. Why? Because any list of number represented by our numerical system is necessarily far taller than it is wide. This is even true in binary notion which I just used. However, this becomes far worse when using the decimal system where each digit can be one of ten symbols 0 thru 9. A mere two column list would be 100 rows long just to fit in every possible 2-digit number.

If this method can't even work in a simple finite case, then it certainly can't be extended to an infinite case where things would just become infinitely worse.

Cantor's "proof" is flawed because he's assuming a "Square List" which is a false assumption.

Cantor's proof could only work if numeral lists were "square", but they aren't "square" and they can't be made to be square. So it's an invalid proof.

So I agree with your conclusion. (Clapping)

But unfortunately the mathematical community can't seem to see this error for some strange reason.

Cantor's diagonalization "proof" is not a valid proof, period. Yet it's being taught to math students in math textbooks all the time and no one seems to have caught this obvious mistake. Cantor himself should have known better.

But I doubt that you'll get too many mathematicians to agree because they have all been formally taught to accept this "proof" as being valid. But it's not a valid proof.

This doesn't mean that the conclusion of the proof is necessarily wrong. But it does show that Cantor's "proof" does not prove this conclusion. It's a logically flawed piece of reasoning. Period.

But you'll be hard-pressed to get the mathematical community to own up to it. I wish you the best of luck with that.
• March 11th 2013, 10:29 AM
HallsofIvy
Re: Cantor's diagonal argument is wrong
Yes, it is extremely difficult to get the mathematical community to "own up to" a false statement. And what nylo is saying is simply false. The crucial point is
Quote:

WRONG! You cannot claim such a thing! You cannot pretend that you can find a number which, in fact, you cannot find, because finding it requires an infinite number of operations and is, therefore, impossible!
Yes, you can! We do it every day when we work with $\pi$, $\sqrt{2}$, or even 1/3, each of whic has an infinite number of digits. We deal with infinite sequences and infinite series in basic Calculus courses. Have you never taken Calculus?

Quote:

Notice that I don't reject that Cantor's s0 would be real. It certainly would. But to prove that it is not in the sequence, you need to do an infinite operation. What this means is that, no matter how good your approximation to s0 is, how close you get to s0, you will always find that your approximation DOES EXIST in the sequence.
What "approximation" are you talking about? There are no approximations involved here.

Quote:

There are always more rows at the bottom. And given that you will never be able to know s0 exactly, you will never be able to claim having found a sequence which was not in the original sequence of sequences.
Again, you are asserting that we cannot have numbers involving an infinite number of decimal places. That would remove all irrational numbers and most rational numbers (all those except fractions whose denominators involve only powers of 2 and 5. Do you really want to assert that neither 1/3 nor 1/7 can be written as decimals?

Quote:

Look at this example. Imagine that I build my infinite sequence of sequences this way:

s2 = 1,0,0,0,0,0,0,0... (same)
s3 = 1,1,0,0,0,0,0,0... (same)

and each new sn just adds a new 1. The last element of that sequence would be, basically, all 1s, that would be the "limit".
No, there is no "last element".

Quote:

A limit that we never reach, as the list is endless, but that doesn't matter to Cantor, who insists on finding a diagonal which cannot be found, because an infinite sequence of sequences with infinite digits produces a Matrix that is not necessarily square. In fact, it is shapeless. It's like pretending that an infinite plane's shape is square, or finding what is the diagonal of an infinite plane. Cantor's method would produce an s0 that he would claim to be the diagonal, but that's only true if the matrix is square and that's something that makes no sense to claim. Cantor's s0 would look like this, given the above sequence, after he has finished:
s0= 1,1,1,1,1,1,1,1,1,1,1,1,1.... (ad infinitum) ...1,1,0. And he would say, as this is the oposite of the diagonal, it is none of the sequences of my sequence. But wait! What do you mean, that it is none of them? If I have built the sequence in the way that I said, s0 of course exists in my sequence. My sequence includes all possible sequences of 1s followed by 0s, including all 1s and all 0s. So s0 is a particular case, and it IS there. The problem is that in this case Cantor would not have found the diagonal, as my matrix is not square. He would think it is, but it isn't. This matrix I have created has strictly 1 more rows than columns, despite both the number of rows and columns being infinite. Indeed, for a sequence of any fixed number of digits n, the number of combinations of 1s followed by 0s is n+1.

Cantor's method can only work if, in the infinite sequence of infinite sequences, both infinites are exactly the same number, making the resulting matrix perfectly square. He has no basis to claim such a thing. Two infinites cannot be compared unless you reach them as limits of algebraic expresions that you can compare. And what is it that allows Cantor to claim that those two infinites are exactly the same number in any sequence that I may propose? I've just proposed one that wasn't.
That doesn't even make sense. The statement the "'infinites" are or are not "exacty the same number" makes no sense. "infinities" are NOT numbers in sense that you are using the word.
• March 11th 2013, 10:37 AM
zzephod
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Nylo
Hi zzephod,

Notice that I don't reject that Cantor's s0 would be real. It certainly would. But to prove that it is not in the sequence, you need to do an infinite operation. What this means is that, no matter how good your approximation to s0 is, how close you get to s0, you will always find that your approximation DOES EXIST in the sequence. There are always more rows at the bottom. And given that you will never be able to know s0 exactly, you will never be able to claim having found a sequence which was not in the original sequence of sequences.

Every real number is somewhere on the list by hypothesis. If $r_n$ is the $n$-th number on the list the Cantor number corresponding to the list differs from $r_n$ in its $n$-th place. Hence for every number on the list the Cantor number of the list differs from it in at least one place.

If you insist on a checking procedure try this:

I give you a real number $x$, you find its' position $n$ in the list (by hypothesis it must be on the list). Then the $n$ digit approximation to the Cantor number by construction is has all its digits equal to the first $n$ digits of the Cantor number and it differs from $x$ in its last place. Hence the Cantor number differs from $x$.

Thus the Cantor number is different from every real in the list (that is no real number can be found that is equal to the Cantor number for the list, but as the Cantor number is a real this is a contradiction and so the hypothesis that the reals are enumerable fails). At no point in this checking procedure do you need the complete expansion of the Cantor number for the list.

Now you could argue that the very first step of the checking procedure can't be done, in which case we are in the realm of computable real numbers (which are enumerable) but Cantor's argument proves that there is no effective (that is computable) enumeration. Which in my opinion is an even neater result.

Finally, if I were moderating MHF I would close this thread as it will go nowhere. Experience on the web indicates that one will never convince those who have got it into their heads that Cantor's construction is wrong (within its' own terms of reference)
.
• March 11th 2013, 11:22 AM
jakncoke
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by zzephod
Every real number is somewhere on the list by hypothesis. If $r_n$ is the $n$-th number on the list the Cantor number corresponding to the list differs from $r_n$ in its $n$-th place. Hence for every number on the list the Cantor number of the list differs from it in at least one place.

If you insist on a checking procedure try this:

I give you a real number $x$, you find its' position $n$ in the list (by hypothesis it must be on the list). Then the $n$ digit approximation to the Cantor number by construction is has all its digits equal to the first $n$ digits of the Cantor number and it differs from $x$ in its last place. Hence the Cantor number differs from $x$.

Thus the Cantor number is different from every real in the list (that is no real number can be found that is equal to the Cantor number for the list, but as the Cantor number is a real this is a contradiction and so the hypothesis that the reals are enumerable fails). At no point in this checking procedure do you need the complete expansion of the Cantor number for the list.

Now you could argue that the very first step of the checking procedure can't be done, in which case we are in the realm of computable real numbers (which are enumerable) but Cantor's argument proves that there is no effective (that is computable) enumeration. Which in my opinion is an even neater result.

Finally, if I were moderating MHF I would close this thread as it will go nowhere. Experience on the web indicates that one will never convince those who have got it into their heads that Cantor's construction is wrong (within its' own terms of reference)
.

although i do agree, usually these threads go no where, the poster is not really being rude and disruptive and i do like that there are some people who post questions on this forum that are actually trying to think about mathematics rather than wait for someone to post the answer. Unless this thread becomes really disruptive, i see no point in closing it. You have a choice to not look or engage in this thread, so really, no point in discouraging the poster by preemptively closing the thread.
• March 11th 2013, 11:35 AM
Zeno
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by HallsofIvy
Yes, it is extremely difficult to get the mathematical community to "own up to" a false statement. And what nylo is saying is simply false.

I don't necessarily support Nylo's infinite series argument. I was addressing the observation that Cantor's argument does indeed require the list of numbers to be square.

I hand you the following finite list of binary numbers. Namely the completed set of numbers that can be formed using only two binary digits:

$\begin{array}{cc} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ \end{array}$

Then I ask you to use Cantor's diagonalization argument to produce a new number that isn't on my list.

Can you do it? No, you clearly cannot. Cantor's diagonal method does not go down the list fast enough to cover all possible numbers on the list. If you use Cantor's method you'll create the binary number 10 and proclaim that it's not already on my list, but that would be false in this finite situation, because that number is indeed on my list, you're diagonalization method of finding a number not on the list was simply inefficient and cannot be used to accomplish the task.

Well, if you can't even do this for a finite list of numbers, then what right would you have to proclaim that you could do it for an infinite list?

You would always be behind no matter how far out you go. In fact the further out you go the further behind the actual list you get.

I offered a binary list of numbers because it's easy to see that this will always be the case. Plus the binary number system of enumerating numbers is as low as we can go. So this proves it for the best possible scenario. Even binary representations of numbers require rectangular lists that are at least twice as tall as they are wide in the simplest case of only two binary digits. Take it out to a four-digit binary number and you've got a list that only four columns wide, but 16 rows tall. So it get's worse with every digit you add to the list.

With decimal notion the situation is far worse. A single 2-digit list is 100 rows long!

00
01
02
03
04
05
.
.
.
95
96
97
98
99

How could you ever hope to use Cantor's diagonalization method to produce a new number that's not on this list?

And if you can't do it for a simple finite case, then why on earth should I believe that you should be able to do it for an infinitely long list?

Lists of numbers that contain every possible number (which is also a critical assumption) simply aren't square. And this includes decimal representations. Writing the numbers out as 0.1234... doesn't change a thing. The same geometry applies to completed lists of numbers.

Therefore Cantor's diagonalization "proof" is flawed.

It can't even be made to work in a finite case how can he possible claim to extend this to infinity?

He will always be behind the list, no matter how far he claims to have gone out.

Moreover, you can easily prove that this is indeed the case. Simply stop Cantor's process at any point and check out the "new" number you've created thus far. Is that number on the list "above" where you've been working? No, of course not because you only have numbers that you've created using the diagonal method. However, if you ask "Is this new number you've just created a legitimate rational number?" The answer necessarily has to be YES! Every truncated decimal number is indeed a rational number.

So at no point does Cantor ever create a "new" number that isn't already on the list of all rational numbers. When is he supposed to accomplish this feat? In his LAST infinite step? Does it even make any sense to speak about a LAST step in a supposedly infinite process?

This is the problem with Cantor. He's thinking in terms of "Completed Infinities" like as if he can actually complete this process, without realizing that no matter how far he carries this process out he will always be behind the list in terms of the vertical direction. In fact, with every new digit he creates he becomes exponentially further behind the list.

Add a 3rd digit to our list of decimal numbers and suddenly the length of that list becomes almost 1000 rows tall. And so on. With every digit you add the list of all possible numbers grows in depth exponentially.

So Cantor's proof is no proof at all. It's a totally bogus argument.

He would need to show that this can be made to make sense in a finite case first, and then extend that idea to infinity. But he clearly failed to show this because it is flat out impossible.

This diagonal method of creating a new number that isn't already on a complete list of numbers is a totally wrong idea to begin with.

It's a false argument that has no merit.

Complete lists of numerals are simply not square. Period. Yet Cantor's proof requires that they must be square.

Therefore Cantor's proof is flawed. It's not a proof at all.

I've been arguing this since back in high school. It just amazes me why mathematicians can see this.

It's so obvious to me.

If his conclusion is true that's just a lucky coincidence because his diagonalization method does not constitute a legitimate proof of his claim.
• March 12th 2013, 08:27 AM
Nylo
Re: Cantor's diagonal argument is wrong
Thanks a lot for your response.

Quote:

Originally Posted by HallsofIvy

Yes, you can! We do it every day when we work with $\pi$, $\sqrt{2}$, or even 1/3, each of whic has an infinite number of digits. We deal with infinite sequences and infinite series in basic Calculus courses. Have you never taken Calculus?

Excuse me, I may have missed the astonishing news of the final calculation of $\pi$. When did it happen? All I know is that a huge numbers of decimals are known. I think it is in the order of trillions. This means that ANY result in which $\pi$ is involved, is not an absolutely accurate result (unless $\pi$ cancels itself somewhere in the formula). It is only an approximation. A very good one if you want, but just that. And of course we work with it. Because in the real world (no pun intended) we do not need absolute accuracy. We only need "good enough" accuracy. In fact, in the real world, the exact value of $\pi$ is not needed at all. Because it establishes a relationship between the radius and the circunference of a perfect circle, and perfect circles only exist in the world of ideas, we can't make absolutely perfect circles, neither can Nature, the perfect circle doesn't exist in the whole universe. Only "good enough" approximations to the perfect circle exist. So we do, indeed, work with $\pi$ as an idea. But when it comes to transform the calculation to some value, we will only get approximations.

By the way, 1/3 does not necessarily have an infinite number of decimals. Only if you choose a base that is not a multiple of 3, then it will have infinite decimals. But in base 3, for eample, 1/3 is expressed as "0.1". This happens because it is rational. The others are irrational and will have infinite decimals no mater which base you choose to represent their value.

Quote:

What "approximation" are you talking about? There are no approximations involved here.
Until you finish calculating s0 (and you can't, in the same way that you cannot finish calculating $\pi$), all you have is an approximation to it. And the approximation will be in the list. So your claim that you have found a number that is not in the list, is wrong. You haven't. You also haven't found $\pi$. But with $\pi$, you know it is there, because you have a mathematical expression that calculates it, even if it would take eons to try to finish it and it would still not be over. With Cantor's method to find s0, you don't have such a thing. No mathematical expression that allows you to deduce that the final number would indeed exist. For such a calculation to be provided, you would need to know how the sequence of numbers has been built. It depends on it. And he begins with a "generic" sequence of sequences.

Quote:

Again, you are asserting that we cannot have numbers involving an infinite number of decimal places. That would remove all irrational numbers and most rational numbers (all those except fractions whose denominators involve only powers of 2 and 5. Do you really want to assert that neither 1/3 nor 1/7 can be written as decimals?
No, I am not asserting such a thing. We can have numbers with an infinite numbers of decimal places. What we cannot claim is that we can compare the number of digits that we can put after the decimal point, with the number of digits that we can put before it. Both are infinite. And infinite is not a number. You cannot claim that either of them is bigger, and you cannot claim that they are the same. You can make NO SUCH CLAIMS. Comparissons not allowed. One infinite minus the other is not zero, it is an indetermination. But Cantor's method requires them to be exactly the same infinite, the matrix to be exactly square, or else there is no diagonal.

Quote:

That doesn't even make sense. The statement the "'infinites" are or are not "exacty the same number" makes no sense. "infinities" are NOT numbers in sense that you are using the word.
GOOD, we are finally talking the same. It doesn't make sense to claim that any of them is bigger than the other. This also means that it doesn't make sense to claim that it is the same number, nor that it isn't. Infinite minus infinite is not zero, as I explained above. It is an indetermination. Cantor's method is requiring infinite minus infinite to be zero. It is requiring the matrix to be square. That's why it is wrong. It assumes that the matrix is square, and that is an invalid assumption.
• March 12th 2013, 08:59 AM
zzephod
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Nylo
Thanks a lot for your response.

Excuse me, I may have missed the astonishing news of the final calculation of $\pi$. When did it happen? All I know is that a huge numbers of decimals are known.

A Turing machine which given $N$ returns the $N$-th decimal (or binary or ..) digit of $\pi$ is an exact and complete representation of $\pi$.

<handwaving>A constructible number is an equivalence class of Turing machines like that above and a equivalence class is determined by any member.</handwaving>

.
• March 12th 2013, 09:06 AM
zzephod
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Zeno
I don't necessarily support Nylo's infinite series argument. I was addressing the observation that Cantor's argument does indeed require the list of numbers to be square.

I hand you the following finite list of binary numbers. Namely the completed set of numbers that can be formed using only two binary digits:

$\begin{array}{cc} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1 \\ \end{array}$

Then I ask you to use Cantor's diagonalization argument to produce a new number that isn't on my list.

Can you do it? No, you clearly cannot. Cantor's diagonal method does not go down the list fast enough to cover all possible numbers on the list. If you use Cantor's method you'll create the binary number 10 and proclaim that it's not already on my list, but that would be false in this finite situation, because that number is indeed on my list, you're diagonalization method of finding a number not on the list was simply inefficient and cannot be used to accomplish the task.

Well, if you can't even do this for a finite list of numbers, then what right would you have to proclaim that you could do it for an infinite list?

You would always be behind no matter how far out you go. In fact the further out you go the further behind the actual list you get.

I offered a binary list of numbers because it's easy to see that this will always be the case. Plus the binary number system of enumerating numbers is as low as we can go. So this proves it for the best possible scenario. Even binary representations of numbers require rectangular lists that are at least twice as tall as they are wide in the simplest case of only two binary digits. Take it out to a four-digit binary number and you've got a list that only four columns wide, but 16 rows tall. So it get's worse with every digit you add to the list.

With decimal notion the situation is far worse. A single 2-digit list is 100 rows long!

00
01
02
03
04
05
.
.
.
95
96
97
98
99

How could you ever hope to use Cantor's diagonalization method to produce a new number that's not on this list?

And if you can't do it for a simple finite case, then why on earth should I believe that you should be able to do it for an infinitely long list?

Lists of numbers that contain every possible number (which is also a critical assumption) simply aren't square. And this includes decimal representations. Writing the numbers out as 0.1234... doesn't change a thing. The same geometry applies to completed lists of numbers.

Therefore Cantor's diagonalization "proof" is flawed.

It can't even be made to work in a finite case how can he possible claim to extend this to infinity?

He will always be behind the list, no matter how far he claims to have gone out.

Moreover, you can easily prove that this is indeed the case. Simply stop Cantor's process at any point and check out the "new" number you've created thus far. Is that number on the list "above" where you've been working? No, of course not because you only have numbers that you've created using the diagonal method. However, if you ask "Is this new number you've just created a legitimate rational number?" The answer necessarily has to be YES! Every truncated decimal number is indeed a rational number.

So at no point does Cantor ever create a "new" number that isn't already on the list of all rational numbers. When is he supposed to accomplish this feat? In his LAST infinite step? Does it even make any sense to speak about a LAST step in a supposedly infinite process?

This is the problem with Cantor. He's thinking in terms of "Completed Infinities" like as if he can actually complete this process, without realizing that no matter how far he carries this process out he will always be behind the list in terms of the vertical direction. In fact, with every new digit he creates he becomes exponentially further behind the list.

Add a 3rd digit to our list of decimal numbers and suddenly the length of that list becomes almost 1000 rows tall. And so on. With every digit you add the list of all possible numbers grows in depth exponentially.

So Cantor's proof is no proof at all. It's a totally bogus argument.

He would need to show that this can be made to make sense in a finite case first, and then extend that idea to infinity. But he clearly failed to show this because it is flat out impossible.

This diagonal method of creating a new number that isn't already on a complete list of numbers is a totally wrong idea to begin with.

It's a false argument that has no merit.

Complete lists of numerals are simply not square. Period. Yet Cantor's proof requires that they must be square.

Therefore Cantor's proof is flawed. It's not a proof at all.

I've been arguing this since back in high school. It just amazes me why mathematicians can see this.

It's so obvious to me.

If his conclusion is true that's just a lucky coincidence because his diagonalization method does not constitute a legitimate proof of his claim.

Is an $\aleph_0 \times \aleph_0$ array square or not?
• March 12th 2013, 10:19 AM
Nylo
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by zzephod
If you insist on a checking procedure try this:

I give you a real number $x$, you find its' position $n$ in the list (by hypothesis it must be on the list). Then the $n$ digit approximation to the Cantor number by construction is has all its digits equal to the first $n$ digits of the Cantor number and it differs from $x$ in its last place. Hence the Cantor number differs from $x$.

I don't know if you realise what you have just said. What you have said is that, no matter which real you choose, even if you don't give me its value but just an infinite mathematical expression that would calculate it, if I can find its position (even if I cannot tell you exactly which position is it but I can provide you with the way to calculate it), then it will NOT be Cantor's s0. So, if I provide you with a sequence which is built in such a way that I can tell you the position of ANY real you can think of, you will have to conclude that s0 does NOT exist for such a sequence, right? I say this because, at the end of this post, I am going to provide you with an example of SUCH a sequence. I wanted to leave the surprise for later, but I will post it now.

Quote:

Now you could argue that the very first step of the checking procedure can't be done, in which case we are in the realm of computable real numbers (which are enumerable) but Cantor's argument proves that there is no effective (that is computable) enumeration. Which in my opinion is an even neater result.
But Cantor is forgetting that there also exist Natural numbers that are NOT COMPUTABLE, in the sense that no matter how big and powerful you build a computer, I can tell you which natural number that computer is unable to represent, because of it being too big. That's what the concept of infinite means. And the fact that some natural numbers cannot be computed, does not mean that they don't exist, nor that they're not natural. The sequence that I am going to build for you later, DOES assign a natural number to ANY real that you can think of, even the non-computable ones. But some of them are of course going to be in non-computable positions (yet demonstrably natural and unique) of the list. I will just tell you with a simple mathematical expression how to calculate their position, and prove that the result is a natural number, although you will not be able to finish the calculation. In the same way that you can prove that $\pi$ is real although you will never finish its calculation.

Quote:

Finally, if I were moderating MHF I would close this thread as it will go nowhere. Experience on the web indicates that one will never convince those who have got it into their heads that Cantor's construction is wrong (within its' own terms of reference)
Thank you mods for not agreeing with this proposal, as it allows me to show a sequence that disprooves Cantor. It's what I believe to be a valid sequence of ALL THE REALS in the interval (0,1). In fact, I am going to provide you with an infinite number of valid sequences, you can then choose which one you like more.

THE SEQUENCE

This is the general expression of the formula that finds the position in the list for any real, i.e. the "n" in sn:

(Edited to show the correct expression, as I had made a mistake before)
Attachment 27495

Where int() means "the integer part of what comes within the brackets" and residue (,) the residue after dividing the first term by the second.

Notice that the result of that expression is incalculable, infinite, for some reals, in particular, for any $x$ which cannot be represented with a finite number of decimals in base 10. However, even if we cannot calculate it, we know a couple of things about that infinite result in particular:
1. It is natural, as it is made of the sum of other numbers which are also natural numbers, and the sum of any two natural numbers is another natural number.
2. It is unique for that x in particular, choose any different x, and you will get a demonstrably different result, even if this other result is incalculable as well.

These two things that we demonstrably know about the result of that expression, prove that the sequence is a valid bijection between the naturals and the reals in the interval (0,1). Give me any real, I will tell you its position in the list, and demonstrate that it is unique for that real only.

The above general expression, in mundane terms, means: given the decimal notation of any real number between 0 and 1, and I don't care if you need infinite decimals or not for its correct representation; the decimal notation of the natural number that I will associate to it is exactly the same, only reversing the order of the decimals and ignoring the initial "zero point". So, the first reals of my sequence are:
s1=0.1
s2=0.2
s3=0.3
...
s10=0.01
s11=0.11
s12=0.21
...
s100=0.001
...

But wait, I told you that I would provide you with infinite sequences that are valid as well. Could you guess them? Yes, in the above expression, just change the "10" for any other natural number bigger than 1. You will have other examples of also valid sequences with equally simple mundane meanings, just change the base that you are using for representing both the real and the natural and there you have it.

Now, zzephod, can you tell me which real cantor says that is not in my list? Thanks.

Best regards.
• March 12th 2013, 10:27 AM
Nylo
Re: Cantor's diagonal argument is wrong
Please ignore the general expression provided, it is wrong. I will show the right one in a few minutes.
Edit: the expression has been corrected and is now valid. Some incorrect thumbnails still exist because they cannot be removed once you upload them.
• March 12th 2013, 11:16 AM
Zeno
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by zzephod
Is an $\aleph_0 \times \aleph_0$ array square or not?

The very idea of $\aleph_0$ came from Georg Cantor. He's attempting to treat the concept of infinity as though it is a "completed" cardinal quantity, and that's a very bad thing to do. It leads to all manner of absurdites. Not the least of which is the idea that there can be "larger" and "smaller" infinities. That itself is an absurdity.

I think it's truly amazing that mathematicians value proof by contradiction as a valid tool of mathematics, yet they accept Cantor's multiple-sized infinities as not being absurd. Proving that one infinity is "larger" than another should itself be seen a reductio ad absurdum.

You ask whether $\aleph_0 \times \aleph_0$ is a square array or not?

But what does that have to do with the fact that I have just shown that it's the very nature of our numerical representations of number to necessarily be rectangular in shape if they are to be "completed lists" of all possible numbers expressed by that numerical system of notion?

I've even shown that this is true all the way down to the binary representation of numbers. You can't go any lower than that, and you still have the property of any "completed list" necessarily being rectangular in shape. Therefore no "completed list" of numbers can be square. Period.

Thus if you have a list of numbers that is $n \times n$ in shape concerning the counting of the digits that make up that list, then it cannot be a "completed list" of numbers because any completed list of numbers must necessarily be taller than it is wide as I have already demonstrated.

This is Cantor's fallacy.

He's not only assuming that infinity can be completed, but he's also assuming that if you could complete the list that would somehow force it to become square. That's absurd. In other words, Cantor's conjectured "proof" reduces to an absurdity.

Therefore Cantor's very idea reduces to absurdity.

And let's not forget that the very idea of $\aleph_0$ as being representative of a "completed cardinal quantity" was Cantor's idea.

You ask whether $\aleph_0 \times \aleph_0$ is a square array or not?

No. It's not "square". All it means is that you have decided to carry out your process endlessly in both directions. But have you actually "completed" this process?

No. And that's is Cantor's fallacy.

In fact, in the case of a list of rational numbers if to claim that you could "complete" the process, is the same as proclaiming that there must be a LAST rational number on your list. That itself is an absurdity.

The whole idea of "completed infinity" is a bogus idea. And that is what Georg Cantor is relying upon with his diagonalization proof.

Like I asked before, at what point does he actually create a number that's not on a list of rational numbers?

At any point in his process what he has created is precisely that. At that POINT he has a valid rational number.

So when does he ever create a number that's not a rational number?

• March 12th 2013, 12:32 PM
Nylo
Re: Cantor's diagonal argument is wrong
Quote:

Originally Posted by Zeno
The very idea of $\aleph_0$ came from Georg Cantor. He's attempting to treat the concept of infinity as though it is a "completed" cardinal quantity, and that's a very bad thing to do. It leads to all manner of absurdites. Not the least of which is the idea that there can be "larger" and "smaller" infinities. That itself is an absurdity.

I don't completely agree with you. Cantor's demonstration that the set of the subsets of the naturals is actually strictly bigger than the set of the naturals, is in my opinion absolutely flawless. And I admire him for having demonstrated such a thing. So one infinite is undoubtedly bigger than the other in that case. I just tend to disagree with the cardinality of reals being bigger than that of naturals. His demonstration for that particular case is wrong.
Show 40 post(s) from this thread on one page
Page 1 of 3 123 Last