- #1
Leucippus
- 39
- 1
I have a problem with Cantor's Diagonalization proof of the uncountability of the real numbers. His proof appears to be grossly flawed to me. I don't understand how it proves anything.
Please take a moment to see what I'm talking about.
Here is a totally abstract pictorial that attempts to show how Cantor's proof works. However, this pictorial is grossly flawed in two ways. First off, it's perfectly square, and secondly, it abstractly uses letters in place of numerals totally missing the point of what this proof is based upon.
In the above picture we're supposed to assume that we've gone down a nice neat square list of numbers and came up with a brand new number that clearly cannot be on the list.
But is that truly the case? I claim that it can't be the case. It's impossible. Why?
Well to realize what the problem is we must first recognize that this list is entirely based upon numerals and numbering systems. It is not based on abstract letters as show in the previous graphic. So let's get a more suitable graphic like the one below so we can illustrate why this can't work.
Ok now we'll be able to see why this can't work. What he's doing here is listing numerals (please understand that he is listing numerals not numbers). Numerals are a system that we use to write out numbers. He is using a graphic system of writing out numerals and then crossing them off diagonally to obtain a brand new number that is supposedly not already on the list.
And if numerical lists were perfectly square he would indeed have a valid proof. But lists of numerals are not square. They are extremely rectangular in the vertical direction. We have no such thing as a square numerical system in terms of being able to write it out graphically as a square. The decimal notational system is extremely rectangular.
What do I mean by this?
Well, take all possible 2-digit decimal numbers (assume non-negative numbers) and list them out. What do you get? You get a very tall narrow rectangular list of numbers like so:
http://users.csonline.net/designer/me/dec_digit.gif
This list is not even remotely close to being square. Add another digit to make it a list a mere 3 digits wide, and it will become almost 1000 rows deep. With every additional digit you add, the list innately becomes longer by powers of 10.
Lists of numbers using the decimal numerical system are far from being square lists.
What does this have to do with Cantor's diagonalization proof, you may ask. Well it has everything to do with it. Cantor is claiming to take a process out to infinity. But I claim that his process can't even be made to work in the simplest finite case.
I would like to use the binary number system to try to illustrate this point. It's far more manageable than trying to do this in base 10. Even the Binary numeralic system isn't square, but it's far more manageable so please bear with me for a few quick examples.
Let me start with a simple 2-digit binary list. This will be four rows long:
Please keep in mind that these are binary numbers now.
http://users.csonline.net/designer/me/2_digit.gif
So what do we do? Well, we go down the list diagonally replacing every digit we cross out with some other arbitrary digit that is not the same digit. In binary this is extremely simple because we are forced to swap 1's for 0's and vice versa.
So we go down this list and changing the first 0 to a 1 and the second 1 to a zero and come up with our new number 10. Then we ask. Is that number already on our list. And yes of course it is. In fact it's the very next number on the list. We just weren't able to reach it because a diagonal line doesn't go down the list fast enough to cover all the rows.
So the new number that we created was already on our 2-digit wide list.
Let's try it now on a binary list 3-digits wide:
http://users.csonline.net/designer/me/3_digit.gif
Well this time it's easy. When we draw our digaonal line we hit three 0's and create the new binary number 111 which happens to be the last number on the list. But it's on the list!
It fact, any number we create this way must always be on the list. It's the very nature of the numerical system. And this is precisely due to the fact that these lists are far taller than they are wide.
Let's to it one last time for a 4-digit binary list. If the list if 4-digits wide it's going to also be 16 rows tall.
http://users.csonline.net/designer/me/4_digit.gif
Yep, sure enough, when we create our new number using Cantor's diagonalization method we come up with another number that is already on our list. This must necessarily always be the case simply due to the very nature of these numerical systems of notation.
Now, you might be tempted to say, "But wait a minute, Cantor is taking this process out to infinity!"
So?
If a diagonal line is already this far behind in a mere finite situation taking it out to infinity is only going to make matters that much worse. Look the binary examples I gave above. When the list was 2-digits wide the diagonal line went half way down the list. When the list was 3-digits wide the diagonal line went only about a third of the way down the list. When the list was 4-digits wide the diagonal line only when down the list about a quarter of the way. The wider the lists become the worse the situation gets.
Using decimal notation (which is what Cantor actually used) the situation is far worse.
If he can't even make it to the bottom of a finite list how could he ever hope to cross off every possible number on a list infinity many digits wide?
He's claiming to have created a brand new number that cannot be on the list.
I say baloney. He could never get to the bottom of the list. How can he claim that the new number that he has constructed "cannot be on the list" when he can't possibly be making enough downward progress in the vertical direction to have ever gotten to the bottom of his list?
As far as I'm concern this so-called "proof" doesn't prove anything other than Cantor must have been mistakenly assuming that it makes sense to assume that lists of numerals could be made square (that is a false assumption).
~~~~~
Please note that this does not mean that the results of Cantor's proof are false. It simply means that his proof does not prove the assertion that he's claiming.
~~~~~
Now if I'm in error please advise. But I honestly don't see how Cantor's diagonalization proof proves anything when it's based on a numerical representation of numbers that simply cannot be made to be square which his "proof" apparently requires.
At no point can he legitimately claim to have reached the "bottom" of his list. And claiming to take this out to infinity doesn't help. Because with every digit wider the list just gets that much taller by an increasing magnitude. He could never hope to reach the bottom of his infinite list to make the proclamation that he has created a new number that's not on the list. His diagonal line simply can't have a steep enough slope to accomplish this task.
I seriously don't see how that could be made to work.
See in these pictures in math books (like the one shown below) they make it look like he can easily reach the bottom of the list. He's going down at what appear to be a nice 45 degree angle on a seemingly square list. But that is a mistaken illusion in these graphic examples. Real numerical lists don't behave this way.
So can anyone explain to me how Cantor's Diagonalization Method can be accomplished if taken out to infinity when it clearly can't even work in simple finite examples?
Seriously, I'd appreciate an explanation.
If you can explain to me why his proof makes sense and why my objections are flawed, I would truly be very grateful because I honestly cannot see how his proof makes any sense at all.
Thank you for taking the time to read my concerns.
Please take a moment to see what I'm talking about.
Here is a totally abstract pictorial that attempts to show how Cantor's proof works. However, this pictorial is grossly flawed in two ways. First off, it's perfectly square, and secondly, it abstractly uses letters in place of numerals totally missing the point of what this proof is based upon.
In the above picture we're supposed to assume that we've gone down a nice neat square list of numbers and came up with a brand new number that clearly cannot be on the list.
But is that truly the case? I claim that it can't be the case. It's impossible. Why?
Well to realize what the problem is we must first recognize that this list is entirely based upon numerals and numbering systems. It is not based on abstract letters as show in the previous graphic. So let's get a more suitable graphic like the one below so we can illustrate why this can't work.
Ok now we'll be able to see why this can't work. What he's doing here is listing numerals (please understand that he is listing numerals not numbers). Numerals are a system that we use to write out numbers. He is using a graphic system of writing out numerals and then crossing them off diagonally to obtain a brand new number that is supposedly not already on the list.
And if numerical lists were perfectly square he would indeed have a valid proof. But lists of numerals are not square. They are extremely rectangular in the vertical direction. We have no such thing as a square numerical system in terms of being able to write it out graphically as a square. The decimal notational system is extremely rectangular.
What do I mean by this?
Well, take all possible 2-digit decimal numbers (assume non-negative numbers) and list them out. What do you get? You get a very tall narrow rectangular list of numbers like so:
http://users.csonline.net/designer/me/dec_digit.gif
This list is not even remotely close to being square. Add another digit to make it a list a mere 3 digits wide, and it will become almost 1000 rows deep. With every additional digit you add, the list innately becomes longer by powers of 10.
Lists of numbers using the decimal numerical system are far from being square lists.
What does this have to do with Cantor's diagonalization proof, you may ask. Well it has everything to do with it. Cantor is claiming to take a process out to infinity. But I claim that his process can't even be made to work in the simplest finite case.
I would like to use the binary number system to try to illustrate this point. It's far more manageable than trying to do this in base 10. Even the Binary numeralic system isn't square, but it's far more manageable so please bear with me for a few quick examples.
Let me start with a simple 2-digit binary list. This will be four rows long:
Please keep in mind that these are binary numbers now.
http://users.csonline.net/designer/me/2_digit.gif
So what do we do? Well, we go down the list diagonally replacing every digit we cross out with some other arbitrary digit that is not the same digit. In binary this is extremely simple because we are forced to swap 1's for 0's and vice versa.
So we go down this list and changing the first 0 to a 1 and the second 1 to a zero and come up with our new number 10. Then we ask. Is that number already on our list. And yes of course it is. In fact it's the very next number on the list. We just weren't able to reach it because a diagonal line doesn't go down the list fast enough to cover all the rows.
So the new number that we created was already on our 2-digit wide list.
Let's try it now on a binary list 3-digits wide:
http://users.csonline.net/designer/me/3_digit.gif
Well this time it's easy. When we draw our digaonal line we hit three 0's and create the new binary number 111 which happens to be the last number on the list. But it's on the list!
It fact, any number we create this way must always be on the list. It's the very nature of the numerical system. And this is precisely due to the fact that these lists are far taller than they are wide.
Let's to it one last time for a 4-digit binary list. If the list if 4-digits wide it's going to also be 16 rows tall.
http://users.csonline.net/designer/me/4_digit.gif
Yep, sure enough, when we create our new number using Cantor's diagonalization method we come up with another number that is already on our list. This must necessarily always be the case simply due to the very nature of these numerical systems of notation.
Now, you might be tempted to say, "But wait a minute, Cantor is taking this process out to infinity!"
So?
If a diagonal line is already this far behind in a mere finite situation taking it out to infinity is only going to make matters that much worse. Look the binary examples I gave above. When the list was 2-digits wide the diagonal line went half way down the list. When the list was 3-digits wide the diagonal line went only about a third of the way down the list. When the list was 4-digits wide the diagonal line only when down the list about a quarter of the way. The wider the lists become the worse the situation gets.
Using decimal notation (which is what Cantor actually used) the situation is far worse.
If he can't even make it to the bottom of a finite list how could he ever hope to cross off every possible number on a list infinity many digits wide?
He's claiming to have created a brand new number that cannot be on the list.
I say baloney. He could never get to the bottom of the list. How can he claim that the new number that he has constructed "cannot be on the list" when he can't possibly be making enough downward progress in the vertical direction to have ever gotten to the bottom of his list?
As far as I'm concern this so-called "proof" doesn't prove anything other than Cantor must have been mistakenly assuming that it makes sense to assume that lists of numerals could be made square (that is a false assumption).
~~~~~
Please note that this does not mean that the results of Cantor's proof are false. It simply means that his proof does not prove the assertion that he's claiming.
~~~~~
Now if I'm in error please advise. But I honestly don't see how Cantor's diagonalization proof proves anything when it's based on a numerical representation of numbers that simply cannot be made to be square which his "proof" apparently requires.
At no point can he legitimately claim to have reached the "bottom" of his list. And claiming to take this out to infinity doesn't help. Because with every digit wider the list just gets that much taller by an increasing magnitude. He could never hope to reach the bottom of his infinite list to make the proclamation that he has created a new number that's not on the list. His diagonal line simply can't have a steep enough slope to accomplish this task.
I seriously don't see how that could be made to work.
See in these pictures in math books (like the one shown below) they make it look like he can easily reach the bottom of the list. He's going down at what appear to be a nice 45 degree angle on a seemingly square list. But that is a mistaken illusion in these graphic examples. Real numerical lists don't behave this way.
So can anyone explain to me how Cantor's Diagonalization Method can be accomplished if taken out to infinity when it clearly can't even work in simple finite examples?
Seriously, I'd appreciate an explanation.
If you can explain to me why his proof makes sense and why my objections are flawed, I would truly be very grateful because I honestly cannot see how his proof makes any sense at all.
Thank you for taking the time to read my concerns.
Last edited by a moderator: