I didn’t read the whole thing carefully, but this
is (a) wrong, and (b) reminds me of that “last time this sort of thing came up” that I mentioned earlier, in this thread, which you may find worth reading. The key point, though, is that something being possible does not imply that that something has a non-zero probability.
It’s crankery and bullshit: each of sections 2, 3, and 4 is fatally wrong.
In section 2, the author fails to comprehend the consequences of n being arbitrary; it has been shown that, for every value of n, the constructed sequence is not in the list at index #n, which is the same as to show that the sequence is not in the list at all.
In section 3, the author invokes probability without having actually specified a probability distribution. No matter; let us assume he means to show that a randomly constructed list contains all digit-sequences. The author states “The probability of any permutation of digits from 0 to 9 inclusive existing in a list of such permutations of digits is non-zero.” but gives no support for this claim. In fact, this claim is false, destroying his argument. (It is possible he came to this claim by conflating “impossible” with “has a probability of zero”; however, such a conflation would not fit with the standard formalization of probability, and would only be possible on an alternative account of probability which invalidates the fifth paragraph of his argument here)
In section 4, the author erroneously assumes that there is a correspondence between natural numbers and infinite sequences of digits; but, of course, the actual correspondence given by standard notation is only between natural numbers and finite strings of digits.
Right. I should have looked past the first two web definitions I found. Fair to say, Aleph-nought is not an integer.
I have to call it a night. I will spend some time looking at Bob’s game with adhay.
Thanks to all.
I think this guy is a crank.
In the second section of that page, after he summarizes Cantor’s proof and in which he presents a “simple argument” against it, he seems to be saying that because for any natural number n there are an infinite number of naturals larger than n, it is possible for entries in the hypothetical “table” beyond n to contain the number X which was constructed by selecting digits different from those on the diagonal. In fact it is impossible, because by the very definition of X, it differs in at least one digit from every real number in the table, including the infinity of reals that follow the index n, for whatever n you care to choose.
It’s a very simple constraint and it doesn’t stop applying just because it’s being applied to an infinitely long sequence. His argument is essentially like denying the possibility of defining an infinite sequence of ones because there are an infinite number of them and we can’t be sure that one of them isn’t really a two, or saying that .999… does not equal 1 because one of the nines between “.999” and infinity could somehow turn into an eight.
The next section is a hilarious probabilistic fallacy of the “make assumptions that feel intuitively right but actually have no basis in fact” variety. The final section is merely a demonstration that he doesn’t understand what a bijection from the naturals to the naturals requires, so he simply assumes that the same requirement holds as for a bijection from the naturals to the reals.
You may be right, it’s difficult for me to say. However, this thread reminds me of many threads I’ve read and participated in regarding the equality of .9999… and 1. It often seems as though people think, “The further you go out, the repeating 9s get closer and closer to 1, but never actually reach it”. This is their argument, not mine. It seems as though they’re imagining an ever lengthening stretch of "9"s; dynamically “growing”, not already “there”. This, along with a misunderstanding of how the decimal representations of real numbers are defined in the first place, seems to be what causes the confusion (though I can’t be absolutely sure; I can only read their words, not their minds).
And now to relate it back to this thread and the game between Bob and adhay: I have a suspicion that adhay may have a problem with the bolded part in this line:
I’m not saying it’s a valid problem with your game, but it may appear that way to him/her. I say this because of a previous quote from adhay (again, bolding the relevant part):
This is why I’m trying to stress the idea that, for the sake of Cantor’s proof and adhay’s understanding, it’s perfectly OK to pretend/hypothesize/assume that the “list” (i.e., the bijection between the naturals and reals) already exists. None of the proof hinges in any way on how this list/bijection is created or came to be, or if it could be created in a finite length of time or whatever. The strength in the proof lies in the logical contradiction that its very existence creates in the first place.
In any finite (representable) realm where n is the number of decimal places, b the base and N the highest counter (always less than Aleph-nought), there is no bijection between the reals and naturals. How could there be? There are n columns and N=b^n rows and a corner-to-corner “diagonal” is inconceivable and, of course, you could always add another decimal place. It gets more and more obvious as n approaches Aleph-nought and N approaches b^Aleph-nought. However, in a REAL sense, ALL the reals ARE represented to n decimal places. In that sense only, there is a bijection between the reals and the naturals.
It is when the table is imagined to have “instantaneously” been completed and is somehow now a square with an actual diagonal that my imagination fails.
My problem exactly. I envision a pay rate of $1000/Aleph-nought/second (or hour or year). I’m as well paid writing here.
I have done some computer programming and am quite aware that the problem concerning the equality of 1 and .9999 … is simply one of representation.
With all due respect, one could just as easily hypothesize the existence of unicorns.
If your representation only has n digits, then not all the reals will be represented – in fact, there are infinitely many reals that map to any single one of your representations, so you don’t, in fact, have a bijection between the reals and the naturals, but only a bijection between the naturals and a subset of the reals, which isn’t any more useful for proving statements about the reals than a bijection between the naturals and the naturals would be.
Let’s say the list is taken to 2 decimal places.
0 .00
1 .01
2 .02
…
98 .98
99 .99
.01 represents (to n places) the complete range of .01000000 … to .01999999 … and
.99 represents .990000000 … to .999999999 …
What happens when n somehow reaches Aleph-nought is beyond imagination.
There is no surjective mapping from a set to it’s power set.
What is the problem here? Why do you keep talking about the table, when it’s been explained repeatedly that the proof of the above statement doesn’t rely on any imaginary table?
Quite true in the finite realm. .01 only represents .019999 … and so is not a true mapping. But there is no reason (imo) to think this holds beyond the finite realm.
I think that the distinction between “reals” and “naturals” is an artifact of finite conception applied inappropriately to the infinite.
Of course you could; that’s the power of proof by contradiction. The piece that you are missing is that if, by hypothesizing the existence of unicorns, you can establish a logical contradiction, then you have demonstrated that such a unicorn can not possibly exist.
Perhaps I should have said that not all the reals are uniquely represented. The problem is that this representation is in itself a non-surjective map from the reals to the subset of two-decimal-digit-numbers, which means you could eschew it completely, since you can just as easily find such a map from the reals to the natural numbers – by leaving out the middle man and ‘representing’ the numbers between .01000… and .01999… with 1 and so on, for instance. This obviously doesn’t give you a ‘counting’ of the reals, since infinitely many of them are assigned the same ‘number’ each.
Perhaps, to make this whole business a bit more intuitive: consider the sets {3, 4, 5, 6} and {9, 16, 25, 36}. Even if you, through some excessive brain damage or something, suddenly lost the ability to count to four, you could prove that they have the same number of elements – by establishing the bijection:
3 <–> 9
4 <–> 16
5 <–> 25
6 <–> 36
I trust this is nothing contentious so far. Similarly, you can show that the sets {3, 4, 5, 6} and {3, 4, 5, 6, 9, 16, 25, 36} have a different number of elements without having to count, by establishing that no such bijection is possible. Furthermore, again without counting, you can show that the second set must be the ‘bigger’ of the two, because it includes all the members of the first set, and then some – the first set is a proper subset of the second.
Now, it won’t have escaped your attention that the choice of elements I’ve made isn’t quite an arbitrary one, instead, one collection of numbers are the squares of the other numbers, so that the bijection in the first example can be written as x → x[sup]2[/sup], just so we can get rid of the ‘table’ notion that’s apparently tripping you up – there’s no table necessary, Cantor’s proof (and what’s so far been offered in this thread) is perfectly valid if all you’re talking about are bijections in whatever form you may wish them to appear (just like there’s no difference between writing x → x[sup]2[/sup] or f(x) = x[sup]2[/sup] or y = x[sup]2[/sup] other than one of notation, there’s no real difference between the short table I’ve written down up there and any of those notations).
With this in mind, the case with the natural and the real numbers is essentially the same as in the second example, just that the number we can’t count to now is infinity rather than four or eight – there doesn’t exist any bijection between the two sets, and one set (that of the natural numbers) is a proper subset of the other, hence, it must contain less elements. And there you have it – though there are infinitely many elements within the naturals, they must be ‘less’ than the reals.
Assume a surjection f exists between a set S and its power set. Then there is some element x of S and the set {x in S | x is not in f(x)}. If x is in f(x), then x is not in f(x), and if x is not in f(x), x is in f(x). Therefore no such surjection can exist, regardless of the cardinality of S.
adhay, I’m not sure I understand your problem with the game. Could you be more specific about what your objection is? If you don’t think I’ve actually proved what I’ve stated I’ve proved, let’s play the game. You can be Bob and I’ll be the other guy.
Oh, great. What language’s syntax are you most familiar with? We can easily put the argument in programming terms. For example:
By “A -> B”, I mean the type of programs which take in inputs of type A and always end up outputting something of type B.
Theorem: For every program L of type A -> (A -> Bool), there is some program S of type A -> Bool which is not in its range.
Proof: Define S via S(x) = NOT (L(x)(x)).
Clearly, S cannot be equal to anything of the form L(c), since S returns a different value on the input c than L(c) does. Therefore, S is not in the range of L, just as we set out to prove. Q.E.D.
If you prefer a different syntax, let me know and we’ll write it in that language instead.
Note that there’s nothing here about infinite tables or real numbers or any such thing. That’s all a distraction and you’re getting too caught up in it.
adhay, I’d like to know where in the above you start to stumble or disagree. I think we can probably talk you through this proof pretty easily, clearing up any misunderstanding or getting rid of any disagreement you may have.
Or, hell, let’s just simulate some games between Bob and Cantor to illustrate how it would go:
Game 1
Bob, turn 1: My rules are that, if you want to put a color in Column #X, Row #Y of my square, then it has to be black if X + Y is even and white otherwise.
Cantor, turn 2: Alright. My rules are that if you want to put a color in Column #X of my sequence, then it has to be white if X + X is even and black otherwise.
Bob, turn 3: Ok. I pick… erm… Row #869.
Cantor, turn 4: Ok. I pick Column #869. Let’s see who wins.
We’ll put a color at Column #869 and Row #869 of Bob’s square; by his rules, this will have to be black, since 869 + 869 is even.
We’ll also put a color at Column #869 of Cantor’s sequence; by his rules, this will have to be white, since 869 + 869 is even.
The two colors we’ve just placed are different. Therefore, Cantor wins.
Bob: Curse you Cantor! Well, I’ll be more clever this time.
Game 2
Bob, turn 1: My rules are that, if you want to put a color in Column #X, Row #Y of my square, then it has to be black if X cubed plus the last digit of Y is prime, and white otherwise.
Cantor, turn 2: Alright. My rules are that, if you want to put a a color in Column #X of my sequence, then it has to be white if X cubed plus the last digit of X is prime, and black otherwise.
Bob, turn 3: Ok. I pick… erm… Row #12
Cantor, turn 4: Ok. I pick Column #12. Let’s see who wins.
We’ll put a color at Column #12 and Row #12 of Bob’s square; by his rules, this will have to be white, since 12 cubed plus the last digit of 12 is 1728 + 2 = 1730, which is not prime.
We’ll also put a color at Column #12 of Cantor’s sequence; by his rules, this will have to be black, since 12 cubed plus the last digit of 12 is 1728 + 2 = 1730, which is not prime.
The two colors we’ve just placed are different. Therefore, Cantor wins.
Bob: Hm… One more match?
Game 3
Bob, turn 1: My rules are that, if you want to put a color in Column #X, Row #Y of my square, then it has to be black if the X-th digit of π after the decimal point is a multiple of the Y-th digit of sqrt(2) after the decimal point, and white otherwise.
Cantor, turn 2: Alright. My rules are that, if you want to put a a color in Column #X of my sequence, then it has to be white if the X-th digit of π after the decimal point is a multiple of the Y-th digit of sqrt(2) after the decimal point, and black otherwise.
Bob, turn 3: Ok. I pick… erm… Row #7
Cantor, turn 4: Ok. I pick Column #7. Let’s see who wins.
We’ll put a color at Column #7 and Row #7 of Bob’s square. Since π = 3.1415926… and sqrt(2) = 1.41421356…, we have that the 7th digit of π after the decimal point is 6 and the 7th of sqrt(2) after the decimal point is 5. Since 6 is not a multiple of 5, the color we place will have to be white.
We’ll also put a color at Column #7 of Cantor’s sequence. Since π = 3.1415926… and sqrt(2) = 1.41421356…, we have that the 7th digit of π after the decimal point is 6 and the 7th of sqrt(2) after the decimal point is 5. Since 6 is not a multiple of 5, the color we place will have to be black.
The two colors we’ve just placed are different. Therefore, Cantor wins.
Bob: Man, you’re really good at this game.
Cantor: I’m unbeatable
Didn’t notice the second page, thought you all had left me on my own fool’s errand hypothesizing unicorns. I do appreciate your efforts and will try to address them.
Other than that you’ve chosen four values of X and eight of X^2. X–>X^2 is a valid bijection, as far as I know.
Don’t see how it’s the same. You’ve shown that a set of four elements is smaller than a set of eight. How this extrapolates to infinity is beyond me.
.
This seems to me to be a proof that Cantor’s diagonal method “works”. If L is limited to the maximum value of k (the diagonal exists), it does work, that is to say S(L) cannot be equal to any sequence in the range of L. But we know that the range of L is 0 to (10^k)-1, quite a different proposition.
No, that’s not correct. The range of L is (ostensibly) all real numbers. There is no maximum value of k; the real numbers can all be said to have an infinite number of digits. The construction of the real number S(L), which differs by at least one digit from every number in the range of L, demonstrates that the range of L cannot actually include all real numbers.
The range of L can be said to be (and not only ostensibly) all real numbers if the range (base 10) is 0 to (10^k)-1 [where k can be said to be infinite, I know we’re on shaky ground here]. Cantor does not acknowledge this. He assumes the range of L is 0 to k-1 (how else could the diagonal exist) and is surprised to find that S(L) cannot be equal to any sequence in the range of L.