## Cantor's Diagonalization Proof of the uncountability of the real numbers

 Quote by MrAnchovy NOOOOOO - Cantor asks us to construct a list of all the real numbers. He then constructs a real number not on that list, proving that such a list cannot exist.
Ok MrAnchovy. I get it now!

You've answered my question and solved the whole problem. I was indeed viewing the proof incorrectly.

Unfortunately it doesn't help.

Why does it not help?

Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number".

He's simply demanding that a "Real Number" is necessarily an "infinite" decimal expansion by definition and assuming that a "Rational Number" cannot be described by an "infinite" decimal expansion.

Another problem is that his "proof" would obviously work for any numbers. Not just reals.

Think of it this way. Just take the decimal point in his proof in his proof away.

What do you have left? A list of natural numbers.

You can go down that list in precisely the same way and proof that even the Natural Numbers can't be put into a correspondence with themselves.

How so?

Well, let's try it.

Start our list with the arbitrary natural number of 1

1

We cross that out and replace it with any arbitrary digit (say 9) So we have a "new number" 9.

Lets continue, we'll need a two digit number to work on next so lets choose 23 our list so far looks as follows:

1
23

Replace the 3 with 5. Our newly constructed number is 95.

Move down another row pick another arbitrary natural number, we'll need one that is at least 3 digits wide or more, lets pick 3476 just for fun.

Here's our new list

1
23
3476

Now we need to replace the 7 with something other than 7, let's choose 8.

Our new number is now 958, and so on.

So we currently have a list of natural numbers

1
23
3476

And thus far we've created a "new number" 958 that isn't on this list.

And we can continue down the list like this just like Cantor and end up with precisely the same situation he has. (i.e. we can create a supposedly "new" natural number that isn't already on the list of numbers that we have created in this way)

Does that mean that we can create a new Natural Number that isn't already on the list of Natural Numbers? And that the Natural Numbers must then be "uncountably infinite" just like the Reals?

This so-called "proof" doesn't prove anything. In fact, if it proves anything at all it proves that the Natural Numbers must have the same weird cardinality as the reals because we can use the very same process as Cantor used to prove it for the Natural Numbers too.

So how are we any further ahead toward proving anything unique?

Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus
 Quote by Leucippus Ok MrAnchovy. I get it now! You've answered my question and solved the whole problem. I was indeed viewing the proof incorrectly. Unfortunately it doesn't help. Why does it not help? Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number". He's simply demanding that a "Real Number" is necessarily an "infinite" decimal expansion by definition and assuming that a "Rational Number" cannot be described by an "infinite" decimal expansion. Another problem is that his "proof" would obviously work for any numbers. Not just reals. Think of it this way. Just take the decimal point in his proof in his proof away. What do you have left? A list of natural numbers. You can go down that list in precisely the same way and proof that even the Natural Numbers can't be put into a correspondence with themselves. How so? Well, let's try it. Start our list with the arbitrary natural number of 1 1 We cross that out and replace it with any arbitrary digit (say 9) So we have a "new number" 9. Lets continue, we'll need a two digit number to work on next so lets choose 23 our list so far looks as follows: 1 23 Replace the 3 with 5. Our newly constructed number is 95. Move down another row pick another arbitrary natural number, we'll need one that is at least 3 digits wide or more, lets pick 3476 just for fun. Here's our new list 1 23 3476 Now we need to replace the 7 with something other than 7, let's choose 8. Our new number is now 958, and so on. So we currently have a list of natural numbers 1 23 3476 And thus far we've created a "new number" 958 that isn't on this list. And we can continue down the list like this just like Cantor and end up with precisely the same situation he has. (i.e. we can create a supposedly "new" natural number that isn't already on the list of numbers that we have created in this way) Does that mean that we can create a new Natural Number that isn't already on the list of Natural Numbers? And that the Natural Numbers must then be "uncountably infinite" just like the Reals? This so-called "proof" doesn't prove anything. In fact, if it proves anything at all it proves that the Natural Numbers must have the same weird cardinality as the reals because we can use the very same process as Cantor used to prove it for the Natural Numbers too. So how are we any further ahead toward proving anything unique?
No. If you do that same prace on the natural numbers then you get a number which extends indefenitely to the left. For example ....999999999. This is NOT a natural number, so this doesn't apply. (instead, it's a so called p-adic number, Cantors diagonalization shows that the p-adics are not countable).

The difference with Cantor diagonalization on the reals is that you end up with a number which extends indefinitely after the decimal point. This IS a real number.

 Quote by micromass Moderator note: This thread will only deal with the rigorous version of Cantor's proof which is found in post 24 or in any serious set theory book.
Awww, I was getting so close to this:

If there are as many rows (real numbers) as there are columns then you can construct the diagonal number which is not in any row, hence the contradiction that shows that this cannot be the case.

If there are more rows (real numbers) than there are columns (natural numbers) then... we don't need to construct anything - this is exactly what we are trying to prove!

 Quote by Leucippus Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number".
Yes, that is how proofs generally work.

 Quote by micromass This thread is going off-topic. Therefore: Moderator note: This thread will only deal with Cantor's diagonalization proof. The invalidity of infinity and real numbers will be considered off-topic and the post will be deleted. If you want to discuss this topic, create a new thread.
With all due respect doesn't this seem to be a bit restrictive?

You just asked me yourself, "What process?? Do you mean taking the limit?? The limit of rational numbers doesn't need to be rational."

A question like that demands addressing the very concept of LIMIT.

You, as a mathematician, should be fully aware that the LIMIT process of calculus does not prove the existence of what the limit equals. On the contrary all that is required to prove a limit is that certain trends and conditions have been proven. The actual result (i.e. the number that the limit is equal to) cannot be said to necessarily "exist".

Surely you're aware of this. You can prove that a "limit exists" for functions where the value of the limit is undefined and therefore in terms of the "function" itself that point does not exist.

So a taking any process to a limit does not imply that the result has any actual "existence".

That may seem to have nothing to do with Cantor's diagonalization proof, but it's very much a part of it. Cantor is claiming that because he can take something to a limit that necessarily proves that the thing the limit is pointing too exists.

That's actually a false use of Limits anyway.

The epsilon-delta definition of limits won't even support any such conclusions.

So is that "off-topic" or is it required information concerning the proof in question?

The proof basically demands that something has been taken to a limit.

So how could that topic not be part of the proof?

 Furthermore, since informal arguments are clearly not convincing. Moderator note: This thread will only deal with the rigorous version of Cantor's proof which is found in post 24 or in any serious set theory book.
Well, I've already voiced my views on this.

If an informal intuitive or graphical argument can be shown to trump a mathematical axiom, then which should be accepted as being more reasonable?

Actually if you demand that we stick solely to the axioms of set theory then how could we ever show that they are flawed? They would necessarily contain those flaws.

Finally, and very sincerely,...

If you don't feel that this forum is the proper venue for fleshing out these kinds of ideas, then may I ask if you can point to an appropriate forum or web site where an intuitive approach to reason is deemed acceptable to discuss.

It not my intent to step on anyone's toes.

But I seriously would like to flesh out these ideas with people who are at least intelligent and professional enough to be capable of comprehending the points I'm attempting to address.

Clearly since these are concerns associated with mathematical formalism, it only makes sense to discuss them with people who at least have some understanding of mathematics.

But it seems to be rather fruitless if they are just going to demand that the status quo cannot be challenged without first accepting the very axioms that are in question.

Where can I propose ideas like these without having them immediately dismissed simply because they are indeed challenging sacred axioms?

Or has mathematics become a religion where any suggestion that its axioms might contain flaws is considered totally unacceptable blaspheme?

You can't very well use a formal axiomatic system to disprove itself.

If there are "flaws" in the formal system they must necessarily be address from an external intuitive approach.

That's my position on that.

So can you suggest a web site math forum where intuitive reasoning has not yet been cast asunder as being totally worthless?

Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus
 Quote by Leucippus With all due respect doesn't this seem to be a bit restrictive? You just asked me yourself, "What process?? Do you mean taking the limit?? The limit of rational numbers doesn't need to be rational." A question like that demands addressing the very concept of LIMIT. You, as a mathematician, should be fully aware that the LIMIT process of calculus does not prove the existence of what the limit equals. On the contrary all that is required to prove a limit is that certain trends and conditions have been proven. The actual result (i.e. the number that the limit is equal to) cannot be said to necessarily "exist". Surely you're aware of this. You can prove that a "limit exists" for functions where the value of the limit is undefined and therefore in terms of the "function" itself that point does not exist. So a taking any process to a limit does not imply that the result has any actual "existence". That may seem to have nothing to do with Cantor's diagonalization proof, but it's very much a part of it. Cantor is claiming that because he can take something to a limit that necessarily proves that the thing the limit is pointing too exists. That's actually a false use of Limits anyway. The epsilon-delta definition of limits won't even support any such conclusions. So is that "off-topic" or is it required information concerning the proof in question? The proof basically demands that something has been taken to a limit. So how could that topic not be part of the proof?
There is indeed one place that you need limits, and this is in the decimal expansion of a number. Given a sequence of numbers (between 0 and 9) $(x_1,x_2,x_3,...)$, then it always induces a real number $x_1\frac{1}{10}+x_2\frac{1}{10^2}+x_3\frac{1}{10^3}+...$. If you want to discuss this, then it is possible in this thread, but the discussion will need to be formal.

 Well, I've already voiced my views on this. If an informal intuitive or graphical argument can be shown to trump a mathematical axiom, then which should be accepted as being more reasonable? Actually if you demand that we stick solely to the axioms of set theory then how could we ever show that they are flawed? They would necessarily contain those flaws. Finally, and very sincerely,... If you don't feel that this forum is the proper venue for fleshing out these kinds of ideas, then may I ask if you can point to an appropriate forum or web site where an intuitive approach to reason is deemed acceptable to discuss. It not my intent to step on anyone's toes. But I seriously would like to flesh out these ideas with people who are at least intelligent and professional enough to be capable of comprehending the points I'm attempting to address. Clearly since these are concerns associated with mathematical formalism, it only makes sense to discuss them with people who at least have some understanding of mathematics. But it seems to be rather fruitless if they are just going to demand that the status quo cannot be challenged without first accepting the very axioms that are in question. Where can I propose ideas like these without having them immediately dismissed simply because they are indeed challenging sacred axioms? Or has mathematics become a religion where any suggestion that its axioms might contain flaws is considered totally unacceptable blaspheme? You can't very well use a formal axiomatic system to disprove itself. If there are "flaws" in the formal system they must necessarily be address from an external intuitive approach. That's my position on that. So can you suggest a web site math forum where intuitive reasoning has not yet been cast asunder as being totally worthless?
The Cantor diagonalization theorem states precisely that: under the given axioms of set theory, it is not true that the reals are countable. So in order to accept Cantor's theorem, it is necessary to accept the axioms. If you don't accept the axioms, then of course the theorem may be false!!

This thread will deal with the theorem that states: under the given axioms of set theory, it is not true that the reals are countable. So in this thread we will accept the currect axiom system and deduce Cantor's theorem. This thread will not be used to question the axioms.

If you want to challenge the axioms, you are free to do so in another thread.

Recognitions:
Gold Member
 Quote by Leucippus But it seems to be rather fruitless if they are just going to demand that the status quo cannot be challenged without first accepting the very axioms that are in question. Where can I propose ideas like these without having them immediately dismissed simply because they are indeed challenging sacred axioms? Or has mathematics become a religion where any suggestion that its axioms might contain flaws is considered totally unacceptable blaspheme?
Dude, get off your pedestal. It's not that you can not question math here, you're just wrong in this case.

 Quote by Jorriss Dude, get off your pedestal. It's not that you can not question math here, you're just wrong in this case.
Well no need to claim that I'm on a 'pedestal'.

I agree that I was wrong.

How's that?

I AGREEnow that Cantor's proof is restricted by the the assumption of these axioms (although in truth, those axioms weren't in place in Cantor's day). They actually evolved out of the original intuitive work of Cantor. And this contributed to them becoming the formalized axioms that they have become today.

Let's not forgot that there didn't even exist any such things as a formal set theory until the turn of the 20th century and Cantor's ideas played a very large role in that development.

I have serious concerns with the whole development of set theory from that time period forward.

And of course my ideas are necessarily going to need to be based on intuitive ideas in order to address these concerns. How could they be anything other than this? That can't very well be based on formally accepted axioms that haven't yet been written.

Blog Entries: 8
Recognitions:
Gold Member