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

[Leucippus]

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.

 

[micromass]

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 A\cap (B\cup C)=(A\cap B)\cup (A\cap C) 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?

 

[Leucippus]

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.

 

[Leucippus]

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.

 

[willem2]

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 that's 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.

 

[Leucippus]

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.

 

[micromass]

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.

 

[Leucippus]

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.

 

[micromass]

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.

 

[Leucippus]

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.

 

[micromass]

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)

 

[pbuk]

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.

 

[Leucippus]

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.

 

[micromass]

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.

 

[pbuk]

Alternatively...

In base 10, the list with n columns has 10ⁿ 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.

 

[pbuk]

Alternatively...

The list is a rectangle with sides ∞ and 10^∞. This list is non-square if and only if ∞≠10^∞.

 

[micromass]

Alternatively...

The list is a rectangle with sides ∞ and 10^∞. This list is non-square if and only if ∞≠10^∞.

Note that mathematicians write \aleph_0 instead of \infty in these cases.

 

[pbuk]

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/2ⁿ and rows of height 1/10ⁿ. 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/20ⁿ high with an extra 0.05 units added to the first row

 

[pbuk]

Note that mathematicians write \aleph_0 instead of \infty 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.

 

[micromass]

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 \aleph notation to the interedted reader following this thread (if there is somebody like this).

 

[Leucippus]

A quite similar "paradox" is in the theory of supertasks.
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.

I absolutely agree with that because infinity is ultimately nothing more than an abstract mathematical concept.

There's really no reason to believe that mathematical infinities have anything at all to do with physical reality or the real world. So why should those abstract notions be intuitive?

I personally have reasons to disagree with many foundational concepts of set theory that actually cause all of these abstract multiple sized infinities. As far as I'm concerned these are all based on flawed logic that has unfortunately already been accepted into mathematical formalism mainly due to ideas introduced by Georg Cantor himself.

I am totally in agreement with the words of Henri Poincare they go something like this, forgive me if the quote is not precise as I am recalling it from memory but it goes something like this,...

"Georg Cantor's transfinite set theory is a disease from with future mathematics will someday be cured" - Henri Poincare

I'm in total agreement with Henri Poincare and I personally believe that at some point humans will fix this mistake.

I honestly believe that if aliens came here from another planet they would laugh at our notion of multiple sized infinities. It's simply an unnecessary and unrealistic concept. It's actually caused by the formal introduction of an "empty set" into set theory (which I believe was also the work of Cantor). It's simply an unnecessary concept. It's not needed.

All of these weird ideas have sprung from the formalization of set theory around the turn of the 20th century. Mathematics did fine without them for some 2000 prior to that. Including Newton and Leibniz invention of calculus.

In the meantime I believe that Henri Poincare's comments about Cantor's transfinite sets will indeed someday be 'cured'. They simply aren't required and they are basically nonsense.

It's no wonder they don't make intuitive sense. They truly are nonsense.

 

[pbuk]

So do you believe that a number exists that is 10x the largest number that exists? Or even one more than the largest number that exists? You don't need set theory to see that this cannot be true, and neither can it be true that your rectangle has more rows than it does columns.

 

[pbuk]

the interedted reader following this thread (if there is somebody like this).

rofl

 

[Leucippus]

Note that mathematicians write \aleph_0 instead of \infty in these cases.

I'm not even a mathematician and I knew that.

\aleph_0 is one of Cantor's transfinite cardinal numbers. And is basically used as a 'number' representing a completed infinite 'quantity'

Precisely what Henri Poincare warned Cantor not to do (i.e. not to think of infinity as a completed thing)

\infty This symbol is more representative of an infinite process and is used a lot in calculus limits, etc. which are indeed processes.

Henri Poincare would be far more approving of infinity thought of as an endless process.


I may not be a mathematician, but I'm not exactly ignorant of math either.

But right now I'm going to bed. (ha ha)

 

[micromass]

We all heard such quotes before. Earlier they might have said:

"Negative numbers is a disease from with future mathematics will someday be cured"

or

"Imaginary numbers is a disease from with future mathematics will someday be cured"

or

"Noneuclidean geometry is a disease from with future mathematics will someday be cured"

or

"Decimal notation is a disease from with future mathematics will someday be cured"

These statements are all quite incorrect. Negative numbers, imaginary numbers, noneuclidean geomety and transfinite numbers are ALL very useful concepts. They will NOT go away.

Transfinite numbers yield a perfectly consistent theory (in so far that the natural numbers are consistent), and they form a theory that are very applicable. They show up literally everywhere in mathematics.

Cantor's ideas were initially despides and Cantor ended up in a deep depression. People like Kronecker and Poincarre were (although they were very smart) ultimately conservative and did not foresee the huge successes in axiomatic set theory.

I understand you don't like it. But you have to realize that it will not go away because mathematicians like it. Transfinite numbers might be unintuitive, but they eventually are entirely logically sound.

I notice a trend. Initially an innovative new idea is always laughed at, then it is furiously attecked and in the end it is accepted as common sense. (somebody else said this, but I can't remember who). Right now, transfinite numbers ARE a common sense. Mathematics will not be cured from axiomatic set theory, and if they would remove axiomatic set theory from mathematics then they would rip out its very heart.

 

[pwsnafu]

Henri Poincare would be far more approving of infinity thought of as an endless process.

In that case Henri Poincare should not http://christianmarks.wordpress.com/2010/05/25/mathematical-logic-finds-unexpected-application-on-wall-street/.

 

[andrewr]

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 have this argument over aleph not occasionally with my brother who is a Mathematician, and he and I both have a problem with the "Axiom of Choice" as he calls it.
Let me ask a simple question, If I were to show you a way to count every possibly decimal representation as a unique list -- and that means as many digits as can be imagined (inductively given n digits, I will list n+1 as well...) What would it do to this silly argument?

I realize many people think it is impossible; but that is part of the point.
I believe it can be done -- is it sufficient to put a big !"?"! into the whole idea of Cantor's idea?

(I am serious... and this isn't a difficult proof.)

 

[micromass]

I have this argument over aleph not occasionally with my brother who is a Mathematician, and he and I both have a problem with the "Axiom of Choice" as he calls it.
Let me ask a simple question, If I were to show you a way to count every possibly decimal representation as a unique list -- and that means as many digits as can be imagined (inductively given n digits, I will list n+1 as well...) What would it do to this silly argument?

I realize many people think it is impossible; but that is part of the point.
I believe it can be done -- is it sufficient to put a big !"?"! into the whole idea of Cantor's idea?

(I am serious... and this isn't a difficult proof.)

I really don't understand what you're trying to say. The axiom of choice has nothing, absolutely nothing to do with Cantor's diagonalization.

 

[Deveno]

Leucippus, let me offer you a variant of Cantor's proof, that show that your consideration of "slope" is irrelevant:

we proceed as before, except, for our "diagonal number" we do THIS:

if the first digit of the first number is 1, we assign the diagonal number the first digit 2.

otherwise, we assign the first digit of the diagonal number to be 1.

the next 8 digits of the diagonal number shall be 1, regardless.

if the 10th digit of the second number is 1, we assign the diagonal number the 10th digit 2.

otherwise, we assign the number 1 to the 10th digit of the diagonal number.

the next 89 digits of the diagonal number are assigned the digit 1.

if the 100th digit of the third number is 1, we assign the digit 2 to the 100th digit of our diagonal number.

otherwise, we assign 1 to the 100th digit of our diagonal number.

we continue in this way.

now the "slope" is "even worse" the diagonal is not even as steep as before. nevertheless, no matter which n we pick, the diagonal number differs from the first n numbers in our list, so it differs from every number on our list (it differs from the k-th number in the 10^k-1-th digit).

@ micromass: i disagree with the contention that if a proof can only be demonstrated graphically, it isn't valid. for what is a formal system, if not a few squiggles on paper? is that not graphical? i don't know about you, but i read most of my mathematics.

more to the point: many proofs in algebraic topology or category theory amount to: diagram-chasing. the diagram IS the proof, in some cases. there's no logical reason why "pictures" can't be made every bit as unambiguous and consistent as well-formed formulas. constructing a length with a compass and straight-edge IS a proof of constructibility (a concept which can be expressed purely algebraically).

there is many people who think that a mathematical result "isn't true" until it is proven formalizable in (first- or second-) order logic in a formal language that has encoded the axioms of Zermelo-Frankel set theory. this is unfortunate.

 

[pbuk]

If I were to show you a way to count every possibly decimal representation as a unique list -- and that means as many digits as can be imagined (inductively given n digits, I will list n+1 as well...) What would it do to this silly argument?

Any countable list can be used as the start of Cantor's argument: simply construct a number whose nth digit is different from the nth number on the list for every n and you have a number that is not on the list.