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

[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.

 

[Jorriss]

This is kind of off topic but I'm curious why graphs can not be proofs (I have not taken a course on logic)?

 

[micromass]

more to the point: many proofs in algebraic topology or category theory amount to: diagram-chasing. the diagram IS the proof, in some cases.

A commutative diagram is not a proof. And many mistakes in category theory actually amount to misleading diagrams. A commutative diagram is a suggestion of a proof. It is merely an illustration.

If you look at Bourbaki, then they show that they treat commutative diagrams very rigorously. They try to prove everything with algebraic means.

To me, a proof is correct if it formilizable in some kind of logical system. You don't actually NEED to formalize it, but just giving a suggestion that it can be done is good enough.

 

[Hurkyl]

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

Ah joy, "completed infinity".

Just for your information, I have never encountered somebody who uses that terms that could give an even quasi-rigorous account of what the term means.

From observing people who use it, I quite honestly believe that it literally means "I am unwilling or unable to engage in one more layer of abstraction, and thus have failed to recognize that we're talking about the same idea." (I don't mean insult by this, except possibly in the 'unwilling' case)

 

[micromass]

This is kind of off topic but I'm curious why graphs can not be proofs (I have not taken a course on logic)?

Hmmm, I don't think I'm expressing myself clearly enough.

There are actually two kind of proofs: informal and formal proofs.

By the very definition, a proof is formal. A proof is defined as a sequence of logical algebraic steps. Each step follows from another step by applying an inference rule.

These things are the actual proofs. However, they are EXTREMELY hard to read. If all math books would consist out of formal proofs, then math books would be unreadable.

That's why we allow informal proofs. An informal proof presents people the basic ideas and reasoning of a proof. An informal proof suggests that the formal proof can be carried out if one would want to do so.

All textbooks contain informal proofs (and it's good that they do). Text books like to work with a lot of text and a lot of pictures to make it easier on the student. But one should always keep in mind that one should be able to formalize the proof.

And indeed, one can formalize all the proofs. An example is given by http://us.metamath.org/index.html which contains thousands of proofs including the celebrated Hahn-Banach theorem. This site shows what actual formal proofs look like. And as one can see, it is completely unreadable. (the site also shows formal proofs in plane geometry, including constructibility).

I am NOT advocating that everybody should be using formal proofs in journals or education. Quite the contrary. But the students should be well-aware that the formal proof can be carried it if one wants to do it.

 

[Jorriss]

Hmmm, I don't think I'm expressing myself clearly enough.

There are actually two kind of proofs: informal and formal proofs.

By the very definition, a proof is formal. A proof is defined as a sequence of logical algebraic steps. Each step follows from another step by applying an inference rule.

These things are the actual proofs. However, they are EXTREMELY hard to read. If all math books would consist out of formal proofs, then math books would be unreadable.

That's why we allow informal proofs. An informal proof presents people the basic ideas and reasoning of a proof. An informal proof suggests that the formal proof can be carried out if one would want to do so.

All textbooks contain informal proofs (and it's good that they do). Text books like to work with a lot of text and a lot of pictures to make it easier on the student. But one should always keep in mind that one should be able to formalize the proof.

And indeed, one can formalize all the proofs. An example is given by http://us.metamath.org/index.html which contains thousands of proofs including the celebrated Hahn-Banach theorem. This site shows what actual formal proofs look like. And as one can see, it is completely unreadable. (the site also shows formal proofs in plane geometry, including constructibility).

I am NOT advocating that everybody should be using formal proofs in journals or education. Quite the contrary. But the students should be well-aware that the formal proof can be carried it if one wants to do it.

I better see what you're getting at now. Thank you for clarifying.

 

[micromass]

I better see what you're getting at now. Thank you for clarifying.

Just to clarify it some more: if I see a graph somewhere which intuitively shows me something, then I will accept this as proof. Any mathematical journal (except logic-journals) will accept it as a valid proof. If you write it on the exam, then the professor will accept it as proof (except in a logic class). But it's not a formal proof in the strict sense of the word.

 

[Hurkyl]

mm: I think the point Deveno makes (and maybe that Jorriss is wondering about) is that proof theory can be cast in settings other than string processing.

For example, arithmetic expressions and equations in category theory are often presented in graphs.

In Categories, Allegories, Freyd introduces the idea of a Q-sequence (and a Q-tree) that consists of a path through a category and a sequence of quantifiers, which can replace the role of formulas.

Applied to the category of finitely-presented categories, he uses them to prove a metatheorem that an equivalence functor preserves and reflects a property if and only if it can be expressed on a blackboard.

 

[andrewr]

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.

IN my discussions of Aleph Not with my brother, the Axiom of choice does come up.
But, set that aside -- what I am saying is that I believe I can show an algorithm which will demonstratably count every possible decimal number in the decimal notation system, uniquely, and once.

eg: 1.01 will be counted exactly once, as will 2.01, 2.011, 2,0000001, etc.
I am not trained in formal mathematical proofs with respect to Aleph not, etc, so excuse my vagueness.
However, my understanding is that the Real numbers are representable by the decimal notation system; and that the "Ideal" representation of all real numbers is spanned by a mantissa and fraction portion that becomes more and more perfect as the number of digits in each is allowed to grow arbitrarily large.

If I were to demonstrate an algorithm which showed that all possible decimal numbers can be counted with a distinct index; say 'i' so that any imaginable real number would exist "somewhere" in a sequence defined by an index (i) which is an integer from 0 to as large as one likes. eg: every possible decimal number could be found by a static algorithm called f(i).

The only issue which would come up is the representation of 0.99999999... vs. 1.00000... and whether or not they are distinct numbers as i becomes arbitrarily large.

If I am following the argument correctly, Cantor appears to be claiming that such a unique counting is impossible. So if I gave a simple counter-example in decimal notation -- would such an algorithm be of use in this discussion?

 

[Hurkyl]

eg: 1.01 will be counted exactly once, as will 2.01, 2.011, 2,0000001, etc.

If I'm understanding what you describe, then you truly do generate a list containing every finite decimal, no matter how long. The set of terminating decimals is, indeed, countable.

The problem is that most real numbers don't have finite decimal representations. It sounds like you have a specific algorithm in mind; can you write down the first 10 or so numbers? After that, can you tell me at what place the number 1/9 appears?

 

[andrewr]

If I'm understanding what you describe, then you truly do generate a list containing every finite decimal, no matter how long. The set of terminating decimals is, indeed, countable.

The problem is that most real numbers don't have finite decimal representations. It sounds like you have a specific algorithm in mind; can you write down the first 10 or so numbers? After that, can you tell me at what place the number 1/9 appears?

Yes, and Yes, although your second question can't be written down inside a text terminal of this size. Representation of an integer is not the same as existence of that same integer.
There are many counting numbers which we know exist, but can't be written down inside a text terminal of this size.

You would agree, no doubt, that "0.999999999..." is a representation of a real number; and by the ellipsis I am suggesting a pattern for something which is much larger than I would like to write down, although I DO KNOW HOW to write it down -- eg: and that the representation improves in accuracy and may have a selectable accuracy for a given discussion or purpose.

The algorithm itself can be adapted for various constraints; eg: there are many such algorithms based on a similar methodology.

DO you care if I count only the positive reals, or do I need to include the negative as well?
etc.