This is a very strange criticism. Cantor’s proof sets out to show that this is impossible to do. So he certainly doesn’t base his proof on the idea that you can do so.
What he does do, though, is “assume” (in a loose sense) that you can do so, specifically for the purpose of showing that this assumption can’t actually hold. It’s a reductio argument. But “assuming” p for a reductio is by no means basing one’s proof on an assertion that p is the case! Almost exactly the opposite!
-FrL-
Certainly not. A diagonal line can be specified by a point and a slope.
-FrL-
You’re getting caught up on the common meaning of words that are being used to signify some mathematical jargon. I’ve already explained Cantor’s argument in detail, so please take a look at that.
With regards to the diagonal, what we’re really talking about is the diagonal of a countably infinite matrix. This is a perfectly well-defined mathematical object.
Not a good cite when discussing ianzin’s particular objection, since the definition it gives refers explicitly to two endpoints.
-FrL-
Damn, I didn’t even notice that. It’s still a matrix diagonal, but you have to use a more formal definition of a matrix (which I guess I mentally substituted there).
ianzin, are you a finitist, like Cantor’s arch-enemy Leopold Kronecker?
The point of Cantor’s proof is that, for any list of real numbers, there must be a real number that is not on the list. There’s nothing in it about constructing a list: rather, given any such list, it’s a way of constructing a number not on the list.
And by a “list” of elements, what is really meant is a one-to-one correspondence between those elements and the natural numbers.
I agree with ultrafilter that you look like you’re getting caught up on common meanings of words, like “diagonal.”
[QUOTE=Thudlow BoinkThe point of Cantor’s proof is that, for any list of real numbers, there must be a real number that is not on the list. There’s nothing in it about constructing a list: rather, given any such list, it’s a way of constructing a number not on the list.
[/QUOTE]
A finitist would not find this result suprising. “Any list” would include only finite lists, so of course there would be numbers not on the list.
I think the best way to put it when responding to a certain family of objections is as possible. The proof is that for any method for extending a list of real numbers indefinitely, there will always be a real number which will never show up on the extended list, no matter how far it has been extended. But importantly, this is not the case for the integers.
I think a finitist agrees that lists can be indefinitely extensible, even if never actually infinite.
-FrL-
If I’m reading this right, the diagonal technique is for rational numbers only (for which it works fine, just inefficiently). A transcendent number could be found too, with an infinite number of steps.
There was a class called “Comparative Infinities” that I didn’t get to take because I had requireds filling that time slot. Consoled myself with “Non-Euclidean Geometry.”
A cute thing that I guess the logic prof did to discourage us until we were higher level went like this:
Assume x=1+2+4+8+16+32+64+…
Then x=1+2(1+2+4+8+32+64+…)
Therefore
x=1+2x
The idea being that infinity is not entirely agreed upon yet. Heck, can anyone integrate 0/0?
And x=-1/2.
As soon as you tell me the last number of e. (Decimal base representation only, please.)
First of all, I have no idea what your bracketed term " (in a loose sense) " means, and I would love you to elucidate.
Secondly, I am well aware of what constitutes a reductio ad absurdum argument, and my view is that Cantor’s proof isn’t one, or at least not a valid one. A reductio ad absurdum argument shows that a sequence of legitimate steps or deductions leads to a contradicton. What I am discussing is the fact that Cantor’s famous proof involves an illegtimate step. Specifically, it asserts that, given an infinitely long list of numbers, one can construct a new number by taking the first digit of the first number, the second digit of the second number and so on. This sounds seductive and plausible, which is why is tends to pass without remark or objection. However, this procedure is only legitimate and meaningful for a finite list of numbers. If you are starting with a list of numbers that you assert has an infinite number of members, each of which can be expressed as an infinitely long decimal (hence the use of an ellipsis at the right-hand end of each number in Anne Neville’s list), then the procedure described is meaningless.
Cantor’s proof as it is traditionally presented uses an analogy in which the first part corresponds to easily understood, easily visualised everyday life, but the second part does not. This is where the illegitimate step creeps in, usually unnoticed. If you show me ten numbers written down as decimals, sure, I can note the first digit of the first number, the second digit of the second number, and so on for the complete list. This is something no-one has trouble either visualising or understanding. If one wants to, one can actually perform this task and, by altering each of the noted digits in some specific way (for example by adding 1), one can create an eleventh number that is distinct from each of the ten numbers originally on the list. Cantor’s proof, as traditionally presented, and as presented earlier by Anne Neville, just assumes that one can perform the same operation on an infinitely long list of infinitely long decimal expressions, and uses this step within a reductio ad absurdem argument. What I am saying is open to qurstion is whether this assumption holds. I maintain that it does not.
One cannot perform this operation (taking the first digit of the first number… and so forth) on an infinitely long list. One way to realise this is to appreciate that one cannot count along to the ‘infinity-th’ digit of an ‘infinitely’ long number. Infinity is not a term that refers to a location, either on a long decimal expression or in any other sense. It is the term we use to denote ‘non-finite’.
Another way to realise this is by reference to my earlier thought experiment about a diagonal line. On my list of ten numbers I can construct a diagonal line (passing through the nth digit of each of the countable numbers on the list), and if I want to I can rotate this diagonal line through 90 degress and tell you where the end points lie after this rotation. I cannot do this on Cantor’s list. On Cantor’s list, the ‘diagonal line’ cannot be created in the first place. If it were possible, Cantor would be able to rotate this line through 90 degrees and tell me where the end points or defining point now lie.
I believe I was referring to Cantor’s proof as it is traditionally presented, for example in Godel, Escher, Bach which happens to be where I first read about it over 25 years ago, and in Anne Neville’s earlier post. These presentations of the proof make no reference that I can find to ‘a point and a slope’.
Thank you for bothering to point this out so that I don’t have to.
Is addition of a number with an infinite decimal expansion meaningful? How?
To be more precise, Cantor’s proof refers to any complete list of real numbers. But if it is complete, one cannot then define a number that isn’t on it. If one can define a number that isn’t on it, then it isn’t complete.
You will be familiar with argument about what happens when an irresistible force meets and immovable object. The answer is that in any defined world or system, if the word ‘irresistible’ is meaningful then no object can be immovable, and vice-versa. So the question as posed contradicts itself and at least one of the constituent terms must be rendered void or meaningless. It’s the same with Cantor’s proof as typically presented in prose terms. Either ‘complete’ means something, or it doesn’t. If it means something, then one cannot use this term as part of a construction process that yields a number not on the list. If it does not mean something, then yielding a number that is not on the list is a trivial task that is of no importance (because the list was never said to be complete in the first place).
Your are aserting both that it is not about constructing a list and that it is about constructing a number not on the list. However, one can only define the latter (elements not on the list) if the list has previously been constructed.
What? No it doesn’t. I thought you said you understood r.a.a? Cantor assumes, for the sake of reductio, that his list is complete. He then constructs a new real that isn’t enumerated by the list, thus showing that his initial assumption, that the list is complete, is false.
This is true, and is exactly my point from above ianzin.
Let’s not confuse your criticism of the possibility of diagonalization with your criticism from the impossibility of a list of the real numbers. Here you purport to be defending the latter criticism, but you are actually defending the former.
Your latter criticism trivially fails to apply to Cantor, because Cantor does not assume the possibility of a list of the real numbers, but rather constructs the proof to show that it is false.
Here is why your diagonalization criticism fails. Here is what it is possible to do. Note that a real number can be thought of as an indefinitely extensible list of digits (though for most reals we don’t have a finite rule for extending that list). Now suppose we have specified a method for writing down a sequence of representations of real numbers. This is a method whose execution can never be actually completed, of course, but we can still give a method–one which makes it clear, given a coordinate, (here I’m thinking of the Cantor grid) what digit would be there. So then, given the existence of such a method, what is possible is to define a method for extending a particular list of digits indefinitely–namely the list of digits which are like this: for each slot in this list numbered m, the digit found there is identical to that found at coordinate [m, m], plus one. I can never finish writing this list, but you give me an m and I can tell you, in a finite amount of time, exactly what digit will be found at the mth place.
And since the digit at the mth place on this list (which is trivilly interpretable as a representation of a real number) at m will always differ from the digit on the grid at [m, m], it follows that the list is not the same as any row (or column) of the grid. Since the rows and the list represent real numbers, we can evaluate this conclusion as indicating that given any method for extending a list of real numbers indefinitely, it is always possible to define a real number (i.e. give a method for extending a list of single digits indefinitely) which would never appear on that list of real numbers no matter how long you went on writing it out. And importantly, what I just said is not true of lists of integers.
-FrL-
ianzin, I’m interested in seeing a response to post 20 above (some of which I repeat in my last post). Do you agree that what I claim is possible and impossible there are in fact possible and impossible? Do you agree that the claim I make there is equivalent to the claim proved by Cantor?
(Mathematicians here, I’m also interested to hear your view on the questions, esp. the latter. Am I making a mistake to think Cantor’s claim can be interpreted the way I’ve interpreted it?)
-FrL-
ianzin, I think that you are putting too much stock in the popularized version of Cantor’s proof that you read in Gödel, Escher, Bach. What GEB gives is perfectly fine, given that its constrained to use only concepts available to the lay reader. GEB takes certain formal concepts in mathematics, such as bijections, and “de-formalizes” them into more familiar concepts, such as lists. But these more familiar concepts are necessarily less precise. As they are given in popular accounts, they do not withstand the extremely rigorous scrutiny that you want to apply.
This means that, to subject the original argument to rigorous scrutiny, you are going to have to “re-formalize” the concept involved. My diagnosis of your doubt of the argument is that you are “re-formalizing” it in the wrong way. That is, you are not recovering the original formal argument as mathematicians understand it. Fortunately, ultrafilter already did the work of giving the true formal version of the argument in post #17. If you are going to accuse literally all professional mathematicians over the last century of being guilty of missing a simple mistake, you should level your criticisms at the actual argument, not at a less rigorous popularized version.
So I suggest that you pose your criticism in the context of the argument as ultrafilter gave it in post #17. If, for whatever reason, you can’t do that, then you are not really addressing Cantor’s proof.
I was under the impression that aleph[sub]0[/sub] was the cardinality of the set of rational numbers. Paging mathochist and other exotic-math experts…
The integers, naturals and rationals all have the same cardinality. By extension, any infinite set containing tuples of integers, naturals or rationals is countable as well.