MHB Is Cantor's second diagonal proof valid?

[Phar2wild]

Cantor "proved" that if there was a list that purported to include all irrational numbers, then he could find an irrational number that was not on the list.

Please consider two scenarios:

1. The list claims to contain all irrationals but doesn't.

2. The list absolutely contains all irrationals.

In scenario 1 Cantor's proof tells us that there is a number that is missing.

In scenario 2 Cantor's proof tells us that there is a number that is missing even though the list is complete.

In scenario 2 the proof returns a false answer.

Am I missing something? Is there any significance here? Is there some reason that this proof would not work with infinite sets?

All comments welcome!

Thanks,

Robert Hall

 

[Evgeny.Makarov]

Am I missing something?

This question is best asked when one discovers a supposed contradiction. For example, you may write a "proof" that 1 = 2 like this one, and if you don't see where the error is, it makes sense to ask, "Am I missing something?"

Is there any significance here?

Yes, Cantor's proof is very significant.

Is there some reason that this proof would not work with infinite sets?

Why do you think it does not?

 

[Phar2wild]

This question is best asked when one discovers a supposed contradiction. For example, you may write a "proof" that 1 = 2 like this one, and if you don't see where the error is, it makes sense to ask, "Am I missing something?"

Yes, Cantor's proof is very significant.

Why do you think it does not?

Yes, I agree. These proofs that result in 1=2 usually involve division by zero and you would be quite right to ask "Am I missing something?"

I question it because if there was a list that did absolutely contain all the irrationals then Cantor's proof would provide a number that supposedly is not on the already complete list. To me this is a contradiction in logic. IF the list is complete THEN there can be no irrational that is not on the list. I have put forward this hypothetical scenario and I conclude that if Cantor's proof still appears to work, then we must be making a false assumption somewhere. It would be like saying here is a list of the ten digits that we use: 0,1,2,3,4,5,6,7,8,9. If someone told me they could produce a digit that was not on the list, I would be suspicious to say the least.

Here are two statements:

1. The list is complete.
2. Here is a number that is not on the list.

One must be false.

I don't doubt that Cantor had a brilliant idea; it just bothers me that it would return the same result with a theoretical truly complete list.I don't know why the proof would not work with infinite sets. With that particular question, I was just exploring possibilities.

Thanks.

Robert

 

[Evgeny.Makarov]

The fact is that no list of irrationals (whose elements are numbered by natural numbers) is complete. The proof makes a temporary assumption that the list is complete and arrives at a contradiction. Therefore, the assumption is false. Even though within the proof there is a possibility that some list may be complete, the verdict after the proof is finished is that no list is complete.

I don't know why the proof would not work with infinite sets.

Which infinite set do you have in mind? What exactly do you mean when you say that the proof does not work with infinite sets? The proof uses natural numbers, for example, which is an infinite set.

 

[Phar2wild]

The fact is that no list of irrationals (whose elements are numbered by natural numbers) is complete. The proof makes a temporary assumption that the list is complete and arrives at a contradiction. Therefore, the assumption is false. Even though within the proof there is a possibility that some list may be complete, the verdict after the proof is finished is that no list is complete.

Which infinite set do you have in mind? What exactly do you mean when you say that the proof does not work with infinite sets? The proof uses natural numbers, for example, which is an infinite set.

I didn't have an infinite set in mind. I was answering your question.

Conversation went as follows:

Me: Is there some reason that this proof would not work with infinite sets?

You: Why do you think it does not?

Me: I don't know why the proof would not work with infinite sets. With that particular question, I was just exploring possibilities.

You: Which infinite set do you have in mind? What exactly do you mean when you say that the proof does not work with infinite sets? The proof uses natural numbers, for example, which is an infinite set.

I think I may have posed too many questions too close together and the conversation veered off on a tangent or something like that!With regard to the rest, I'm still bothered by it and have a feeling that something's a little off about the whole thing.
If I can come up with anything to clarify I will add to the post.

I do thank you for the time that you have taken to respond.
Robert

 

[JeffJo]

Cantor "proved" that if there was a list that purported to include all irrational numbers, then he could find an irrational number that was not on the list.

Cantor never made any such proof. He did make a similar one, but it is almost always taught incorrectly.

The proposition Cantor wanted to prove was that there exists at least one infinite set that cannot be put into 1:1 correspondence with the natural numbers. To prove it, all he needed was one example. And the set of irrational numbers was never the one he used.

Define a "Cantor String" to be any infinite-length string using only the two characters "m" and "w." So "mmmm...", "mwmwmw...", and "mwmwwmwwwmwwww..." are all Cantor Strings. Here's a brief summary of the proof:

1. Assume C is a countably infinite set of Cantor Strings; that is, that it can be put into a 1:1 correspondence with the natural numbers. This can be called a list.
2. Make string D by finding the nth character of the nth string in the list of C, for all n; and then making the nth character of D the opposite of that character.
3. String D is a Cantor String.
4. String D is not in C.
5. Therefore, L="If a set of Cantor Strings is infinitely countable, then it does not contain every Cantor String" is a true statement.
6. So the contrapositive of L is also a true statement, "If a set contains every Cantor String, then it is not infinitely countable."
7. QED.

Correcting your scenarios to be about Cantor Strings:

Please consider two scenarios:

1. The list claims to contain all [Cantor Strings] but doesn't.

No such claim was ever made.

2. The list absolutely contains all [Cantor Strings].

The proof was that a "list" cannot.

Am I missing something?

Several. The most important one is that the proof is not a proof by contradiction, it is a proof by contrapositive. That is, you can prove "If A, then B" by proving "If not B, then not A."

 

[Phar2wild]

Cantor never made any such proof. He did make a similar one, but it is almost always taught incorrectly.

The proposition Cantor wanted to prove was that there exists at least one infinite set that cannot be put into 1:1 correspondence with the natural numbers. To prove it, all he needed was one example. And the set of irrational numbers was never the one he used.

Define a "Cantor String" to be any infinite-length string using only the two characters "m" and "w." So "mmmm...", "mwmwmw...", and "mwmwwmwwwmwwww..." are all Cantor Strings. Here's a brief summary of the proof:

1. Assume C is a countably infinite set of Cantor Strings; that is, that it can be put into a 1:1 correspondence with the natural numbers. This can be called a list.
2. Make string D by finding the nth character of the nth string in the list of C, for all n; and then making the nth character of D the opposite of that character.
3. String D is a Cantor String.
4. String D is not in C.
5. Therefore, L="If a set of Cantor Strings is infinitely countable, then it does not contain every Cantor String" is a true statement.
6. So the contrapositive of L is also a true statement, "If a set contains every Cantor String, then it is not infinitely countable."
7. QED.

Correcting your scenarios to be about Cantor Strings:

No such claim was ever made.The proof was that a "list" cannot.

Several. The most important one is that the proof is not a proof by contradiction, it is a proof by contrapositive. That is, you can prove "If A, then B" by proving "If not B, then not A."

Interesting, but I just want to be clear. I have seen several examples of this proof in math books and they use as an example ( to the best of my recollection ) non terminating decimals. Based on this I have assumed that this proof was about irrational numbers.

There is a lot in your answer for me to absorb and I would like to address one thing at a time.

My question is:

Would Cantor's second diagonal proof apply to irrational numbers?

Thank you for your reply. I appreciate any help in my understanding of all aspects of this.

Robert