Hi Exapno,
Yep, it’s only correct to talk about infinity as an approached limit or a potential. But what do those ellipses in the diagonal proof represent?
That the sequence never ends.
You need to be more specific and precise. k is the number of decimal places in what? n is the number of naturals “produced” by what? (And why are we bothering to think about the number of naturals produced by anything?) What is y?
Ah, okay. I think I see what your reasoning is. You’re thinking of the diagonal as a finite, “physical” thing that must span the entire “table” in order to be able to use it to construct a number that is not in the table. So for example, if you decided to construct a finite table in which 10 natural numbers indexed 10 sequences of digits, but the sequences only had 5 digits, you’re saying that we couldn’t use the diagonal to construct a sequence guaranteed to not be in the last five rows of the table.
That’s correct, but it has no real relevance to the problem at hand. Your discussion of “max x” and “max y” in the context of Cantor’s diagonalization makes no sense. For simplicity, let’s just say that every sequence of digits mapped by the function we’re discussing has an infinite number of digits. There’s no problem because for whatever row k we pick, we can always consider the kth digit in the sequence in row k.
So, when constructing our sequence S(L), we specify that its kth digit is different from the kth digit of L(k). This means that, no matter which row k you choose in the table, S(L) differs from it at least in the kth digit.
But remember that the table is just a visualization aid. What we’re really talking about is a function L that maps natural numbers to potentially infinite sequences of digits. So what we’re really saying is that no matter what k you choose to plug into L, the sequence S(L) differs from L(k) at least in the kth digit.
This doesn’t make sense either. As I said, the “number of digits” in each sequence mapped by this function we’re discussing can be infinite. It doesn’t have any relation to what particular number k the sequence is mapped to.
This is not correct. We’re just talking about infinite sequences of digits here. Any given infinite sequence can be placed into one-to-one correspondence with the natural numbers. We’ll map 1 to the first digit in the sequence, 2 to the second digit, 3 to the third, and so on.
k doesn’t “reach” infinity. The ellipses mean that the mapping represented by the table is not finite, and thus the table representing it could be carried to infinity.
Again, why are you talking about “squares” and “tables” and “diagonals?” These things are just visualizations. They don’t have to actually exist in order for the proof to work, and obviously they are not helping you understand the proof, since you keep getting hung up on the idea of infinity being “reachable” or something like that.
Ok.
Do you know what a natural number is? It sounds like your terminology is a bit off. A natural number is a finite number like 0, 1, 2, 3, 4, and so on.
A natural number is not the same thing as a countably-long sequence of digits. I assume you meant, instead of “n = the number of naturals produced”, instead “n = the number of countably-long digit-sequences produced”.
It sounds like you’re saying there is some finite number of decimal places and some finite number of sequences in the “square”. That’s why you shouldn’t think of things in terms of squares, cause it’s fucking you up. You shouldn’t even think of things in terms of sequences, cause they’re fucking you up too.
Remember, in standard mathematical terminology, when we say “countably-long sequence/list of _s”, all we mean is “Some rule for taking in a natural number index as input and spitting out a corresponding _ as output”. For example, a countably-long sequence like <0, 1, 0, 1, 0, 1, 0, 1…> really means, as far as we’re concerned, the rule “Take in a natural number as input. If it’s even, output 0. If it’s odd, output 1”. Similarly, a countably-long sequence like <0, 1, 4, 9, 16, 25, …> really means, as far as we’re concerned, a rule like “Take in a natural number as input. Return its square as output.”
We may use such language as seems to indicate that the entire sequence already lies written out in front of us, but this language doesn’t really mean anything and you don’t have to take it literally if your mind rejects such perspective. Remember, all we mean is that there is some rule by which we can ask “What should go at index #so-and-so?” and get back an answer “Such-and-such goes there”.
Note, also, that these sequences have no last element. If you can ask “What goes at index #k?”, then you can also ask “What goes at index #(k+1)?” There’s always a higher index. There’s always a next thing in the sequence. There’s no last element. The sequence does not have a finite length.
Now, in Cantor’s proof, we start with a countably-long list of countably-long sequences of digits. What does this mean? Remember, “countably-long list/sequence of _s” just means “Some rule for taking in natural numbers as input and outputting _s”. So don’t think of this as a square, since that visualization is fucking you up badly. This is just “Some rule for taking in natural numbers as input and outputting (some new rule, which describes how to take in natural numbers as input and ouput some digit)”. In more standard terms, perhaps terms familiar to you from programming, this is just “A function from natural numbers to (functions from natural numbers to digits)”.
Let’s return to what you said:
It sounds like you are assuming there is some fixed finite length k for all our digit-sequences and some fixed finite length n for our list of digit-sequences. But remember, there isn’t. These sequences do not have a finite length. In fact, it’s best not to think of them as lists or sequences or a square or any such thing as all, like I said, because that keeps fucking you up. Don’t fuck yourself up. Remember, all we’re actually talking about is a function from natural numbers to (functions from natural numbers to digits). Let’s call this function L.
It looks like you want “n” to mean “What’s the largest input I can give as an index to the function L?”. But there is no largest such input; like we said, for any input you give, you can always give another input one bigger, (or two bigger, or three bigger, and so on). So this is misguided.
Similarly, it looks like you want “k” to mean “What’s the largest input I can give as an index to the functions which are produced as outputs of the function L?”. But, again, there is no largest such input; like we said, for any input you give, you can always give another bigger one. So this is misguided as well.
The things you are trying to define “k” and “n” to mean do not make sense, at least not in the manner you’re thinking. There is no “k”. There is no “n”.
There is no “max y”; there is no “max x”. All the functions we are concerned with, there’s no maximum input you can give them; for any input you can give them, you can always also give them an input bigger by one. Asking about “max x” is like asking “What’s the bigger natural number?”. There’s no biggest natural number. You can always go bigger. You can always add one.
There is a correspondence in the sense that these inputs are the same kinds of things; L is a function from natural numbers to (functions from natural numbers to digits), so both L and all the outputs of L are functions which take in natural numbers. This is the correspondence that matters. But there is no “max y” and there is no “max x”.
There is no “k”, there is no “n”, there is no “max y”, and there is no “max x”. Remember, you are utterly misguided in thinking there are such things. Asking about “max x” is like asking “What’s the bigger natural number?”. There’s no biggest natural number. You can always go bigger. You can always add one.
There’s no such thing as k. The correspondence is in the sense that both L and the outputs of L are functions which take the same kinds of things as input: they both take natural numbers as input. But there’s no such thing as k and there’s no such thing as n and so there’s no question of whether k and n are equal.
There’s no such thing as k, which makes this question very misguided. You needn’t think there’s even any table or square; those are just visualization devices to help you grasp something which they are instead, clearly, blocking you from grasping.
Remember, even though people speak of a big square of digits, they don’t, as far as you’re concerned, mean that literally. What they mean is “Some rule which, if you give it a natural number as input, produces as output some new rule which, if you give a natural number as input, produces as output some digit”. People bring up the square because they like to visualize the first input here as a row number and the second input here as a column number and the elements of the square as the final outputs. For many people, this metaphor works well; for you, it works terribly, and so you shouldn’t use it. Just think about what they really mean instead, a function from natural numbers to (functions from natural numbers to digits). This is exactly the sort of thing that we were talking about with the Bob-Cantor game [well, with colors instead of digits, but it makes no difference]. If you agree that Cantor wins the Bob-Cantor game, then you agree to what, ultimately, all the mathematicians actually really mean by Cantor’s proof. You just think they mean something else, something inchoate and misguided.
I’ve requoted the most important thing for you to acknowledge, adhay. Read everything Stealth Potato and I wrote, but if you still want to argue, first read these two paragraphs over and over again, making sure to actually absorb what’s in the bolded bits.
Some confusion caused by misunderstanding (I think) of random vs. not. Even the fully countable set of rational numbers cannot be list in order, but that doesn’t mean any listing is random. Quite the contrary. For example the positive rationals can be listed as 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, … The list is in the order first of the sum of numerator and denominator and, within a given sum, in order of incresing numerator. Certainly non-random, but certainly not in numerical order.
Now as Cap’n Ridley said, there is no 1-1 correspolndence between a set and its set of subsets. This fact is as true for finite sets as for infinite sets. And ultimately means that you cannot form the set of all sets that are not elements of themselves, which is another version of Cantor’s diagonal argument. (In most set theories you cannot form the set of all sets, but there are some strange versions of set theory in which you can. But then you cannot use all predicates to carve out subsets, such as the predicate “not a member of itself”. And some of these exotic set theories allow a set to be a member of itself. The set x = {x} is perfectly acceptable in non-well-founded set theory.)
Another point I wanted to make is that if you think it is hard to multiply 2pi, try pipi or .9898… times itself (ignoring the fact that it is rational). But mathematicians have proved that it can be done, although it is hard. The process ultimately converges. But infinite decimals are not the only or the best way to define real numbers. In many ways, the simplest is the one as Cauchy sequences, but I don’t find that in wiki and it is too long to explain here.
It’s here.
Maybe adhay is an intuitionist. Adherents of intuitionism reject the reality of uncountable infinite sets. No joke. It is my understanding that intuitionists also don’t like proof by contradiction, but I couldn’t find anything about that on the linked webpage.
I don’t mean to presuppose anything here. It’s hard to tell, adhay, if you object only to Cantor’s diagonal method of proof (and that you do in fact believe that the real numbers are uncountable), or if you actually take issue with the statement that the reals are uncountable.
If the only thing you have a problem with is the diagonal method of proof, well several others here have done a wonderful (and I must say, correct) job of trying to convince you. You should know that there is a constructive proof (that is, one that does not make use of the method of proof by contradiction) from topology that proves the uncountability of the reals. It’s deeper and more complicated, but maybe you would appreciate this proof better: Every nonempty compact Hausdorff space with no isolated points is uncountable. It does depend on the completeness axiom, though, and it sounds to me that you might very well have a problem with that.
If you don’t believe that there is a set that is uncountable, then it sounds like you really are an intuitionist. While they must be a tiny minority among working mathematicians, apparently there are some real mathematicians out there–not cranks at all–that have objections to infinities like the ones you have raised here. The link above talks about this, scroll down to “Intuitionism and infinity.”
I thought I’d throw that out there, because it’s interesting to me. I accept Cantor’s proof with no problem, and so do most undergraduate students taking real analysis and topology for the first time. I’m just sayin’ not everyone does!
Cantor’s theorem is constructive as well; it constructs, from any function from X to 2^X, an element of 2^X not in X. [By 2^X, I mean the collection of functions from X to bits]. There is no need to view it as a proof by contradiction, even though it is often presented this way.
At any rate, it is often mis-stated that intuitionists do not accept proof by contradiction. In modern-day formal intuitionistic logic a la Heyting, intuitionists do accept proofs by contradiction in the sense that they will admit that a proof of a contradiction from the supposition A yields a proof of NOT A. What they really do not accept is double negation elimination; they do not accept that NOT NOT A should necessarily imply A. And so if you prove a contradiction from the supposition NOT A, you have a valid intuitionistic proof, just one of NOT NOT A, instead of A.
Even intuitionistically, Cantor’s theorem remains valid. And so, even in intuitionistic logic, there can be no surjection from X onto 2^X, nor onto the powerset of X [which is generally different from 2^X intuitionistically]. In fact, Cantor’s Theorem remains true in systems much, much weaker than standard impredicative intuitionistic higher-order logic; such is the logic of particular special mathematical structures called topoi, but Cantor’s Theorem actually holds in a much wider class of mathematical structures; to wit, it holds in any category with finite products, which is pretty much the minimal structure requisite for even stating the theorem.
All that having been said, it is consistent, in intuitionistic logic, for there to be a surjection from the naturals onto the reals (suitably formalized)… but A) this is only possible because it is intuitionistically consistent for there to be no surjection from the reals onto the powerset of the naturals and B) even intuitionistically, it’s not consistent for there to be a bijection between the naturals and the reals.
There are also predicative constructive set theories in which all collections called “sets” admit a surjection from the naturals onto them. But even here Cantor’s theorem continues to hold; it just happens to demonstrate, in such theories, that there is no “set” which contains all the functions from naturals to bits. [This was also, to some extent, the view of Brouwer, although this, like many other aspects of his informal views, does not make itself felt in the formalized intuitionism of his student Heyting]
Summary: Even intuitionists and constructivists of other flavors must accept Cantor’s theorem as fully as anyone else. They just may draw different implications from it. But the core issue under discussion [that there can be no surjection from naturals to the functions from naturals to bits] is inarguable.
Incidentally, that’s why throughout this discussion, I haven’t wanted to talk about real numbers, and have wanted to talk about digit-sequences/functions from naturals to digits instead. For the latter is what Cantor’s theorem is really directly about, and carrying the result over to the former requires methods both irrelevant to this discussion and of much more limited applicability (i.e., “non-constructive” techniques which cannot be employed in intuitionistic contexts).
(It’s also intuitionistically consistent for there to be a surjection from a subset of the naturals to the functions from all naturals to bits. But it’s not possible for that subset to be all of the naturals, because of Cantor’s Theorem.)
Well, thank you all. I’m sure it’s been every bit as frustrating talking to me as talking to someone standing on his own foot and complaining about the pain.
I do accept the idea that between any two consecutive natural numbers there exists an infinity of reals which is of the same cardinality of the infinity between two natural numbers which are not consecutive. This is why we can limit our inquiry to the range of 0 to 1.
I understand now (correct me me briefly if I’m wrong) that all Cantor is saying that if you assume you could contstruct a one-to-one mapping of the naturals to the reals, you’d discover that you couldn’t. Amen to that.
After a little more reasearch on the net, I find that this is not the first forum to host my argument which was best expressed in post #79. There are others but see Bush's new Moon-Mars initiative . There was another I saw and can’t locate now in which one of the participants cited the very website I did in post #39 with much the same response I received here. After checking out the author of this site, I blush.
Finally, check out The Crackpot Offer — LessWrong. I can relate.
Again, thanks for your patience.