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


by Leucippus
Tags: cantor, diagonalization, numbers, proof, real, uncountability
Leucippus
Leucippus is offline
#19
Feb6-12, 01:53 PM
P: 39
Quote Quote by Deveno View Post
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
SteveL27 is offline
#20
Feb6-12, 02:00 PM
P: 799
Quote Quote by Leucippus View Post

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
Preno is offline
#21
Feb6-12, 02:19 PM
P: 159
Quote Quote by Leucippus View Post
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
Preno is offline
#22
Feb6-12, 02:22 PM
P: 159
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
Leucippus is offline
#23
Feb6-12, 02:46 PM
P: 39
Quote Quote by SteveL27 View Post
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
micromass is offline
#24
Feb6-12, 02:57 PM
Mentor
micromass's Avatar
P: 16,690
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
Preno is offline
#25
Feb6-12, 03:43 PM
P: 159
Quote Quote by micromass View Post
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
HallsofIvy is online now
#26
Feb6-12, 03:50 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,895
Quote Quote by Preno View Post
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
micromass is offline
#27
Feb6-12, 03:57 PM
Mentor
micromass's Avatar
P: 16,690
Quote Quote by Preno View Post
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
Leucippus is offline
#28
Feb6-12, 03:58 PM
P: 39
Quote Quote by micromass View Post
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
micromass is offline
#29
Feb6-12, 04:01 PM
Mentor
micromass's Avatar
P: 16,690
Quote Quote by Leucippus View Post
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
willem2 is online now
#30
Feb6-12, 04:40 PM
P: 1,351
Quote Quote by Leucippus View Post
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
Leucippus is offline
#31
Feb6-12, 04:42 PM
P: 39
Quote Quote by micromass View Post
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
micromass is offline
#32
Feb6-12, 04:52 PM
Mentor
micromass's Avatar
P: 16,690
Quote Quote by Leucippus View Post
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
Leucippus is offline
#33
Feb6-12, 04:54 PM
P: 39
Quote Quote by willem2 View Post
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
Leucippus is offline
#34
Feb6-12, 05:05 PM
P: 39
Quote Quote by micromass View Post
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
willem2 is online now
#35
Feb6-12, 05:19 PM
P: 1,351
Quote Quote by Leucippus View Post
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.
Leucippus
Leucippus is offline
#36
Feb6-12, 05:57 PM
P: 39
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.


Register to reply

Related Discussions
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