Why Cantor's Diagonalization Proof is Flawed.

Discuss Physics, Astronomy, Cosmology, Biology, Chemistry, Archaeology, Geology, Math, Technology

Moderator: Moderators

Post Reply
User avatar
Divine Insight
Savant
Posts: 18080
Joined: Thu Jun 28, 2012 10:59 pm
Location: Here & Now
Been thanked: 15 times

Why Cantor's Diagonalization Proof is Flawed.

Post #1

Post by Divine Insight »

micatala wrote: 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? :-k

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.
[center]Image
Spiritual Growth - A person's continual assessment
of how well they believe they are doing
relative to what they believe a personal God expects of them.
[/center]

keithprosser3

Post #2

Post by keithprosser3 »

Well, first off Cantor was dealing with real numbers not integers. Does that matter? Yes. For convenience only it is usual to consider only (real) numbers between 0 and 1 so if we want 'squares of numbers' it's easy:

1) 0.0001 4 digits
2) 0.2345
3) 0.4534
4) 0.4567

which becomes
1) 0.00010 if you want 5 digits, just right pad with zeros.
2) 0.23450
3) 0.45340
4) 0.45670
5) 0.67543

The numbers ahead of the ) are just to indicate clearly the position or index of each real in the list of reals.

To make the square as wide as it is high, just pad with zeros on the right as required, as that doesn't change the value of the number.

Now perform the diagonalization step on the 5 digit square thus:
1) 0.10010
2) 0.24450
3) 0.45440
4) 0.45680
5) 0.67544

producing the new number 0.14484 which is not - cannot be - in the original list of 5 numbers. Doing the same on a '6 digit square' would obviously produce a new 6 digit number not in the list, and so for 7 digits, 8 digits and so for any number of digits you like, without limit and beyond, even if the list was infinitely long (and equally infinitely wide)

Thus the real numbers between 0 and 1 are not countable, ie no integer-indexed list of them can contain all of them because at least one real number - the diagonal number - could not have been in the list.

Obviously if the real numbers between 0 and 1 are uncountable then the set of all reals is also uncountable.

QED, as Euclid would say.

I have no idea what DI is trying to prove or disprove. It seems to have nothing to do with Cantor's theorem to me.

User avatar
Divine Insight
Savant
Posts: 18080
Joined: Thu Jun 28, 2012 10:59 pm
Location: Here & Now
Been thanked: 15 times

Post #3

Post by Divine Insight »

[Replying to post 2 by keithprosser3]

But Keith, you forgot one extremely important thing.

You are supposed to be constructing a "Completed List".

There is no way that you can claim that your arbitrary random number list represents a "Completed List" of anything.

Just because you created a new number that NOT already on your arbitrary list is totally meaningless. It would only be meaningful if you could claim to complete this process.

Cantor is looking at this and saying, "Well, if we carry it out to infinity we will have completed it.

But no, that's wrong. That is the flaw in his argument.

The fact that he has created a new number that's not on HIS list is totally meaningless. That's just a result of the fact that numerical systems of representation are NOT SQUARE.

Take away your decimal point and you can do the same thing with integers.

1) 1
2) 12
3) 167
4) 5785


Ok, there's the beginning of my list of integers.

I need to make the integers on the right an extra digit long in every step just to facilitate the diagonalization method of elimination.

So now I run my diagonal line down that list


1) [strike]1[/strike]
2) 1[strike]2[/strike]
3) 16[strike]7[/strike]
4) 578[strike]5[/strike]

Replace the following

1 = 2
2 = 3
7 = 8
5 = 6

My new number is 2386

Therefore I've created an integer that's not on my list. And if I keep this up to infinity I will ALWAYS have a NEW integer that's not on my list.

It's numerical trickery.

It's meaningless. The decimal point doesn't save it, it only serves to hide the error.

You can use this same method to prove that the integers can't be put into a correspondence with themselves. Except when you do this with the Integers it becomes CRYSTAL CLEAR that your list is necessarily incomplete. And then you quickly see the flaw staring you right in the face.

This becomes illusive and unseen when you start using decimal notation.

You don't see that your list can never be COMPLETE.

But that is PARAMOUNT.

It your list isn't complete, then how can you claim that the number that you just created cannot be on the completed list?

Remember the COMPLETED LIST CANNOT BE SQUARE!

That is the flaw.

If you have only generated a SQUARE LIST then your list cannot be complete.

But using the diagonal method to create the list in the first place FORCES your list to be square. Therefore it CANNOT be complete.

That is the logical error of Cantor's so-called "Proof".
[center]Image
Spiritual Growth - A person's continual assessment
of how well they believe they are doing
relative to what they believe a personal God expects of them.
[/center]

keithprosser3

Post #4

Post by keithprosser3 »

Take away your decimal point and you can do the same thing with integers.
a)no you can't because you can right pad decimal numbers with zeros harmlessly. Padding with zeros is not harmless with integers. You can make your square wider than it is high if you wanted to by adding lots of zeros on the end of the numbers with decimals.

b)You can't change from reals to integers anyway because the theorem is about the uncountability of the real numbers - ie you can't put the reals into 1:1 correspondence with the integers.

Your other complaint is that it's impossible to complete an infinite process.

The point of Cantor's proof is that it describes a process by which a new number can be produced from the numbers in a list in such a way it is guaranteed the new number is not in the list regardless of the list's length.

No matter how long (or indeed short) the list is, diagonalising will produce a number not in the list. Guaranteed.

Of course with little lists like my ones with only 4 or 5 digits there are lots of real numbers not included as well as the diagonal number, such as 0.25 and 0.33 but that's beside the point. The point is the diagonal number is always missing from any list.

Note - any list. That includes infinitely long lists.

So can a list contain all the real numbers? No, because there is always going to be that pesky diagonal real number not in the list. Even if the list is so long it needs all the integers to index it from top to bottom it would have the same problem.

QED - there are indeed more reals than integers.

Now it is still possible to complain that all this talk of infinitely long lists and numbers with infinitely many decimal digits is daft because they can't exist in the physical universe. But that is a different issue. If you have a problem with infinite quantities in general, there is no need to take it out on this particular theorem! If you reject infinity on principle then the theorem doesn't need disproving - the fact it even mentions infinity would disqualify it.
Last edited by keithprosser3 on Thu Oct 24, 2013 10:37 pm, edited 1 time in total.

User avatar
Divine Insight
Savant
Posts: 18080
Joined: Thu Jun 28, 2012 10:59 pm
Location: Here & Now
Been thanked: 15 times

Post #5

Post by Divine Insight »

keithprosser3 wrote: Now it is still possible to complain that all this talk of infinitely long lists and numbers with infinitely many decimal digits is daft because they can't exist in the physical universe. But that is a different issue. If you have a problem with infinite quantities in general, there is no need to take it out on this particular theorem! If you reject infinity on principle then the theorem doesn't need disproving - the fact it even mentions infinity disqualifies it.
So how about my integer that can't be on the list of integers?

How is that any different? :-k

I can create an integer in the same way using the same diagonal process. It will never be on my list for the obvious reasons.

Therefore the integers cannot be put into a one-to-one correspondence with themselves for the same reason. I will always have that one pesky integer that's not on the list.

It's no different at all.

I realize that it's meaningless because it's a bogus proof.

But if you think this proof is valid, then how do you explain that I can create an integer using the same method that can't be put into a one-to-one correspondence with the integers themselves?
[center]Image
Spiritual Growth - A person's continual assessment
of how well they believe they are doing
relative to what they believe a personal God expects of them.
[/center]

lao tzu
Apprentice
Posts: 106
Joined: Mon Dec 03, 2007 1:04 pm
Location: Everglades

Re: Why Cantor's Diagonalization Proof is Flawed.

Post #6

Post by lao tzu »

Divine Insight wrote: They keep publishing this proof and teaching it like as is it has merit when in fact it's totally bogus.
Dear DI,

You might want to consider the fact that all of Cantor's numbers are real numbers, are less than one, and are represented by an infinite sequence of digits, whereas all of your numbers are integers, are greater than one, and are represented by a finite number of digits.

In short, your rebuttal takes the form of arguing that if all real numbers were integers, then they, like the integers, would also be countable. Have you ever seen the proof by parity that the square root of two cannot be represented as a quotient of whole numbers? We can prove there are real numbers that are not rational, and hence, that your rebuttal is irrelevant, and more, that your opinion of Cantor's proof does not rise beyond what Pauli would dismiss as "not even wrong."

As ever, Jesse
There is no lao tzu.

User avatar
micatala
Site Supporter
Posts: 8338
Joined: Sun Feb 27, 2005 2:04 pm

Post #7

Post by micatala »

Well, I say keithprosser has already waded in.

I do not have time now to address all that has gone on, but I will ask a few questions of Divine Insight for clarification.


I take you accept the existence of individual natural numbers.

You stated in the other thread you do not accept the existence of irrational numbers. Is that a correct understanding of your view?

How do you define the existence of numbers in general?

Do you accept the existence of rational numbers? Here, I define rational numbers in the usual way. Any number that can be expressed as a ratio or fraction of integers where the denominator is not zero.


How do you define cardinality? I define two sets to have the same cardinality if there exists a bijective (one-to-one and onto) function from one set to the other. Do you accept this definition, at least as applied to finite sets?

Do you accept the existence of any infinite sets? Is the set of positive integers, for example, a legitimate set in your view? How about the set of all integers?
" . . . the line separating good and evil passes, not through states, nor between classes, nor between political parties either, but right through every human heart . . . ." Alexander Solzhenitsyn

User avatar
Divine Insight
Savant
Posts: 18080
Joined: Thu Jun 28, 2012 10:59 pm
Location: Here & Now
Been thanked: 15 times

Re: Why Cantor's Diagonalization Proof is Flawed.

Post #8

Post by Divine Insight »

lao tzu wrote: Dear DI,

You might want to consider the fact that all of Cantor's numbers are real numbers, are less than one, and are represented by an infinite sequence of digits, whereas all of your numbers are integers, are greater than one, and are represented by a finite number of digits.
What? :-k

You say the integers are greater than one, and are represented by a finite number of digits?

Where do you come up with that? Are you saying that there exists a largest integer?

If not, then how can you say that they are represented by a finite number of digits?

You can always add another digit and you'll still have an integer. So to say that they have to have a finite number of digits seems to be a claim with no proof?
lao tzu wrote: In short, your rebuttal takes the form of arguing that if all real numbers were integers, then they, like the integers, would also be countable.
You are off track here entire. I never claimed the the real numbers are countable. I simply claimed that Cantor's Diagonalization Proof is flawed.

I'm am not arguing that all real numbers need to be countable. However, I can actually show that they necessary have to be. But that is a whole other argument unrelated to the topic of this thread.
lao tzu wrote: Have you ever seen the proof by parity that the square root of two cannot be represented as a quotient of whole numbers?
That's totally irrelevant to Cantor's diagonalization proof.
lao tzu wrote: We can prove there are real numbers that are not rational.
And I have no problem with that. I even understand why this is the case. ;)
lao tzu wrote: , and hence, that your rebuttal is irrelevant, and more, that your opinion of Cantor's proof does not rise beyond what Pauli would dismiss as "not even wrong."

As ever, Jesse
My observations of the flaw in Cantor's proof has nothing at all to do with whether the real numbers can be placed in a one-to-one correspondence with the integers.

All I'm saying is that Cantors Proof is flawed. Even if the conclusion implied by his so-called proof is correct, his proof is still flawed and not a valid proof at all.

Just because you happen to come up with the right answer doesn't mean that the proof you used was correct.

But the conclusion too could be wrong. Just because irrational numbers can't be expressed neatly as a ratio of integers doesn't automatically mean that they can't be placed into a one-to-one correspondence with the integers. Where is there any logical reasoning to support such a conclusion?

I have no need to place the "Real Numbers" in a direct correspondence with the integers. But that's beside the point.

I"m addressing the validity of Cantor's proof here. I'm not arguing about whether or not the reals can be placed in a one-to-one correspondence with the integers.

That is a totally different argument.
[center]Image
Spiritual Growth - A person's continual assessment
of how well they believe they are doing
relative to what they believe a personal God expects of them.
[/center]

User avatar
micatala
Site Supporter
Posts: 8338
Joined: Sun Feb 27, 2005 2:04 pm

Re: Why Cantor's Diagonalization Proof is Flawed.

Post #9

Post by micatala »

lao tzu wrote:
Divine Insight wrote: They keep publishing this proof and teaching it like as is it has merit when in fact it's totally bogus.
Dear DI,

You might want to consider the fact that all of Cantor's numbers are real numbers, are less than one, and are represented by an infinite sequence of digits, whereas all of your numbers are integers, are greater than one, and are represented by a finite number of digits.

In short, your rebuttal takes the form of arguing that if all real numbers were integers, then they, like the integers, would also be countable. Have you ever seen the proof by parity that the square root of two cannot be represented as a quotient of whole numbers? We can prove there are real numbers that are not rational, and hence, that your rebuttal is irrelevant, and more, that your opinion of Cantor's proof does not rise beyond what Pauli would dismiss as "not even wrong."

As ever, Jesse

Good points.

I have provided the proof you allude to in the other thread.

http://debatingchristianity.com/forum/v ... 480#607480
" . . . the line separating good and evil passes, not through states, nor between classes, nor between political parties either, but right through every human heart . . . ." Alexander Solzhenitsyn

User avatar
Divine Insight
Savant
Posts: 18080
Joined: Thu Jun 28, 2012 10:59 pm
Location: Here & Now
Been thanked: 15 times

Post #10

Post by Divine Insight »

micatala wrote: Well, I say keithprosser has already waded in.

I do not have time now to address all that has gone on, but I will ask a few questions of Divine Insight for clarification.


I take you accept the existence of individual natural numbers.
I accept that this can be a rational and intuitively comprehensible idea, that can be easily formally defined, yes.
micatala wrote: You stated in the other thread you do not accept the existence of irrational numbers. Is that a correct understanding of your view?
I reject them as "cardinal quantities". I feel that they violate the definition of cardinality.

I accept them as relative quantitative relationships associated with self-referenced situations. I would even say that it's basically impossible to define a meaningful irrational quantity that is not based on a self-referenced situation.

They are not the cardinal property of a collection of things.
micatala wrote: How do you define the existence of numbers in general?
To begin with numbers are ideas of quantity. They are defined and understood as being the quantitative property of a collection of individual things, where the individuality of the things within the collection must be recognizable.

Numeral are not numbers. They are symbols or names given to popular quantities. We have created a very clever systemd of numerical representation where a zero serves as a place holder where there is no quantity, and the columns in which the numerals appear are also weighted by a representative quantity. Obviously the base ten is the most common numerical system, but we can also use Binary, Hexadecimal, and many other systems of representations. All of these systems of representation are just that; systems of representation. They are not themselves numbers. They are just symbols to keep track of information about numbers. The numbers never change no matter what numerical system we actually use. Of course the numerical representation changes quite dramatically.

IMHO, we only need one definition for "number" and that is the cardinal definition of a quantitative property of a collection of recognizable individual things or objects.

IMHO, this is the only definition we need.
micatala wrote: Do you accept the existence of rational numbers? Here, I define rational numbers in the usual way. Any number that can be expressed as a ratio or fraction of integers where the denominator is not zero.
I don't see the point in treating this like a new invention. Why not just recognize them to be the ratios that they are? Sure we can put them into decimal notation and play with them in that form too, but they are still just ratios of cardinal quantities. Why treat them as though they are a new idea? They are already well-defined as the ratios of natural numbers.

It's just superfluous to act like they are something new or different.
micatala wrote: How do you define cardinality? I define two sets to have the same cardinality if there exists a bijective (one-to-one and onto) function from one set to the other. Do you accept this definition, at least as applied to finite sets?
Yes.
micatala wrote: Do you accept the existence of any infinite sets? Is the set of positive integers, for example, a legitimate set in your view? How about the set of all integers?
Yes and no.

Yes, I accept the concept on the condition that the term "infinite" is understood to mean "endless".

As soon as someone starts claiming that this represents some sort of completed quantity then all bets are off.

So as soon as we start talking about infinite "quantities" we need to be extremely careful.

Let me put it this way, I DO NOT see infinity as being a quantitative property of a set. In other words, I do not treat infinity as an idea of cardinality. Instead I see infinity as being a qualitative property of a set. It simply means that the set is basically ill-defined in terms of cardinality and that it has the potential of being endless.

Infinity is a potential. It's not a cardinal number. That's my position on that.

It's a qualitative property of a set not a countable cardinal quantitative property.

You cannot count the elements in the set of integers. They are infinite (i.e. endless). To even say that they are countable is meaningless, IMHO.
[center]Image
Spiritual Growth - A person's continual assessment
of how well they believe they are doing
relative to what they believe a personal God expects of them.
[/center]

Post Reply