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

Leucippus

Quote by Preno

Well, you haven't demonstrated it, you just provided some sort of intuitive graphical argument, but other than that - that's precisely what Cantor was attempting to show. Cantor's theorem, phrased in your terms, states: there is no square list of real numbers. This is what both you and Cantor are saying.

But I have demonstrated it. You claim that I just provided some sort of intuitive graphical argument. But that is precisely what Cantor's diagonal proof is. It's a graphical argument based on using a numerical representation of numbers.

I'm demonstrating (using precisely the same kind of numerical graphical representations of numbers) why Cantor's graphical diagonalization proof has no merit.

And my points should indeed be extremely easy to intuitively understand.

Let me try to make this as clear as possible using a numerical representation of the natural numbers based on 10.

Let's start with the simplest case and expand on this and see where it leads,...

Here's the simplest case of a 1-digit wide list of number based on ten digits. There are exactly ten of them so in order to list them all the list must be 1 column wide by 10 rows long.

This is an extremely rectangular list of numbers, necessarily so, forced by the very nature of this numerical representation.

Now, let's move on to a 2-digit complete list of these numbers. And it's important that these list are indeed complete. Incomplete lists would be incomplete and therefore meaningless.

Now the list has become even vastly more rectangular. Now it has only 2 columns, but it requires a length of almost a hundred rows. It is an extremely skinny tall rectangle, force by the very nature of the numerical representation of these numbers.

Let's do it one more time just to be sure that we have a convincing trend,...

Yep the trend is pretty convincing. Now we have a list only 3 digits wide yet it's almost a thousand rows long. In fact, it doesn't take a genius to realize that these lists are going to continue getting longer by powers of ten every time we increase their width by a single digit.

So it should be pretty obvious that lists of natural numbers are innately far longer than they are wide.

Therefore to think that we should be able to draw a diagonal line down through a list of numbers represented by these numerical digits and proclaim to have created a new number "that isn't already on the list" is basically a false claim that could never hold true.

Yet this is precisely what Cantor's diagonal proof requires that we must be able to do. We must be able to go down through such a list of number diagonally and actually "reach" the bottom of the list creating a new number in the process, in order to concluded that we have created a new number that isn't already on this list.

That makes absolutely no sense. Cantor is assuming that these lists could somehow be square enabling him to successfully cross over every number on the list diagonally.

That simply isn't possible.

Cantor's diaganoalization proof based on this method is necessarily a flawed proof and doesn't prove what he claims it proves.

It's pretty obvious to me.

~~~~

This isn't to say that the result is necessarily untrue. Maybe the real numbers truly are uncountable. But Cantor's diagonalization "proof" most certainly doesn't prove that this is the case.

It is necessarily a flawed proof based on the erroneous assumption that his diagonal line could have a steep enough slope to actually make it to the bottom of such a list of numerals. That simply isn't possible.

I don't care if he claims to take this out to infinity. How would that change anything? The slope of his diagonal line is only going to get shallower and shallower with ever digit he crosses out. He could never hope to claim to have reached the bottom of the list and created a new number that isn't already on the list.

It's nonsense. What else can I say?

Leucippus

Quote by Deveno

you don't seem to grasp a key point. the numbers listed are not just rational numbers. the vast majority of them (as it turns out) are aperiodic non-terminating decimals.

if we stop the process after 3 steps, all we have is a decimal representation that differs from the first 3 numbers. if we continue, then after n steps, we just have a decimal that is different from the first n numbers listed.

now, if the real numbers between 0 and 1 COULD be put in a 1-1 correspondence with the natural numbers, at some finite time, we would reach any given real number. that is what it means to be "countable" (eventually you can "count up" to any given element of the set).

but the ever-increasing number we are creating at the bottom, doesn't match any number reached after a finite number of steps. so no matter how long we "count" (how far down the list we go), let's say we go down 3 million places, the number at the bottom is different from the first 3 million numbers.

you could write a computer program, that checked the number at the bottom against the first k numbers at step k, and if it found a match within the first k, instruct it to halt. it will never halt.

if the real numbers between 0 and 1 WERE countable, eventually, at some point, we would find a match, because at some point, we'd get to any real number we cared to name. but the way we are constructing the number (it grows by one digit, as we eliminate the possible matches from the "top down"), it's guaranteed not to match as many numbers as it has digits.

no match = not countable. and we're rigging it so there won't BE a match. which number on the list can it possibly match? the 1st? no. the 2nd? no. the 3rd? no. the 4th? no. the 3,567,281st? no.

all our number on the bottom has to do, to "not match" is be different in ONE digit-place from any given number. how do you think that will fail to happen?

With all due respect Deveno, your argument here makes no sense to me at all.

Why would you expect to ever get a number that's already on the list that you are generating?

That would never happen in this process. That's obvious.

But that doesn't prove anything in light of my observations.

You're always going to be generating a number that is "further down" the list than where you are currently working. That's a given. Even my finite examples clearly show that this will always be the case. The very process that is being used to generate your "new number" demands that this be the case.

My point is that it doesn't matter.

Numerical representations of numbers like this simply aren't square to begin with. So just because the new number you've created isn't on the list above where you are currently working in this process doesn't mean a thing.

That's my whole POINT.

The numbers above where you are working cannot be a "complete list" with respect to where you are at in the columns, because the slope of the diagonal line simply isn't steep enough to make that guarantee.

And this is why this diagonal method can't prove what Cantor claims it proves.

This diagonal method of creating a "new number" simply isn't anywhere near "fast enough" (i.e. it doesn't have a steep enough slope) to even deal with finite lists of numbers. It will always be "behind" the list. And it just gets further and further behind with every digit that is crossed out.

We can clearly see this in the finite examples I've given.

Why should this change if we try to take this process out to infinity?

The situation is only going to get worse with ever digit we cross out.

SteveL27

Quote by Leucippus

That would never happen in this process. That's obvious.

Leu, one point of confusion here is that you are thinking of Cantor's proof as a process. You are adding one row at a time and looking at the antigiagonal and then talking about rectangles.

All of that is erroneous thinking and has nothing to do with Cantor's proof.

Cantor asks us to consider any complete list of real numbers. Such a list is infinite, and we conceptualize it as a function that maps a number, such as 47, to the 47-th element on the list. There's a first element, a 2nd element, and DOT DOT DOT. We assume that ALL of these list entries exist, all at once.

Then we construct the antidiagonal. It's clear that the antidiagonal can't be on the list ... because it differs from the n-th item on the list in the n-th decimal place. (Or binary place if you do the proof in base-2).

Since we started by assuming we had a list of all reals; and we just showed that any such list must necessarily be missing a real; then it follows that there can be no such complete list in the first place.

I suggest that you make an attempt to fully understand this beautiful proof on its own terms. There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself.

Preno

Quote by Leucippus

But I have demonstrated it. You claim that I just provided some sort of intuitive graphical argument. But that is precisely what Cantor's diagonal proof is. It's a graphical argument based on using a numerical representation of numbers.

Um, no, it's not a "graphical argument", it is (or can be made into) a precise formal argument.

I'm demonstrating (using precisely the same kind of numerical graphical representations of numbers) why Cantor's graphical diagonalization proof has no merit.

No, you are demonstrating why it's impossible for a list of numbers (finite or infinite) to be square. That's exactly what Cantor is saying. That is literally the content of his theorem: the width of the list (the cardinality of the naturals) is less than the height of the list (the cardinality of the reals). You are literally repeating Cantor's theorem while at the same time claiming you're denying it. Jesus Christ.

Preno

A: Let us prove that 2 is irrational. We use proof by contradiction. Thus, suppose that 2 is the ratio of two integers..."

B: But 2 is not a ratio of two integers! We can prove it's not."

A: Um, yeah, that's what I'm trying to prove, using the method of contradiction. Again, suppose that 2 is the ratio of two integers..."

B: But it's not! Your theorem is false."

A: *facepalm*

Leucippus

Quote by SteveL27

Leu, one point of confusion here is that you are thinking of Cantor's proof as a process. You are adding one row at a time and looking at the antigiagonal and then talking about rectangles.

All of that is erroneous thinking and has nothing to do with Cantor's proof.

Cantor asks us to consider any complete list of real numbers. Such a list is infinite, and we conceptualize it as a function that maps a number, such as 47, to the 47-th element on the list. There's a first element, a 2nd element, and DOT DOT DOT. We assume that ALL of these list entries exist, all at once.

Then we construct the antidiagonal. It's clear that the antidiagonal can't be on the list ... because it differs from the n-th item on the list in the n-th decimal place. (Or binary place if you do the proof in base-2).

Since we started by assuming we had a list of all reals; and we just showed that any such list must necessarily be missing a real; then it follows that there can be no such complete list in the first place.

I suggest that you make an attempt to fully understand this beautiful proof on its own terms. There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself.

"There is nothing here about processes and nothing here about rectangles. You are introducing those irrelevant concepts on your own and losing sight of the proof itself."

I disagree. Cantor is using a numerical presentation of numbers and crossing them out using a diagonal line.

My observations of why this cannot be used in the way he is using it are valid observations, IMHO.

You can't just tell me to ignore the very things that Cantor's proof rely upon.

As far thinking of the thing as a "process", that too is irrelevant. It doesn't matter whether it's thought of as a process, or as some sort of miraculous completed object.

The slope of the diagonal line is too shallow to prove what Cantor claims to have proved in either case.

Trying to imagine a "Completed infinite process" isn't going to help. If you're imagining that you could have actually made it to the bottom of any list at all, then you are imagining something that simply won't work in this situation.

The innate rectangular nature of numerical systems of representation cannot be ignored either. In fact, if you are ignoring that, it's no wonder the proof appears to be so beautiful to you. You're just wrongfully assuming that such a list could be square and that a diagonal line could traverse the whole list from top to bottom.

You absolutely need to realize that it makes no sense to think of lists of numbers in that way before you can even begin to see why this proof cannot hold.

Recognizing the innate rectangular nature of numerical representations of numbers is paramount to understanding why this proof has no validity and cannot work.

Pretending that such lists could be square is the only thing that 'saves' the proof.

Why would I want to pretend that such lists could be square?

~~~~

So basically you're telling me that if I ignore that numerical lists are innately rectangular, and pretend that they are square, I too could see the "beauty" of Cantor's proof?

Well, I guess so.

But that's not reality, so why should I go there?

micromass

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.

Preno

Quote by micromass

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.

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.

HallsofIvy

Quote by Preno

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.

micromass

Quote by Preno

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.

Leucippus

Quote by micromass

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.

micromass

Quote by Leucippus

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.

willem2

Quote by Leucippus

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.

Leucippus

Quote by micromass

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

Quote by Leucippus

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?

Leucippus

Quote by willem2

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

Quote by micromass

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.

Similar Threads for: Cantor's Diagonalization Proof of the uncountability of the real numbers
Thread	Forum	Replies
Use Cantor's Diagonalization on the set of Natural Numbers?	Calculus & Beyond Homework	8
Cantor diagonalization argument	Set Theory, Logic, Probability, Statistics	2
Cantor's diagonalization	Calculus & Beyond Homework	5
A new point of view on Cantor's diagonalization arguments	General Physics	177
A question on Cantor's second diagonalization argument	General Math	36

Preno	A: Let us prove that 2 is irrational. We use proof by contradiction. Thus, suppose that 2 is the ratio of two integers..." B: But 2 is not a ratio of two integers! We can prove it's not." A: Um, yeah, that's what I'm trying to prove, using the method of contradiction. Again, suppose that 2 is the ratio of two integers..." B: But it's not! Your theorem is false." A: facepalm