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

  • Thread starter Leucippus
  • Start date
  • #26
HallsofIvy
Science Advisor
Homework Helper
41,833
956
I disagree. Personally, I've never thought of Cantor's argument in terms of squares and rectangles previously but I do find it to be a rather nice way of thinking about it. Cantor's diagonal proof is precisely proof of the fact that the rectangles never become squares. That's just a very straightforward reformulation of Cantor's point - the rectangle is as wide as N and as high as R.
No, it isn't. The whole point of Cantor's argument is that this list doesn't exist to begin with!

The only thing that's bizarre here is that Leucippus for some reason doesn't seem to understand that showing that an assumption cannot hold is precisely what you're supposed to do in a proof by contradiction.
 
  • #27
22,089
3,286
I disagree. Personally, I've never thought of Cantor's argument in terms of squares and rectangles previously but I do find it to be a rather nice way of thinking about it. Cantor's diagonal proof is precisely proof of the fact that the rectangles never become squares. That's just a very straightforward reformulation of Cantor's point - the rectangle is as wide as N and as high as R.

The only thing that's bizarre here is that Leucippus for some reason doesn't seem to understand that showing that an assumption cannot hold is precisely what you're supposed to do in a proof by contradiction.
I agree that it's a rather nice way of thinking about it. But it's not rigorous.

You have to make a fundamental distinction in mathematics between a rigorous formal argument and "nice ways of thinking about it".

A pure formal argument uses axioms and inference rules, nothing else. It is often a very abstract argument, but it is always completely correct.

An illustration or a picture are NOT valid proofs. They're ok to form your intuition, but you have to realize that they are NOT proofs.

Realizing what a valid proof is, is very fundamental in mathematics.
 
  • #28
39
1
Cantor's argument has NOTHING to do with squares and rectangles. I know that there are often fancy pictures of squares in books, but those are ILLUSTRATIONS of the argument. The real formal argument is indisputable.

I'll number the steps so you can specifically say where you disagree.

Here is the formal argument:
1) Assume that ]0,1[ is countable, then we can write [itex]]0,1[=\{x_1,x_2,x_3,x_4,...\}[/itex].

2) Every number has a decimal expansion. So we can write [itex]x_i=x_i^1\frac{1}{10}+x_i^2\frac{1}{10^2}+...+x_i^n\frac{1}{10^n}+...[/itex].

3) Put [itex]y_n=x_n^n[/itex] for all n. Put [itex]z_n=4[/itex] if [itex]y_n=5[/itex] and put [itex]z_n=5[/itex] otherwise.

4) Put [itex]z=z_1\frac{1}{10}+z_2\frac{1}{10^2}+...+z_n\frac{1}{10^n}+...[/itex].

5) Notice that [itex]z_n[/itex] does not equal [itex]x_n^n[/itex] for all n. We can use this to prove that z does not equal any [itex]x_n[/itex]. (I won't write this proof down. If the problem is here then you should say so and I will write the explicit proof down of this fact).

This argument is the pure formal argument. You should find a mistake in this proof, not in the illustration of the proof.
Hello, Micromass.

I am not refuting the ultimate conclusion that reals are uncountable.

I am totally convinced that the real numbers cannot be placed into a one-to-one correspondence with the natural numbers. I'm not questioning that at all.

I'm addressing only what I set out to address: Cantor's Diagonalization Proof.

It is indeed a graphical proof, based on listing numerals and running a diagonal line through them. This is how Cantor originally proposed it, and it is the specific proof that I'm interested in addressing.

~~~~

I'll take a look at the formal abstract proof you offered too, and comment on that proof later. But that's really not what I'm addressing. I'm not concerned with proving or disproving the countability of the reals in general.

All I'm concerned with is whether Cantor's Diagonalization proof is valid. That's what I'm looking at, and that's what I'm addressing specifically.

I'm addressing the validity of this specific proof.

I'm not challenging the results of the proof in general, or whether the reals are uncountable.

I'm more interested in methods of proofs, than in what they are trying to prove. And this is what led me to finding the flaw in this particular proof.

So it is this specific method of proof that I'm addressing. And the flaws associated specifically with it.

~~~~

I've recently watched a course by the Teaching Company Course on Great theorems. I was able to follow all of the theorems and proofs without a hitch until it came to this proof by Cantor. As I tried to better understand it I actually realized why it doesn't prove anything.

The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.
 
  • #29
22,089
3,286
Hello, Micromass.

I am not refuting the ultimate conclusion that reals are uncountable.

I am totally convinced that the real numbers cannot be placed into a one-to-one correspondence with the natural numbers. I'm not questioning that at all.

I'm addressing only what I set out to address: Cantor's Diagonalization Proof.

It is indeed a graphical proof, based on listing numerals and running a diagonal line through them. This is how Cantor originally proposed it, and it is the specific proof that I'm interested in addressing.

~~~~

I'll take a look at the formal abstract proof you offered too, and comment on that proof later. But that's really not what I'm addressing. I'm not concerned with proving or disproving the countability of the reals in general.

All I'm concerned with is whether Cantor's Diagonalization proof is valid. That's what I'm looking at, and that's what I'm addressing specifically.

I'm addressing the validity of this specific proof.

I'm not challenging the results of the proof in general, or whether the reals are uncountable.

I'm more interested in methods of proofs, than in what they are trying to prove. And this is what led me to finding the flaw in this particular proof.

So it is this specific method of proof that I'm addressing. And the flaws associated specifically with it.

~~~~

I've recently watched a course by the Teaching Company Course on Great theorems. I was able to follow all of the theorems and proofs without a hitch until it came to this proof by Cantor. As I tried to better understand it I actually realized why it doesn't prove anything.

The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.
IF you're talking about the graphical proof, then it is not a valid proof. Proofs should never be graphical.

Notice that how Cantor originally proposed the proof is irrelevant, mathematics has changed a lot in 100 years.

The abstract proof I just gave IS commonly known NOW as Cantor diagonalization. The "graphical proof" is not valid these days.
 
  • #30
1,973
264
The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof?

It would require that numerical lists of numbers are square, but they aren't.
I don't understand this at all. The proposed list will have an countably infinite number of reals, and each real will have an countably infinite number of digits (adding an infinite number of zero's if necessary).

For the proof, it's only necessary that for each number N, there's an N'th row, and there's an N'th column. Since both the number of rows and the number of columns is infinite, this is obviously true, so it's always possible to find the N'th number of the diagonal and change it. Since this works for all N, we can find the complete diagonal.
 
  • #31
39
1
IF you're talking about the graphical proof, then it is not a valid proof. Proofs should never be graphical.
That's certainly a controversial statement. I just finished taking a course on "The Shape of Nature" which is a cutting-edge course on Topology by Professor Satyan L. Devadoss of Williams College. He not only enthusiastically supports graphical proofs, but he even cites one that he personally introduced into mathematics and he suggests that it could not be stated any other way than graphically. But then again, he addresses topology which is clearly different from set theory concepts.

Here's a link to his course if you would like to watch it.

The Shape of Nature

By the way, you don't need to buy it. Usually you can get it through inter-library loan.

Notice that how Cantor originally proposed the proof is irrelevant, mathematics has changed a lot in 100 years.

The abstract proof I just gave IS commonly known NOW as Cantor diagonalization. The "graphical proof" is not valid these days.
His diagonalization proof is still being presented to people and taught to people in many math courses and books today. If it's a flawed proof then that flaw should be addressed and exposed.

So I would disagree with you that it's not a valid concern today.

Seems to me that all you're basically suggesting is that it's irrelevant if I might have found a flaw in Cantor's original proof. I personally don't think that's irrelevant at all.

Like I say. I'll look into the proof you provided and see if I can relate it back to Cantor's original idea.
 
  • #32
22,089
3,286
That's certainly a controversial statement.
It's not a controversial statement at all. The idea of what a proof is and is not, is very well established. If you study mathematical logic, then you see that mathematicians have a very very very precise idea of what a proof really is.

That said, the formal logical proof is often to hard to comprehend. So that is why people make illustrations to proofs, and formulate proofs to make them easier. It is important to know that that is NOT what the proof is. It's like somebody pointing to the moon and the people are all looking at the finger. The logical proof is what mathematics is all about.


but he even cites one that he personally introduced into mathematics and he suggests that it could not be stated any other way than graphically.
THAT is the controversial statement. If a proof can only be stated graphically, then it's wrong. Period.

But then again, he addresses topology which is clearly different from set theory concepts.
Topology is not different from set theoretic concepts. Topology is well-established and formalized. All proofs in topology can be expressed in formal form.

His diagonalization proof is still being presented to people and taught to people in many math courses and books today. If it's a flawed proof then that flaw should be addressed and exposed.
His diagonalization is being presented to people today. But those people usually KNOW that the graphical proof is not the proof itself. When I first saw Cantor diagonalization, I realized very well that one should formalize the proof and write it in formal statements.

When they first showed me that [itex]A\cap (B\cup C)=(A\cap B)\cup (A\cap C)[/itex] using a picture, it was IMMEDIATELY made clear that this was not a valid proof. It simply SUGGESTS a valid proof.

So I would disagree with you that it's not a valid concern today.
Well, you got your answer: the proof is wrong. Is there anything else you would like to discuss?
 
  • #33
39
1
I don't understand this at all. The proposed list will have an countably infinite number of reals, and each real will have an countably infinite number of digits (adding an infinite number of zero's if necessary).

For the proof, it's only necessary that for each number N, there's an N'th row, and there's an N'th column. Since both the number of rows and the number of columns is infinite, this is obviously true, so it's always possible to find the N'th number of the diagonal and change it. Since this works for all N, we can find the complete diagonal.
Yes, I understand what you are saying. But aren't you completely tossing out everything that I had previously pointed out?

You're basically assuming a "square" situation.

You're basically saying that since it's infinitely many rows and infinitely many columns that somehow makes it doable or even "square" in the sense that it's infinity by infinity in dimension.

But you're not taking into account the observations I've given. That lists of numbers represented by numerals cannot be made into 'square' lists. Pretending that "infinity by infinity" represents a square list that can be completed is the folly.

You'd also have to ignore the limitations on the slope of any line that needs to go down these lists crossing out a digit at time.

The slope of that line cannot be made steep enough to keep up with a list that would be required to represent even the natural numbers let alone the reals.

The very assumption that this problem can be viewed as a "square" infinity-by-infinity list is indeed the folly.

That's the false assumption right there that can't hold true.
 
  • #34
39
1
Well, you got your answer: the proof is wrong. Is there anything else you would like to discuss?
No, I guess I'm done here then.

I wasn't aware the proof was considered to be wrong.

I only wish the people who teach these things would be more clear about that.

Then I wouldn't need to go around making myself look like an idiot proclaiming to have discovered things that everyone else already knows.
 
  • #35
1,973
264
Yes, I understand what you are saying. But aren't you completely tossing out everything that I had previously pointed out?

You're basically assuming a "square" situation.
The term square or rectangle makes no sense at all for an array of numbers that's infinite in 2 dimensions. Both are countably infinite, and thats ALL you can say.

But you're not taking into account the observations I've given. That lists of numbers represented by numerals cannot be made into 'square' lists. Pretending that "infinity by infinity" represents a square list that can be completed is the folly.
I'll agree with you that the lists cannot be made into square lists, but that's just because an infinite square list is nonsense. But you don't need that. All you need is to be able to extend the diagonal arbitrarily far.

You'd also have to ignore the limitations on the slope of any line that needs to go down these lists crossing out a digit at time.

The slope of that line cannot be made steep enough to keep up with a list that would be required to represent even the natural numbers let alone the reals.
Note that an infinite list of numbers with an infinite number of digits only has a corner at (1,1) (the first digit of the first number). It does NOT have an opposite corner with the diagonal running between those corners. The diagonal does just fine with a slope of 1.
 
  • #36
39
1
Thank you for sharing your views Willem, but as Micromass points out, this historical "proof" doesn't have the mathematical rigor worth arguing over. It wouldn't be accepted as a valid "proof" today precisely because the type of issues that I've brought up (and the types of issues that you offer in return). This "proof" cannot be made rigorous enough to settle these concerns in a clear and definitive way.

I guess Micromass has a point. It just doesn't measure up to the rigor required of modern mathematics.

I most certainly will agree with that observation.
 
  • #37
22,089
3,286
This "proof" cannot be made rigorous enough to settle these concerns in a clear and definitive way.
That's not at all what I said!! The proof CAN be made rigorous and I have done so in one of the above posts!!

The original Cantor proof is not a proof by itself, but it merely suggests a proof. Once you rigorize the proof (like I have done), it becomes perfectly valid.
 
  • #38
39
1
That's not at all what I said!! The proof CAN be made rigorous and I have done so in one of the above posts!!

The original Cantor proof is not a proof by itself, but it merely suggests a proof. Once you rigorize the proof (like I have done), it becomes perfectly valid.
It can't possibly be the very same proof. Because I've already shown why the graphic proof must necessarily be invalid.

Or to put that another way. If it is the exact same proof then it must also be flawed in a similar way.
 
  • #39
22,089
3,286
It can't possibly be the very same proof. Because I've already shown why the graphic proof must necessarily be invalid.

Or to put that another way. If it is the exact same proof then it must also be flawed in a similar way.
It IS the exact same proof.

So please, show me where my rigorous proof is flawed.
 
  • #40
39
1
It IS the exact same proof.

So please, show me where my rigorous proof is flawed.
I'm looking in to. It might take a while to figure out where the flaw is hiding.

After all, look where it was hiding in Cantor's graphical proof.

You would never see it easily from the presentation of the proof itself. Who would think to list numeral representations of numbers and recognize that they necessarily form taller and taller rectangles? And then attempt to draw diagonal lines over them to create new numbers that aren't on the list? And that this would result in diagonal lines that are constantly getting shallower in slope with every new digit you create. And that every number you create would already be on the lists further down where your diagonal line can't reach.

Hey that was by no means obvious.

If there is a similar flaw in your formal proof it may very well be hiding in the form of some assumption that isn't blatantly apparent in the actual proof itself.

Finally, I confess that I am rusty at this. I haven't worked with this stuff for a while. I used to be really good at it back in my college days, but that was eons ago. So it's going to take me a while to figure out what your formal proof is actually trying to say.

This could take some time, so don't expect a quick response on this. But I'm definitely going to look into it. I might be back later requesting the rest of your proof. Or more details.

In the meantime it's going to take me a while just to orient myself to your proof. I haven't been working on it tonight at all. I have a headache right now and quite frankly I don't want to think about things like this at the moment. But I'll get back to you on it for sure.

Leave the thread open, and I'll be back. But it might be a few days. So carry on with with your normal activities in the meantime.

If it truly is the same proof it should contain the same flaw somehow.
 
  • #41
22,089
3,286
I'm looking in to. It might take a while to figure out where the flaw is hiding.

After all, look where it was hiding in Cantor's graphical proof.

You would never see it easily from the presentation of the proof itself. Who would think to list numeral representations of numbers and recognize that they necessarily form taller and taller rectangles? And then attempt to draw diagonal lines over them to create new numbers that aren't on the list? And that this would result in diagonal lines that are constantly getting shallower in slope with every new digit you create. And that every number you create would already be on the lists further down where your diagonal line can't reach.

Hey that was by no means obvious.

If there is a similar flaw in your formal proof it may very well be hiding in the form of some assumption that isn't blatantly apparent in the actual proof itself.

Finally, I confess that I am rusty at this. I haven't worked with this stuff for a while. I used to be really good at it back in my college days, but that was eons ago. So it's going to take me a while to figure out what your formal proof is actually trying to say.

This could take some time, so don't expect a quick response on this. But I'm definitely going to look into it. I might be back later requesting the rest of your proof. Or more details.

In the meantime it's going to take me a while just to orient myself to your proof. I haven't been working on it tonight at all. I have a headache right now and quite frankly I don't want to think about things like this at the moment. But I'll get back to you on it for sure.

Leave the thread open, and I'll be back. But it might be a few days. So carry on with with your normal activities in the meantime.

If it truly is the same proof it should contain the same flaw somehow.
Just a question. You DO acknowledge that 100% of all the mathematicians find Cantor's proof to be correct??

(Correct in the sense that the intuitive graphical proof can be rigorized in a completely correct proof)
 
  • #42
pbuk
Science Advisor
Gold Member
1,627
546
The list is square.

How many columns does it have? Each column can be 'labelled' with a unique integer, so there are as many columns as there are integers.

How many rows does it have? Each row can be labelled with a unique rational number, so there are as many rows as there are rational numbers. But we already know that there are as many rational numbers as there are integers so there are as many rows as there are integers, so there are as many rows as there are columns.

I agree that it is counter-intuitive that the limit of a list which appears to get more and more 'un-square' is square, but that is just one of the strange properties of infinite sets.
 
  • #43
39
1
Just a question. You DO acknowledge that 100% of all the mathematicians find Cantor's proof to be correct??

(Correct in the sense that the intuitive graphical proof can be rigorized in a completely correct proof)
I'll believe that when someone publishes a graphic diagram showing precisely how the formal proof relates back to the graphic proof in detail.

After all, if a direct correspondence can be made then such a diagram should be easy to construct.

I'm going to attempt to do that very thing with the proof that you gave me.

I confess that I'm a very visually-oriented thinker. I always have been and it's actually paid off highly for me. Although my expertise was in physics not pure mathematics. So I'm used to working with applied mathematics.

In fact, way back when I was in high school I was great in simple mathematics (i.e. geometry, trig, etc.) until I hit algebra. Then I totally lost it. I couldn't deal with axioms without physical analogies.

I gave up on math. I went into electronics. Well duh? Guess what? Electronics is riddled with algebra. But keep guessing,.... it was EASY! It was simple. It was a piece of cake because I could see how the physical quantities that are being quantified related to one another. I totally understood algebra and why it is the way it is. From there I went back to college and studied physics and algebra and calculus was a breeze.

But I confess that when it comes to understanding things based on pure axioms and rules it just makes my head spin even today.

So I'll be tearing your proof apart and making analogies in my own mind with Cantor's Diagonal proof. If I can match this up, I'll have a good chance at being able to show where there is a flawed assumption. --- Because I already know what the problem is with Cantor's graphical proof.

If there truly is a direct correspondence between the proof you gave me, and Cantor's Graphic Proof, then that very same issue must STILL BE THERE. How could it go away?

So I'm looking forward to seeing how this formal proof fits back onto Cantor's Diagaonalization Proof.

It should be able to fit if it's representing the very same ideas.

And if it can't be made to fit, then I question that it's truly the same proof.
 
  • #44
22,089
3,286
I agree that it is counter-intuitive that the limit of a list which appears to get more and more 'un-square' is square, but that is just one of the strange properties of infinite sets.
A quite similar "paradox" is in the theory of supertasks.

Let's say I have three boxes A, B and C. The boxes B and C are empty and the box A contains countable many elements numbered by 1,2,3,4,5,..
First I take the balls 1 and 2 out of A and I put them into B.
Then I take ball 1 out of B and put it into C.

Secondly, I take the balls 3 and 4 out of A and I put them into B.
Then I take ball 2 out of B and put it into C.

Thirdly, I take balls 5 and 6 out of A and I put them into B.
Then I take ball 3 out of B and put it into C.

So at every step, I pick the two balls of A with the lowest number and put them into B. Then I take a ball with the lowest number of B and put it into C.


So, actually, after every step, the box B contains one more ball then before the step. So I actually always put one ball into B.

Surprisingly, if I do this process to the "limit" (so if I do it until A is empty), then I get that B will also empty.

Indeed, let's say that B contains ball with number n. But this cannot be, because at step n I took out the ball with number n!!!!!

So even though I always fill up B, in the end B turns out to be empty!!!


These are the paradoxes that arise with infinity. The OP's argument with squares and rectangles is ALSO a paradox, but the truth is that in the end you DO end up with a square.

Human beings have very little and very wrong intuitions about infinity. When dealing with infinity, one should NEVER trust on intuition but rather on logical formal arguments.
 
  • #45
pbuk
Science Advisor
Gold Member
1,627
546
Alternatively...

In base 10, the list with n columns has 10n rows.

So to determine the number of rows in the list with an infinite number of columns we need to multiply 10 by itself an infinite number of times. Will we get an answer that is larger than the number of columns? No, it is the same so the list is square.
 
  • #46
pbuk
Science Advisor
Gold Member
1,627
546
Alternatively...

The list is a rectangle with sides ∞ and 10. This list is non-square if and only if ∞≠10.
 
  • #47
22,089
3,286
Alternatively...

The list is a rectangle with sides ∞ and 10. This list is non-square if and only if ∞≠10.
Note that mathematicians write [itex]\aleph_0[/itex] instead of [itex]\infty[/itex] in these cases.
 
  • #48
pbuk
Science Advisor
Gold Member
1,627
546
To take it a bit further, if we are looking to present Cantor's original proof in a way which is more obviously 'square', simply use columns of width 1/2n and rows of height 1/10n. The whole table will then exactly fill a unit square. Within it, the 'diagonal' will be composed of line segments with ever-decreasing (but non-zero) gradients, and ever decreasing (but non-zero) lengths.

This can be the form of a 'graphical proof', if you want to call it that.

Edit:
Actually I think the rows need to be 1/20n high with an extra 0.05 units added to the first row
 
Last edited:
  • #49
pbuk
Science Advisor
Gold Member
1,627
546
Note that mathematicians write [itex]\aleph_0[/itex] instead of [itex]\infty[/itex] in these cases.
I am a mathematician (of sorts), but I am trying to present an argument to someone who isn't in terms that he seems to understand.
 
  • #50
22,089
3,286
I am a mathematician (of sorts), but I am trying to present an argument to someone who isn't in terms that he seems to understand.
I wasn't calling you out!! I see in your posts that you have experience with these things. I just wanted to introduce the [itex]\aleph[/itex] notation to the interedted reader following this thread (if there is somebody like this). :smile:
 

Related Threads on Cantor's Diagonalization Proof of the uncountability of the real numbers

  • Last Post
3
Replies
62
Views
5K
Replies
9
Views
3K
  • Last Post
4
Replies
86
Views
4K
  • Last Post
Replies
4
Views
1K
Replies
43
Views
906
  • Last Post
2
Replies
49
Views
9K
  • Last Post
Replies
17
Views
843
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
38
Views
9K
Top