Thread: Cantor's diagonal argument is wrong

Originally Posted by Nylo

I don't completely agree with you. Cantor's demonstration that the set of the subsets of the naturals is actually strictly bigger than the set of the naturals, is in my opinion absolutely flawless. And I admire him for having demonstrated such a thing. So one infinite is undoubtedly bigger than the other in that case. I just tend to disagree with the cardinality of reals being bigger than that of naturals. His demonstration for that particular case is wrong.

I think that this last reply is the most reasonable in this otherwise ridiculous thread.

Have any of you read GEORG CANTOR: His Mathematics and Philosophy of the Infinite by Joesph Warren Dauben?
It is without doubt the most complete and actuate account of Cantors' work. In my copy beginning on page 165, there is a good discussion of the THE DENATIONALIZATION PROOF OF 1891 .

Originally Posted by Plato

I think that this last reply is the most reasonable in this otherwise ridiculous thread.

Have any of you read GEORG CANTOR: His Mathematics and Philosophy of the Infinite by Joesph Warren Dauben?
It is without doubt the most complete and actuate account of Cantors' work. In my copy beginning on page 165, there is a good discussion of the THE DENATIONALIZATION PROOF OF 1891 .

Thank you for your contribution. No, I haven't read that book. In fact, I hadn't ever heard Cantor's name just three weeks ago. I came to it by accident. I have studied some advanced mathematics, but I am not a matematician, I am an engineer and for me mathematics is not a hobby or a passion, they're just a tool.

Is there, in the page that you cite, any difference with what wikipedia says regarding the demonstration that we are discussing? Links would be most welcome. If what wikipedia says is an accurate description of Cantor's diagonal argument, then I stand by everything that I have said about it so far. Argumentum ad auctoritatem do not impress me. The greatest genious can make mistakes too.

Originally Posted by Nylo

Is there, in the page that you cite, any difference with what wikipedia says regarding the demonstration that we are discussing? Links would be most welcome. If what wikipedia says is an accurate description of Cantor's diagonal argument, then I stand by everything that I have said about it so far. Argumentum ad auctoritatem do not impress me. The greatest genious can make mistakes too.

It is almost impossible for me as someone who has worked with these ideas for forty years to even understand your objections.

You may not be aware of the school of constructivism.
Basically, they reject the use of the law of the excluded middle. This law states that, for any proposition, either that proposition is true or its negation is.

I read the book more than twenty years ago while working on the philosophy of mathematics as related to issues in non-standard analysis. So I cannot answer your about the book.

Originally Posted by Plato

You may not be aware of the school of constructivism.

You are right, I was not aware. I don't pretend to know more mathematics than any of you. I'm quite ignorant regarding many philosophical aspects of mathematics. But from the wikipedia page that you linked, I can read: "In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its existence, according to constructivism".

According to contructivism, therefore, in the sequence that I provided above, you will not be able to prove the existence of a real for which I cannot associate a natural number, because no method that you can imagine will find such a real. Cantor's method fails too. Cantor's method applied to that sequence provides the real 0.01111111... with infinite 1s. But I can demonstrate that such a real has a place in my list. Its position is calculated, from the general expression provided, as the sum, from i=1 to infinitum, of 10^i. I can demonstrate that the result of that operation is a natural, and therefore is a position in my list, even if it is a position that you will never be able to reach. That doesn't stop it from being a natural number. Cantor's method fails to find a real that is not in my list, because what he thinks that is a diagonal, in reality is not. I have built my "matrix" in such a way that there will be infinitely more rows than columns, despite both being infinite.

Edited to add:

It is almost impossible for me as someone who has worked with these ideas for forty years to even understand your objections.

Let's then simplify my objection. Among other things, I object Cantor's method because it fails to provide a real which would not be present in my sequence.

Originally Posted by Nylo

You are right, I was not aware. I don't pretend to know more mathematics than any of you. I'm quite ignorant regarding many philosophical aspects of mathematics. But from the wikipedia page that you linked, I can read: "In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its existence, according to constructivism".

Your being an engineer means that we speak an almost different languages.

Do you accept the idea that it is possible to make a list of the rational numbers?
That is, we can use the positive integers to name, list, the rationals:
.
You give me any rational number whatsoever, I can tell you its name which is a positive integer.

If your answer to that is yes, then we can continue.

If your answer to that is no, then we any further discussion is pointless.

My answer is yes, it is possible.

Originally Posted by Nylo

My answer is yes, it is possible.

O.K.
Here is the best example of the diagonal process that I know.
This is in The Mathematical Experience by Davis & Hersh, p237.

Think of the set of all functions that map positive integers to positive integers.
Now think that we can list that set: .

Then define . We can show that but it cannot be in the list.

If we admit the rule of the excluded middle , then it is proven that cannot be listed.

If you do not admit the rule of the excluded middle then all of that is pointless.
We are speaking different languages. Our languages actually determine the realities in which we live (see L Wittgenstein.

I cannot be arsed to go through this, but will make one comment:

Originally Posted by Nylo

However, even if we cannot calculate it, we know a couple of things about that infinite result in particular:
[LIST=1][*]It is natural, as it is made of the sum of other numbers which are also natural numbers, and the sum of any two natural numbers is another natural number.

An infinite sum of naturals, assuming it converges is not necessarily a natural, to conclude that your sum is a natural either you must show that only a finite number of terms are non-zero or do a lot more work to prove it.

.

Originally Posted by Plato

O.K.
Here is the best example of the diagonal process that I know.
This is in The Mathematical Experience by Davis & Hersh, p237.

Think of the set of all functions that map positive integers to positive integers.
Now think that we can list that set: .

Then define . We can show that but it cannot be in the list.

If we admit the rule of the excluded middle , then it is proven that cannot be listed.

If you do not admit the rule of the excluded middle then all of that is pointless.
We are speaking different languages. Our languages actually determine the realities in which we live (see L Wittgenstein.

First, I don't see the relationship between this and my acknowledgement or not that the rationals are countable. Why did you set it as a prerrequisite to continue the discussion?

Second, as you said, this is nothing but another version of the same diagonal process, and is flawed in exactly the same way.

If S is the set of all possible functions that sort positive integers, then S has strictly more functions than positive integers you can find, despite you being able to find infinite positive integers. This is demonstrable, in a somewhat similar way to Cantor's demonstration that the infinite number of subsets of N is strictly bigger than the infinite elements of N. This means that the matrix that is made of all those sequences of positives being rows, and the nth element of each of them being columns, is not square, or at the very least, it cannot be claimed to be square. If it is not square, there doesn't exist such a thing as its diagonal.

You will have found after finishing with the infinite set of positive integers, but having done so, in a 1 to 1 relationship, you will still not have finished with the infinite set of ways to sort the infinite positive integers. There will be "more rows at the bottom". And your will be one of them, so it will exist in the set of infinite ways to sort positive integers.

Originally Posted by Nylo

Is there, in the page that you cite, any difference with what wikipedia says regarding the demonstration that we are discussing? Links would be most welcome. If what wikipedia says is an accurate description of Cantor's diagonal argument, then I stand by everything that I have said about it so far. Argumentum ad auctoritatem do not impress me. The greatest genious can make mistakes too.

I trust that you are aware that Cantor's diagonal slash is not the only proof of the uncountability of the reals?

Originally Posted by zzephod

I trust that you are aware that Cantor's diagonal slash is not the only proof of the uncountability of the reals?

I'm aware that other demonstrations exist. However I don't know them. That's why my only claim so far is that Cantor's demonstration is wrong. I am not 100% sure that his conclusion is wrong, and I stated that in the first paragraph of my first post. It's entirely possible that he gets the right answer (that reals are not countable) despite doing things in the wrong way. In order to verify this, I have already proposed a sequence of all reals in (0,1) that I THINK has them all. And I have proved that Cantor's method cannot find a real that is not in the sequence. Maybe some other method developed by someone else can find it. I just cannot imagine such a method. And that's why I have come to this forum, where great experts in mathematics are supposed to participate, people with far more mathematics baggage than I have, to be illustrated on which real number can be proved not to exist in the sequence that I have provided. I can't find it.

Originally Posted by zzephod

Is an array square or not?

Since is not a number, much less an integer, the question makes no sense. There is no such thing as an " array".

Originally Posted by zzephod

I trust that you are aware that Cantor's diagonal slash is not the only proof of the uncountability of the reals?

For me, that's totally irrelevant. I'm not arguing against the conclusion of Cantor's diagonal argument. I'm saying that the argument itself is logically flawed and doesn't prove a thing.

If he happened to be right it was a pure coincidence.

What upsets me is not the conclusion of his argument, but rather the fact that people can't see the flaw in the argument.

Cantor makes two assumptions which can't both be true simultaneously:

1. First assumption: The list that he is constructing using his diagonal process is a "complete list" of all possible numbers of that form. (it cannot be because of the following)
2. Second assumption: A completed list of all possible numbers is square. (this is required for his diagonal process to be valid)

Both of these assumptions are false. The list he is constructing using his diagonal method cannot be a "complete list". And the reason it can't be a complete list it because a complete list of numbers represented by decimal notion cannot be made to be square. I've already demonstrated this in a previous post.

If fact, this can't be done using any numerical notation. When I first realized this I instantly took it to the case of using binary numerals (the smallest possible numerical notation we can use) and I confirmed that completed lists of numbers are still rectangular even in that basic simplest case. And their rectangular structure grows exponentially with every digit added to their width.

So Cantor's diagonal method of constructing a "completed list" of number using decimal numeric notation is impossible.

This so-called "proof" truly needs to be wiped out of math books. It's a false proof that actually suggests that this process is meaningful when in fact it's grossly logically flawed.

Whether the reals can be put into a one-to-one correspondence with natural numbers is a totally separate question. What I'm saying is that Cantor's Diagonal Proof is no proof at all. It's grossly flawed and should be removed from math books.

And potentially more to the point, mathematicians should be taught something about the nature of numeral systems!

Numerals aren't really numbers anyway. They are just labels we use to name the numbers. So when we start attempting to prove things about numbers using the properties of numerals (as Cantor tries to do in his diagonal proof) we've totally lost track of that difference.

So exposing this flaw in Cantor's diagonal proof may actually serve to help mathematicians realize the folly of trying to use numerals to prove things about numbers.

If there exist other "proofs" that the reals cannot be "counted", that's a totally different topic. I'm not saying Cantor's conclusion was necessarily false. But his method of proof most certainly is grossly flawed. It's simply an extremely flawed argument based on numeral notation. An argument that doesn't even hold true for numerical systems. Much less for the numbers they represent.

Originally Posted by HallsofIvy

Since is not a number, much less an integer, the question makes no sense. There is no such thing as an " array".

Doubly countably infinite.

Also is a cardinal number.

.

Originally Posted by zzephod

I cannot be arsed to go through this, but will make one comment:



An infinite sum of naturals, assuming it converges is not necessarily a natural, to conclude that your sum is a natural either you must show that only a finite number of terms are non-zero or do a lot more work to prove it.

.

What you say is interesting. I thought that an infinite sum of naturals is a natural, no matter if it converges or not. If it converges, then IN ADDITION it can be calculated, whereas if it doesn't, it can't. But it has to be a natural as it is the sum of naturals. Again, this has a lot of philosophy behind, I guess, and I'm no expert in mathematical philosophy. So any links that you can provide asserting what you said, that a sum of naturals with an incalculable result is not a natural, will be most welcome.