Why Cantor's Diagonalization Proof is Flawed.

[Divine Insight]

Here is a Youtube video, under 10 minutes, of Cantor's diagonalization argument.

Ok, I've seen this proof countless times.

And like I say it's logically flawed because it requires the a completed list of numerals must be square, which they can' t be.

~~~~

First off you need to understand the numerals are NOT numbers. They are symbols that represent numbers. Numbers are actually ideas of quantity that represent how many individual things are in a collection.

So we aren't working with numbers here at all. We are working with numeral representations of numbers.

So look at the properties of our numeral representations of number:

Well, to begin with we have the numeral system based on ten.

This includes the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

How many different numbers can we list using a column that is a single digit wide?

Well, we can only list ten different numbers.

0
1
2
3
4
5
6
7
8
9

Notice that this is a completed list of all possible numbers. Notice also that this list is not square. This list is extremely rectangular. It is far taller than it is wide.

Let, apply Cantor's diagonal method to our complete list of numbers that are represented by only one numeral wide.

Let cross off the first number on our list which is zero and replace it with any arbitrary number from 1-9 (i.e. any number that is not zero)


[strike]0[/strike]
1
2
3
4
5
6
7
8
9

Ok we struck out zero and we'll arbitrary choose the numeral 7 to replace it.

Was the numeral 7 already on our previous list? Sure it was. We weren't able to get to it using a diagonal line because the list is far taller than it is wide.

Now you might say, "But who cares? We're going to take this out to infinity!"

But that doesn't help at all.

Why not?

Well what happens when we make the next step? We need to make the list 2 digits wide now.

What happens?

Here is a 2-digit list of all possible numbers represented by 2 numerals.

00
01
02
03
04
05
06
07
08
09
11
12
13
14
15
.
.
.

95
96
97
98
99

What happened? Well, our completed list of possible numerals that is two digits wide has incrusted in vertical height exponentially. This list is now 100 rows tall and only 2 column wide.

Now let's cross off the first two digits of our list and replace them with arbitrary numerals.

[strike]0[/strike]0
0[strike]1[/strike]

Ok, for the first zero being stuck off the list, I'll chose to arbitrarily replace that with a 5. For the second digit being struck off the list I'll replace that arbitrarily with a 7.

My new number is 57.

Is 57 already on my completed list? Yes. It's just further down the list where I couldn't possibly reach it by drawing a diagonal line.

Now you might say, "But who cares? We're going to take this out to infinity!"

But duh? We can already see that in a finite situation we are far behind where we need to be, and with every digit we cross off we get exponentially further behind the list.

Taking this process out to infinity would be a total disaster.

You could never claim to have "completed" this process because you can't move down the list fast enough using a diagonal line that crosses off each digit diagonally.

The very nature of our system of numerical representation forbids this. You can't complete this process in a finite situation, and it gets exponentially worse with every digit you add to the width, then you could never claim to have completed this process by claiming to have taken it out to infinity.

"Completed Lists" of numerical representations of numbers are NOT SQUARE.

Yet Cantor claims to be creating a "Completed List" here. It's a bogus proof that fails. Cantor didn't stop to realize that our numerical representations of number do not loan themselves to nice neat square competed lists. And that was the flaw in his logic.

By the way you can't even do this using binary representations of numbers.

In Binary Representation

A completed list of binary numbers 2 digits wide:

00
01
10
11

It's not square. It's twice as tall as it is wide.

Add another digit it gets worse:

000
001
010
011
100
101
110
111

There is no way that a completed list of numbers can be represented numerically in square lists.

Yet Cantor's diagonal argument demands that the list must be square. And he demands that he has created a COMPLETED list.

That's impossible.

Cantor's denationalization proof is bogus.

It should be removed from all math text books and tossed out as being totally logically flawed.

It's a false proof.

Cantor was totally ignorant of how numerical representations of numbers work. He cannot assume that a completed numerical list can be square. Yet his diagonalization proof totally depends on this to be the case.

Otherwise, how can he claim to have a completed list?

If he's standing there holding a SQUARE list of numerals how can he claim that he has a completed list?

Yet at what point does his list ever deviate from being square?

It never deviates from being square. It can't because he's using a diagonal line to create it. That forces his list to always be square.

Georg Cantor was an idiot.

He didn't even understand how numerical representations of numbers work.

His so-called "proof" doesn't prove anything. It's totally bogus.

He can't claim to have a "completed list" by the way he is generating his list. Claiming to take this out to infinity doesn't help. With every new digit he creates he falls exponentially behind where he would need to be to create a "Completed List".

Yet that's what he claims to have: A Completed List.

It's a bogus proof, and I'm shocked that no mathematicians have yet recognize this extremely obvious truth.

They keep publishing this proof and teaching it like as is it has merit when in fact it's totally bogus.

[Divine Insight]

[Replying to post 73 by Friedrich]

This argument suffers from essentially the same problem as olavisjo's. All the numbers in your list of binary numbers have finitely many digits and so are rational. The list does not contain any irrational numbers.

Cantor's Diagonalization proof is no proof of anything if Cantor can't show that a completed list of numerals that represent the numbers could be a square list.

I've already shown in the OP that this isn't even possible using binary:

In Binary Representation

A completed list of binary numbers 2 digits wide:

00
01
10
11

It's not square. It's twice as tall as it is wide.

It's far worse in decimal numerical notation which is what Cantor was using.

But I've shown that it can't even be made to work in Binary numerical notions.

So, Micatala, unless you can show me a numerical system that can represent all numbers in a square list, then you haven't justified Cantor's Diagonalization argument.

The flaw is simple. Cantor was assuming a completed numerical list that could be square, when the numerals he was using (i.e. base 10) isn't anywhere near square.

I've even gone as far to demonstrate that this can't even be done using binary numerical notation.

So can you provide a numerical notion that can represent a completed list of numbers that is a square list?

If you can I would love to see it because I can't imagine what it would be. If binary notional can't even work, then what could?

There is no such thing as a unitary numerical system. You need to have at least two states (i.e. Binary), and that already requires a rectangular list. So how are you ever going to produce a square list of all numbers?

And without a complete square list, then any Diagonalization argument fails immediately.

[micatala]

[Replying to post 73 by Friedrich]

This argument suffers from essentially the same problem as olavisjo's. All the numbers in your list of binary numbers have finitely many digits and so are rational. The list does not contain any irrational numbers.

Cantor's Diagonalization proof is no proof of anything if Cantor can't show that a completed list of numerals that represent the numbers could be a square list.

Alright. What is your precise definition of a 'completed list' of numbers.

In Binary Representation

A completed list of binary numbers 2 digits wide:

00
01
10
11

It's not square. It's twice as tall as it is wide.

This is a list of 4 numbers. What makes it complete? That you used all possible two-digit numbers? You may have done this, but I don't recall you ever precisely defined what a 'complete list' is.

So, Micatala, unless you can show me a numerical system that can represent all numbers in a square list, then you haven't justified Cantor's Diagonalization argument.

You are forming your own argument. Since you are not even addressing the main points of Cantor's argument, this does not debunk his argument.

The flaw is simple. Cantor was assuming a completed numerical list that could be square, when the numerals he was using (i.e. base 10) isn't anywhere near square.

Cantor is doing a proof by contradiction to prove a given statement, call is P. The form of the argument is.

1) Assume P is false.
2) On the basis of this assumption, derive a contradiction. In other words, prove there is a statement A which is both true and not true.
3) Since no statement can be true and not true. This means the assumption that P was false must itself be false. Therefore, P is true.

The statement P in Cantor's case is "Assume there is a function f from the natural numbers N to the real numbers R so that every real number y there is a natural number with f(n)=y. (We call f surjective or onto). Since N can be 'listed,' he does this by creating the list which you seem to be referring to as a square list of numbers.

But, as has been pointed out, any real number (say between 0 and 1), whether it is rational or not, can be expressed as a decimal number with infinitely many digits.

1/2 for example is 0.50000 . . . .

1/3 is 0.3333333. . . .

Root 2 minus 1 begins 0.41421 . . . and goes on forever, never repeating any finite pattern.


The list that Cantor is assuming exists for purposes of contradiction does not in fact exist, and he is not saying it DOES exist. He is proving it does NOT exist by contradiction.

If the list did exist (as assumed), then it is infinite from the top down AND if you use the infinite digit form of for real numbers, it is infinite left to right. To say this is or is not 'square' is both irrelevant and incorrect. You might as well say it is square and non-square rectangular.

For example, consider the list.

0.2000 . . .
0.4000 . . .
0.6000 . . .

etc. The digits of each number can be indexed by N by place value. 10ths go with 1, 10oths with 2, 1000ths with 3, etc. The numbers are indexed by the even integers 2N. Since (and I am trying to follow how you are thinking of this as best as I can) only half of the natural numbers are even, the rectangle is "twice as wide as it is long."

On the other hand, the function f(n)=2n is a bijective (One to one correspondence) from the even integers 2N TO N. So, the length and width of the 'rectangle' can also be considered square.



Any such infinite list of real numbers will have this feature, essentially because infinite sets always have the property that there can be a one-to-one correspondence from the whole set to a proper subset. You can make it any 'shape' you wish. What 'shape' you consider it does not change the selection of the diagonal elements.

[Divine Insight]

In Binary Representation

A completed list of binary numbers 2 digits wide:

00
01
10
11

It's not square. It's twice as tall as it is wide.

This is a list of 4 numbers. What makes it complete? That you used all possible two-digit numbers? You may have done this, but I don't recall you ever precisely defined what a 'complete list' is.

It's a "complete list" in that it has listed every possible number using this numerical system of notation.

And this demonstrates that a 'complete list' is necessarily rectangular and not square. In fact, it gets more rectangular with every numerical digit added. Adding just one more numeral produces a 'completed list' that is 3 digits wide and 16 rows tall. The situation is only going to get much worse the further out the list we go.

In fact, you can see this with only using a list of 1 digit in binary

O
1

See. We already have 1 column and 2 rows in order to list all possible numbers, that's already a rectangular list. So Binary requires a rectangular list in the most elementary situation. And it's only going to become more rectangular with every digit added. Therefore we could never use this list for any kind of "diagonal proof" that certain numbers aren't on the list. The only way we could do that is if our list was perfectly square in numerical notation. But no such numerical notation is even possible.

So these lists cannot be used the way that Cantor is using them.

So, Micatala, unless you can show me a numerical system that can represent all numbers in a square list, then you haven't justified Cantor's Diagonalization argument.

You are forming your own argument. Since you are not even addressing the main points of Cantor's argument, this does not debunk his argument.

I'm only talking about his Diagonalization Proof. If he has other proofs so be it. That would be an entirely different thing.

The flaw is simple. Cantor was assuming a completed numerical list that could be square, when the numerals he was using (i.e. base 10) isn't anywhere near square.

Cantor is doing a proof by contradiction to prove a given statement, call is P. The form of the argument is.

1) Assume P is false.
2) On the basis of this assumption, derive a contradiction. In other words, prove there is a statement A which is both true and not true.
3) Since no statement can be true and not true. This means the assumption that P was false must itself be false. Therefore, P is true.

The statement P in Cantor's case is "Assume there is a function f from the natural numbers N to the real numbers R so that every real number y there is a natural number with f(n)=y. (We call f surjective or onto). Since N can be 'listed,' he does this by creating the list which you seem to be referring to as a square list of numbers.

But, as has been pointed out, any real number (say between 0 and 1), whether it is rational or not, can be expressed as a decimal number with infinitely many digits.

1/2 for example is 0.50000 . . . .

1/3 is 0.3333333. . . .

Root 2 minus 1 begins 0.41421 . . . and goes on forever, never repeating any finite pattern.


The list that Cantor is assuming exists for purposes of contradiction does not in fact exist, and he is not saying it DOES exist. He is proving it does NOT exist by contradiction.

But he is not proving that it doesn't exist by contradiction because his contradiction assumes that the list is square (i.e. that by the time you get to the end of his diagonal line you have covered every possible number on this list up to that point. But that's a false assumption because that assumption requires that a complete list of such numbers would indeed be square. In other words, that assumption assumes that the list grows to the left at the same rate that it grows downward. But that's not how numerical representations work. So he has made an incorrect assumption from the get go.

If the list did exist (as assumed), then it is infinite from the top down AND if you use the infinite digit form of for real numbers, it is infinite left to right. To say this is or is not 'square' is both irrelevant and incorrect. You might as well say it is square and non-square rectangular.

For example, consider the list.

0.2000 . . .
0.4000 . . .
0.6000 . . .

etc. The digits of each number can be indexed by N by place value. 10ths go with 1, 10oths with 2, 1000ths with 3, etc. The numbers are indexed by the even integers 2N. Since (and I am trying to follow how you are thinking of this as best as I can) only half of the natural numbers are even, the rectangle is "twice as wide as it is long."

On the other hand, the function f(n)=2n is a bijective (One to one correspondence) from the even integers 2N TO N. So, the length and width of the 'rectangle' can also be considered square.

But for Cantor's bijection to work, every possible number that can be listed must have already been on the list prior to reaching the bottom of his diagonal line AT THAT POINT. But he's already necessarily far behind of what any actual list would include.

So he can't say that he has ruled out any numbers.

Any such infinite list of real numbers will have this feature, essentially because infinite sets always have the property that there can be a one-to-one correspondence from the whole set to a proper subset. You can make it any 'shape' you wish. What 'shape' you consider it does not change the selection of the diagonal elements.

Sure it does. If you are drawing a diagonal line down a rectangular list that is growing in rows far faster than the rate at which your diagonal line is moving down the rows, then you can't say anything about what's on the list at any point on your diagonal line. Your diagonal line hasn't gone down the rectangular list far enough, and never will.

I mean, think about it, this already fails in a finite situation. How in the world would you ever hope to improve the situation by pretending that you could take this out to infinity?

The further you go out the further behind you get.

Try re-reading my OP again.

Look at the situation with decimal numerals. By the time your diagonal line has only gone down ONE row, you are already 98 rows BEHIND THE LIST.

To go down another row you need to add a third digit, and now you are something like 997 rows behind. The next digital will take you to being something like 9996 rows behind.

The further out you take the diagonal line the further behind you get. Trying to take this out to infinity would be futile. With every additional digit you become exponentially further behind the actual potential of the list.

To use your diagonal line at that point to make any claims about what might or might not be on this list is utterly absurd at this point. The diagonal line can never "reach" down far enough on the list to be used to say what may or may not be on the list.

So if Cantor is using decimal notation as his evidence for (or against) a one-to-one bijection between the natural numbers and the reals, then his argument fails miserably. He's not making any meaningful one-to-one correspondence at all.

[micatala]

In Binary Representation

A completed list of binary numbers 2 digits wide:

00
01
10
11

It's not square. It's twice as tall as it is wide.

This is a list of 4 numbers. What makes it complete? That you used all possible two-digit numbers? You may have done this, but I don't recall you ever precisely defined what a 'complete list' is.

It's a "complete list" in that it has listed every possible number using this numerical system of notation.

Very good. Thanks for the clarifiication.

And this demonstrates that a 'complete list' is necessarily rectangular and not square.

This does not follow. As noted, at least for decimial numbers which are the relevant type of numbers in Cantor's proof, the representation of the number does not depend on the number and can incorporate any number of zeroes. Often, you can add 9's instead at least in base 10.

In fact, it gets more rectangular with every numerical digit added. Adding just one more numeral produces a 'completed list' that is 3 digits wide and 16 rows tall. The situation is only going to get much worse the further out the list we go.

In fact, you can see this with only using a list of 1 digit in binary

O
1

I see what you are saying, but this is irrelevant to Cantor's proof since these are not decimal numbers. Besides not having an infinite decimal expansion (unless your write, for example, 1 as 0.99999 . . . .), integers are also separated in that there is a number S (we can use 0.49) so that for any two integers A and B with A<B, A+S < B-S.

There is not single S which satisifies this property for either real or rational numbers.

See. We already have 1 column and 2 rows in order to list all possible numbers, that's already a rectangular list. So Binary requires a rectangular list in the most elementary situation. And it's only going to become more rectangular with every digit added. Therefore we could never use this list for any kind of "diagonal proof" that certain numbers aren't on the list. The only way we could do that is if our list was perfectly square in numerical notation. But no such numerical notation is even possible.

So these lists cannot be used the way that Cantor is using them.

Again, not relevant since integers do not share all the same characteristics as real (or rational) numbers.

So, Micatala, unless you can show me a numerical system that can represent all numbers in a square list, then you haven't justified Cantor's Diagonalization argument.

You are forming your own argument. Since you are not even addressing the main points of Cantor's argument, this does not debunk his argument.

I'm only talking about his Diagonalization Proof. If he has other proofs so be it. That would be an entirely different thing.

The flaw is simple. Cantor was assuming a completed numerical list that could be square, when the numerals he was using (i.e. base 10) isn't anywhere near square.

Cantor is doing a proof by contradiction to prove a given statement, call is P. The form of the argument is.

1) Assume P is false.
2) On the basis of this assumption, derive a contradiction. In other words, prove there is a statement A which is both true and not true.
3) Since no statement can be true and not true. This means the assumption that P was false must itself be false. Therefore, P is true.

The statement P in Cantor's case is "Assume there is a function f from the natural numbers N to the real numbers R so that every real number y there is a natural number with f(n)=y. (We call f surjective or onto). Since N can be 'listed,' he does this by creating the list which you seem to be referring to as a square list of numbers.

But, as has been pointed out, any real number (say between 0 and 1), whether it is rational or not, can be expressed as a decimal number with infinitely many digits.

1/2 for example is 0.50000 . . . .

1/3 is 0.3333333. . . .

Root 2 minus 1 begins 0.41421 . . . and goes on forever, never repeating any finite pattern.


The list that Cantor is assuming exists for purposes of contradiction does not in fact exist, and he is not saying it DOES exist. He is proving it does NOT exist by contradiction.

But he is not proving that it doesn't exist by contradiction because his contradiction assumes that the list is square (i.e. that by the time you get to the end of his diagonal line you have covered every possible number on this list up to that point.

No, as I explained, it really makes no sense to even consider an infinite list of numbers each with infinitely many digits 'square.' You could in some sense say that such lists can be any shape at all. Nowhere does Cantor state this assumption. Nowhere does he even implicitly use such an assumption.

But that's a false assumption because that assumption requires that a complete list of such numbers would indeed be square. In other words, that assumption assumes that the list grows to the left at the same rate that it grows downward. But that's not how numerical representations work. So he has made an incorrect assumption from the get go.

If what you are saying were actually true, you would have found a much easier way to prove that the real numbers are uncountable because you would have shown that such an assumed list does not exist. You would have reached a contradiction in a different way. But again, your examples are integers, not real numbers between 0 and 1 with infinitely many digits.

If the list did exist (as assumed), then it is infinite from the top down AND if you use the infinite digit form of for real numbers, it is infinite left to right. To say this is or is not 'square' is both irrelevant and incorrect. You might as well say it is square and non-square rectangular.

For example, consider the list.

0.2000 . . .
0.4000 . . .
0.6000 . . .

etc. The digits of each number can be indexed by N by place value. 10ths go with 1, 10oths with 2, 1000ths with 3, etc. The numbers are indexed by the even integers 2N. Since (and I am trying to follow how you are thinking of this as best as I can) only half of the natural numbers are even, the rectangle is "twice as wide as it is long."

On the other hand, the function f(n)=2n is a bijective (One to one correspondence) from the even integers 2N TO N. So, the length and width of the 'rectangle' can also be considered square.

But for Cantor's bijection to work, every possible number that can be listed must have already been on the list prior to reaching the bottom of his diagonal line AT THAT POINT. But he's already necessarily far behind of what any actual list would include.

So he can't say that he has ruled out any numbers.

Cantor is assuming the bijection works for purposes of contradiction. Also, there is no 'bottom of the diagonal' in the argument since the diagonal is infinite. What happens at a particular spot N on the diagonal is simply that a number can be selected which is different than the Nth number on the list at the Nth spot in that number.

It seems to me what you are arguing is analogous to the following.

We have a suspect for a crime A committed in Gotham City. To prove A is guilty, we might at first assume A is not guilty. This is an assumption for purposes of contradiction. Let's say that based on this assumption we can prove the crime was committed in a large apartment building in the city. We then go on to show that no such crime was committed in any such large apartment building (whether they had square windows or not). This is a contradiction since we have proven the crime was committed and also was not committed in a large apartment building in the city. Therefore, the assumption that A is not guilty must have been false.

You are objecting to this line of reasoning on the basis of the buildings being taller than they are wide.

Any such infinite list of real numbers will have this feature, essentially because infinite sets always have the property that there can be a one-to-one correspondence from the whole set to a proper subset. You can make it any 'shape' you wish. What 'shape' you consider it does not change the selection of the diagonal elements.

Sure it does. If you are drawing a diagonal line down a rectangular list that is growing in rows far faster than the rate at which your diagonal line is moving down the rows, then you can't say anything about what's on the list at any point on your diagonal line. Your diagonal line hasn't gone down the rectangular list far enough, and never will.

Once again, your assumption about the list having to be taller than it is wide is not valid. Just add zeroes as necessary to the representation of the numbers. Why do you seemingly refuse to consider this?

[micatala]

Really, DI, you seem to be objecting to Cantor's diagonalization argument not working on finite lists of numbers with finitely many digits. You are right in this sense. The argument does not work on a finite list of INTEGERs. It would not even work on an infinite list of integers, mainly for the reason that integers ARE countable not uncountable.

[Divine Insight]

Really, DI, you seem to be objecting to Cantor's diagonalization argument not working on finite lists of numbers with finitely many digits. You are right in this sense. The argument does not work on a finite list of INTEGERs. It would not even work on an infinite list of integers, mainly for the reason that integers ARE countable not uncountable.

Well don't let the decimal point fool you into thinking anything would change just because you are working to the right of a decimal point. The rectangular property of this numerical style of notation still holds.

So if this is Cantor's argument for why the reals cannot be placed in a one-to-one correspondence with the natural numbers, then his arguments fails miserably.

All he has managed to do here is create a false quantitative idea of larger and smaller cardinal infinities.

There simply is no need for any ideas of infinity greater than endlessness. Such ideas are totally bogus.

[micatala]

Really, DI, you seem to be objecting to Cantor's diagonalization argument not working on finite lists of numbers with finitely many digits. You are right in this sense. The argument does not work on a finite list of INTEGERs. It would not even work on an infinite list of integers, mainly for the reason that integers ARE countable not uncountable.

Well don't let the decimal point fool you into thinking anything would change just because you are working to the right of a decimal point. The rectangular property of this numerical style of notation still holds.

No, it does not. With an integer, say 27, adding zeroes after the 7 changes the value of the number represented. I suppose if you wanted to, you could add zeroes before the 2 and write all integer numerals as infinitely many zeroes followed by the usual representation.

With decimal numbers, you can add infinitely many zeroes (or any finite number of zeroes) after the last nonzero digit and not change the value of the number. That is why your 'square' criterion is irrelevant.

All he has managed to do here is create a false quantitative idea of larger and smaller cardinal infinities.

Just remove the 'false' from this statement and you have it right. Cantor's proof does establish that the cardinality of the set of natural numbers is different than the cardinality of the set of real numbers. Cardinality for infinite and finite sets can be defined using the concept of bijective functions (one-to-one correspondences).

The set of numbers represented on the side of a standard die is the same as the cardinality of the set of sides of a regular hexagon because they can be put into one to one correspondence.

The function f(n)=2n establishes that the natural numbers and the even natural numbers are of the same cardinality.

The fact that the natural numbers cannot be put into one-to-one correspondences with the real numbers between 0 and 1 is established via Cantor's proof. To prove the 'cannot,' we assume, for purposes of contradiction that we can, which gets us to the list which you keep insisting has to be square but which is really just an infinite list of decimal representations of infinitely many digits each. 'Squareness,' however defined is not mentioned in the proof, nor is it relevant.

There simply is no need for any ideas of infinity greater than endlessness. Such ideas are totally bogus.

Define "need."

I think I asked this (or something like this) before.

Do you dispute the the decimal number 0.333 . . . infinitely repeating threes is a valid representation for the rational number 1/3?

[mgb]

The argument does not work on a finite list of INTEGERs. It would not even work on an infinite list of integers, mainly for the reason that integers ARE countable not uncountable.

But it would work on an infinite list of infinite integers; integers with an infinity of digits...

[mgb]

The argument does not work on a finite list of INTEGERs. It would not even work on an infinite list of integers, mainly for the reason that integers ARE countable not uncountable.

But it would work on an infinite list of infinite integers; integers with an infinity of digits...

[micatala]

[Replying to mgb]

Can you more precisely define what you mean.

Do you mean a countably infinite set/list of integers?