Cantor's Diagonalization Proof of the uncountability of the real numbersby Leucippus Tags: cantor, diagonalization, numbers, proof, real, uncountability 

#19
Feb612, 01:53 PM

P: 39

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. 



#20
Feb612, 02:00 PM

P: 799

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 47th 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 nth item on the list in the nth decimal place. (Or binary place if you do the proof in base2). 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. 



#21
Feb612, 02:19 PM

P: 159





#22
Feb612, 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* 



#23
Feb612, 02:46 PM

P: 39

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? 



#24
Feb612, 02:57 PM

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



#25
Feb612, 03:43 PM

P: 159

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. 



#26
Feb612, 03:50 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,895





#27
Feb612, 03:57 PM

Mentor
P: 16,690

You have to make a fundamental distinction in mathematics between a rigorous formal argument and "nice ways of thinking about it". A pure formal argument uses axioms and inference rules, nothing else. It is often a very abstract argument, but it is always completely correct. An illustration or a picture are NOT valid proofs. They're ok to form your intuition, but you have to realize that they are NOT proofs. Realizing what a valid proof is, is very fundamental in mathematics. 



#28
Feb612, 03:58 PM

P: 39

I am not refuting the ultimate conclusion that reals are uncountable. I am totally convinced that the real numbers cannot be placed into a onetoone correspondence with the natural numbers. I'm not questioning that at all. I'm addressing only what I set out to address: Cantor's Diagonalization Proof. It is indeed a graphical proof, based on listing numerals and running a diagonal line through them. This is how Cantor originally proposed it, and it is the specific proof that I'm interested in addressing. ~~~~ I'll take a look at the formal abstract proof you offered too, and comment on that proof later. But that's really not what I'm addressing. I'm not concerned with proving or disproving the countability of the reals in general. All I'm concerned with is whether Cantor's Diagonalization proof is valid. That's what I'm looking at, and that's what I'm addressing specifically. I'm addressing the validity of this specific proof. I'm not challenging the results of the proof in general, or whether the reals are uncountable. I'm more interested in methods of proofs, than in what they are trying to prove. And this is what led me to finding the flaw in this particular proof. So it is this specific method of proof that I'm addressing. And the flaws associated specifically with it. ~~~~ I've recently watched a course by the Teaching Company Course on Great theorems. I was able to follow all of the theorems and proofs without a hitch until it came to this proof by Cantor. As I tried to better understand it I actually realized why it doesn't prove anything. The ultimate conclusions may very well be true coincidentally. But this diagonalization method (as it was presented in this course) is not a valid proof. It fails for the reasons I've already stated in previous posts. I don't understand why people think this is a valid proof? It would require that numerical lists of numbers are square, but they aren't. 



#29
Feb612, 04:01 PM

Mentor
P: 16,690

Notice that how Cantor originally proposed the proof is irrelevant, mathematics has changed a lot in 100 years. The abstract proof I just gave IS commonly known NOW as Cantor diagonalization. The "graphical proof" is not valid these days. 



#30
Feb612, 04:40 PM

P: 1,351

For the proof, it's only necessary that for each number N, there's an N'th row, and there's an N'th column. Since both the number of rows and the number of columns is infinite, this is obviously true, so it's always possible to find the N'th number of the diagonal and change it. Since this works for all N, we can find the complete diagonal. 



#31
Feb612, 04:42 PM

P: 39

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 interlibrary loan. So I would disagree with you that it's not a valid concern today. Seems to me that all you're basically suggesting is that it's irrelevant if I might have found a flaw in Cantor's original proof. I personally don't think that's irrelevant at all. Like I say. I'll look into the proof you provided and see if I can relate it back to Cantor's original idea. 



#32
Feb612, 04:52 PM

Mentor
P: 16,690

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



#33
Feb612, 04:54 PM

P: 39

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" infinitybyinfinity list is indeed the folly. That's the false assumption right there that can't hold true. 



#34
Feb612, 05:05 PM

P: 39

I wasn't aware the proof was considered to be wrong. I only wish the people who teach these things would be more clear about that. Then I wouldn't need to go around making myself look like an idiot proclaiming to have discovered things that everyone else already knows. 



#35
Feb612, 05:19 PM

P: 1,351





#36
Feb612, 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 