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.

[benchwarmer]

[Replying to post 1 by Divine Insight]

Perhaps I don't fully understand the issue, but when I looked up this proof, I understand it differently. I see it as saying that you can't count all possible values if you have X sets of digits each with X digits.

Using binary digits, we have the following:

-> Using 1 set of 1 digit

S1: 0

If we flip the 0 to a 1, we can see that 1 isn't included in the only set.

-> Using 2 sets of 2 digits

S1: 0, 0
S2: 0, 1

If we flip the diagonal S1(0) and S2(1) we get 1,0. This value is not included in either set.

-> Using 3 sets of 3 digits

S1: 0,0,0
S2: 1,1,1
S3: 0,1,0

Flip the diagonal, we get 1,0,1 which is not included in any set.

Etc.

This shows that you cannot include all possible arrangements of the digits using the SAME number of digits as the number of sets. i.e. X digits within X sets, regardless of the value of X. This means we can create an uncountable set if X continues to infinity because we can always add one digit to the length of the sets and adding one more set doesn't get us a complete set. In fact, it gets worse and worse as you've shown.

The original proof was not about unbalanced sets as you have shown with your finite sets.

Using your finite sets, if we add one more digit to the end of each list, we have to create an exponentially increasing number of sets to the list to give a complete accounting of all possible values. I think this proves the same thing. As the length L of the sets increases, the number N of all sets required to give all values increases such that N can never equal L. i.e. increase N, L just keeps getting further and further away.

In summary, I believe the proof does show that the possible values that can be created with any digit system is uncountable where 'uncountable' means we cannot show every possible value because they are infinite.

[Divine Insight]

[Replying to post 97 by benchwarmer]


I don't see your explanation as being a valid representation of what Cantor is doing.

For one thing, if we accept your explanation then we can apply it to anything, including the natural numbers. So what could it possibly be telling us about the natural numbers?

As far as I see it, Cantor's list must be a "complete" list of all possible numbers. Otherwise saying that he can create numbers that aren't on his list is meaningless.

Take my original binary example.

Here is the complete list of all possible numbers that can be expressed by using binary numerals that are only two digits wide.

00
01
10
11

There are four possible numbers, basically 0 thru 3 in decimal.

If I use your idea, of making up arbitrary sets I could then claim that after having included in my list, 00, and 01, that the numbers 10 and 11 cannot be on this list, therefore I conclude that binary numbers are uncountable.

So do you see why that can't work?

We already know that 10 and 11 are valid binary numbers that actually would be on a complete list of binary numbers. But the abstract sets that you have created wouldn't be able to address that fact at all.

So I don't see where your abstract method of making up arbitrary sets that have nothing to do with any actual completed lists could be claimed to be able to say anything about those completed lists.

As I have shown above, if we use your proposal, then we could claim that binary numbers would be precisely just as uncountable as the real numbers.

If you aren't addressing the actual complete lists of numeral representations of numbers, then you aren't saying anything about those complete lists.

Yet that is precisely what Cantor is claiming. He's claiming to be able to say something about the complete list of real numbers. He's claiming that a "complete" list would be uncountable because he can create numbers that would not be on that list.

If his list is incomplete, then it's meaningless, because the numbers he's claiming to have created that aren't on his list, would actually be on a real completed list.

How can that be?

I've already explained the problem. The real completed lists are necessarily far taller than they are wide (i.e. they necessarily contain far more rows than columns). Yet, Cantor's method assumes the lists can be expressed as perfectly "square" lists. (i.e. completed lists of numbers that have equal number of columns and rows).

That is mandatory because of the slope of his diagonal line that he is using to cross off digits. His diagonal line simply cannot keep up with lists that have more rows than columns. Yet that is precisely what he needs if he wants to be claiming to be addressing a completed list.

In short, Cantor's list cannot be complete. Therefore the fact that he can create numbers that aren't on his list is meaningless, because he cannot say that these are not on a completed list. In fact, he can't say anything at all about what might be on a completed list because his diagonal line can't keep up with the rapidly growing number of rows with ever new digit he crosses off.

Remember, by adding just one more digit his problem become exponentially worse. He gets further and further behind the real list with ever digit he crosses off.

So his "proof" is no proof of anything other than proof that he wasn't paying attention to the fact that completed lists are not "square" (i.e. they don't have the same number of rows and columns.) Yet he's treating them as though they do.

[mgb]

As far as I see it, Cantor's list must be a "complete" list of all possible numbers. Otherwise saying that he can create numbers that aren't on his list is meaningless.

Cantor's list is not complete. That is the point he is making. The list is infinite in terms of Aleph Null but the new numbers he creates are not on the list. Therefore the reals are greater than Aleph Null. No matter how infinite/complete his list is, the new number cannot be on it because it differs from every one of them.

Suppose his new number IS on the list. He changes a digit in it so now it is no longer on the list!

[Divine Insight]

As far as I see it, Cantor's list must be a "complete" list of all possible numbers. Otherwise saying that he can create numbers that aren't on his list is meaningless.

Cantor's list is not complete. That is the point he is making. The list is infinite in terms of Aleph Null but the new numbers he creates are not on the list. Therefore the reals are greater than Aleph Null. No matter how infinite/complete his list is, the new number cannot be on it because it differs from every one of them.

Suppose his new number IS on the list. He changes a digit in it so now it is no longer on the list!

Have you not paid any attention to what I've been saying?

What you just said here makes precisely the same error that Cantor made.

He assumes that the numbers he creates are not on his list. But that assumption is precisely the flaw in his argument.

Stop and think about the simplest possible example that I've given. A binary list that is only two digits long.

00
01
10
11

That is a complete list of binary numbers that are two digits long.

So now let's apply Cantor's ridiculous method to this and show that we can create numbers that are not on this list.

We start our list by crossing off every consecutive digit'

[strike]0[/strike]0

We cross off the first 0 and replace it with a 1

So our NEW number begins with 1

Then we move down a row over to the next digit and cross it off,

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

Then we replace that 1 with a 0 so our NEW number is 10 and we claim that this number cannot be on our list because we have already addressed those first two digits.

But wait!

Look at the complete list. The number 10 is already on the list. It's in the third row down which we haven't gotten to yet.

So to claim that the number 10 cannot be on our list is meaningless because our list cannot possibly be a complete list.

The flaw is because Cantor has wrongfully assumed that a complete list of numerals can be square. But it cannot be square. It's an inherent property of numerical systems that a complete list of numbers cannot be listed in a square list.

This is just an innate property of the numerical representation of numbers.

I've reduced the problem for you to binary. That's the simplest possible numerical system we can have. There cannot be a numerical system that lists all possible numbers in a square list that has the same number of rows as columns. It's simply not possible.

A binary numerical representation is as low as we can go and it's already rectangular. And it becomes increasingly rectangular with every digit column we add.

So what Cantor is doing is absurd. He can't pretend that his list is a complete list. Every number he constructs that he thinks isn't on his list is necessarily already on a truly complete list whether he realizes this or not.

In short, the list he is constructing can never become a complete list. And this holds true no matter how far he carries out his process. In fact, with every digit he adds his problem become exponentially worse.

In fact, look at the OP of this thread. With decimal numerals the problem is extremely worse than with binary numerals. And Cantor is indeed using decimal numerals.

So Cantor's so called diagonal "proof" is utter nonsense.

And the fact that mathematicians haven't caught this in all these years is truly sad.

They are still worshiping Cantor's proof as being "genius" when it fact it's grossly ignorant of how numerical systems even work.

~~~~

That Cantor himself didn't see his own mistake is understandable.

The fact that no mathematician has caught this mistake in over a century is highly troublesome. I'm not even a mathematician and I caught it.

[mgb]

You keep making the same mistake. Your numbers are finite. Cantor's have infinite decimal expansion. The diagonal method shows clearly that the new number cannot be on the list because its kth digit differs from the kth digit of the number on the kth row. If it is different from every number on the list it is not on the list. It is as simple as that. You cannot refute this with finite numbers because it does not work for finite numbers. You need to accept that finite is different, arithmetically, from infinite.

[Divine Insight]

You keep making the same mistake. Your numbers are finite. Cantor's have infinite decimal expansion. The diagonal method shows clearly that the new number cannot be on the list because its kth digit differs from the kth digit of the number on the kth row. If it is different from every number on the list it is not on the list. It is as simple as that. You cannot refute this with finite numbers because it does not work for finite numbers. You need to accept that finite is different, arithmetically, from infinite.

I can't believe you just said this.

How are the natural numbers not infinite?

[micatala]

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.

You are wrong. It is relevant. We aren't just talking about adding zeros, we're talking about adding any digits between 0 and 9.

I am fine with adding any number of digits selecting from the digits 0 through 9 after the decimal place, including infinitely many digits either repeating or non-repeating, to form representations for real #'s. That much was done well before Cantor came along.

Because you can, in particular, add infinitely many zeroes to any number after the decimal place, your square criteria is irrelevant.

Moreover if you truncate them at any point then Cantor's argument fails. It only appears to potentially work if you allow the lists to continue on infinitely. But the moment you pretend to do that you lose sight of the reason why it doesn't work. And the reason is precisely because Cantor's list isn't square.

Your objection is illogical since, for just one example

1/2=0.5=0.50000 . . . = 0.49999 . . .

with the last two representations having infinitely many digits repeating.

The bottom line is that Cantor's argument relies upon the claim that the numbers he requires are NOT on his list. But that claim makes absolutely no sense at all if the list isn't square.

You keep repeating this but you continue to simply be wrong. Neither the word nor even the concept in some implicit form of 'square' is a part of Cantor's argument.

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

Yes, I reject this notion. This notion is just as absurd as Cantor's ideas. This notion wrongfully assumes that you could complete an infinite process. But you can't. And therein lies the fallacy of claiming that 0.333... equals 1/3 exactly.


Does it qualify as being the same as 1/3 in the context of the Calculus Limit? Yes, but that's a totally different concept from saying that it's actually the same quantity.

Well, I am grateful for the clarification. I would point out that if you refuse to acknowledge the logical soundness of infinite repeating decimal representations, you are rejecting mathematics that predates Cantor and is taught in nearly every high school in the U.S.

A "Calculus Limit" is a quantity. Calculus limits that exist are numbers, just like numbers defined in any other way.

The limit of 0.3, 0.33, 0.333, . . . is the quantity 1/3, which is the same as the limit of 0.4, 0.34, 0.334, 0.3334. One can see this by noting the every element of the first sequence is less than 1/3 and every elements of the second is bigger than 1/3, and that the difference between the two sequences is the sequence

0.1, 0.01, 0.001, . . .

which clearly has a limit of zero. So the sequences have a common limit which is at least equal to 1/3 and at most equal to 1/3. 0.333 repeating infinitely is between the elements of the two sequences, so it must equal the common limit of the two sequences, namely 1/3.

If you deny the logical soundness of infinite decimal expansions than you are also denying that the square root of 2 has a decimal expansion, as well as every other irrational number.

[micatala]

[Replying to mgb]

Can you more precisely define what you mean.

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

Yes. The same procedure would create an integer not on the list if the integers had an infinity of digits.

I am not following you. No integer has an infinite number of digits. You can create an infinite list of integers, for example

1, 10, 100, 1000, . . .

but every integer in the list will have a finite number of digits.

[micatala]

If we try to run a diagonal line down this simplest finite list of numerals from zero to three we instantly find that we would need to claim that the numbers two (10) and three (11) are not on the list, but they are on the list.

You are missing Cantor's point. He is dealing with the infinite expansion of real numbers. You cannot apply finite arithmetic to infinities; eg. 1 + 10 = 11 but 1 + Aleph Null = Aleph Null.

YEs, he is missing the point in more than one way. For one, he is assuming that Cantor's argument applied to finite lists of numbers with finitely many digits is relevant to Cantor's argument as it really exists.

[micatala]

You cannot apply finite arithmetic to infinities;

In this specific proof not only can you apply finite arithmetic to this but you absolutely must apply it. If it can't even be made to work in a finite situation then it can hardly be extended to infinity.

This statement is simply not logical.

I can show that the natural numbers and the even natural numbers have the same cardinality by proving that the function f(n)=2n is a bijective, one to one correspondence between the two sets. In doing so, I have proven that a proper subset of the natural numbers (the even ones) has the same cardinality of the whole set of natural numbers. This can only happen with infinite sets.

No proper subset of a finite set can have the same cardinality as the whole set. So, it is false to say that if an argument does not work on finite sets it cannot work in the realm of the infinite.