What's up with the Continuum?

Factual Questions
61

I think we’re having some terminology issues. You seem to be using a lot of words very imprecisely, which limits the ability of these statements to represent any kind of mathematical argument.

First off, what do you mean by “0 to (10^k)-1”? The most sensible way to read that implies that you’re referring to the subset of natural numbers in [0, (10^k)) for some k. But in that case, your statement that the range of L is all real numbers if the range is 0 to (10^k)-1 is patent nonsense, since you have clearly just said that the range is a subset of the natural numbers, which does not include, for example, the real number pi.

But in any case, why do you even think the expression (10^k)-1 has any significance here? Indistinguishable merely proved that any function L from natural numbers to sequences of decimal digits cannot contain all possible sequences of decimal digits. This is in fact slightly more general, but it still proves that a bijection from the naturals to the reals is impossible.

You’re also wrong if you say Cantor assumes the range of L is 0 to k-1, whatever it is exactly that you mean by that. The premise taken by Cantor’s argument is that L (the hypothetical bijection) has a range that includes all real numbers, period. I’m not sure what you mean by “how else could the diagonal exist.” Are you going back to insisting that the table somehow has to be a realizable thing in order for the function it abstractly represents to be, for lack of a better word, “usable”?

62

Shall I reword the game, adhay? You still haven’t responded to my request for clarification on your response to it.

Forget infinities, squares, sequences, real numbers, sizes, digits, everything. Fuck them all, throw them all away. They are distracting you to the point of blindness. (If you like, look at post #54, which doesn’t make any mention of any of those concepts and puts things in programming terms instead. Or, don’t bother, and just read this post.)

Bob comes up to Cantor and says “Let’s play a game”.

The way it works is that there are four turns:

On turn 1, Bob gets to make up some rules for how to answer questions of the form ‘What color does Bob decree for the inputs […] followed by […]?’. Whenever someone asks a question like that [e.g., ‘What color does Bob decree for the inputs 12 followed by 17?’], Bob’s rules should tell us a specific color to answer with.

On turn 2, Cantor gets to make up some rules for how to answer questions of the form ‘What color does Cantor decree for the input […]?’. Whenever someone asks a question like that [e.g., ‘What color does Cantor decree for the input 83?’], Cantor’s rules should tell us a specific color to answer with.

On turn 3, Bob picks some particular input value and announces “Bob’s input is such-and-such” [e.g., “Bob’s input is 19”].

On turn 4, Cantor picks some particular input value and announces “Cantor’s input is so-and-so” [e.g., “Cantor’s input is 52”].

After turn 4, all that’s left to do is figure out the winner: we use the rules the players gave to figure out the answers to the questions "What color does Bob decree for the inputs [Bob’s input] followed by [Cantor’s input]?’ and ‘What color does Cantor decree for the input [Cantor’s input]?’.

If both answers come out the same, Bob wins. If they come out different, Cantor wins.

Would you rather be Bob or Cantor when playing this game?

Cantor’s Theorem is precisely the statement “No matter what Bob does, Cantor can always win this game”.

The diagonalization proof is precisely the following win-guaranteeing strategy for Cantor: On turn 2, Cantor announces “To answer ‘What color does Cantor decree for the input [whatever]?’, take the opposite of the answer to ‘What color does Bob decree for the inputs [whatever] followed by [whatever]?’.” And on turn 4, Cantor picks the same input value as Bob picked on turn 3.

I outlined three examples above of how the game goes when Cantor plays with this strategy, though they were using my old wording. Suffice it to say, this strategy really does make Cantor unbeatable.

A) Do you have a problem with the mere concept of this game?
B) Do you have a problem with Cantor’s strategy for playing this game?
C) Do you have a problem with the assertion that Cantor’s strategy will guarantee that Cantor wins at this game?
D) Do you have a problem with the assertion that this is what mathematicians mean by Cantor’s theorem and Cantor’s proof? [Well, tough shit; don’t have a problem with it. Maybe you wouldn’t use the same wording as mathematicians use, but I’m telling you, when mathematicians talk about Cantor’s theorem, no matter what technical jargon they may be employing, all they mean is precisely that Cantor can always win this game, and when mathematicians talk about the diagonalization proof, all they mean is precisely the above strategy for Cantor to use to win this game.]

63

I think the sticking point for you is just the one in the question in D) above; hopefully that is indeed the case, and you can accept the response I gave in brackets, and that will clear away most of the argument, and we can have a productive discussion about whatever “philosophical” issues are left (and there are actually lots of interesting things to say here, but it’s not worth saying any of them till you first actually grasp the basics of what goes on with this game).

However, if you would attack the premises of A), B), or C) instead, then you are very much wrong, and I suggest you should “put up or shut up”, so to speak, before going any further. We’ll actually play the game, you in the Bob role and me in the Cantor role, and we’ll see who wins. If I can consistently beat you in the game, it would suggest I’m on to something, right?

64

@Indistingishable

I suppose the Games show how Cantor’s diagonal proof “works”. Of course, in Games 2 and 3, if X and Y were both say between one and two googles, Bob would spend the next few years figuring out his move, (and a maybe a few more locating the square). Cantor, as usual, would have an easy job of it.

edit: I need to look at you new post which appeared while I was writing this one.

65

Yeah, life is easier on Cantor’s side of the game in many ways (e.g., Cantor’s also the only one not doomed to lose), that being, ultimately, the point. Bob’s stuck playing a fool’s game.

Why do you put “works” in scare quotes above?

66

(Now that I’ve seen your edit: Ok, take your time)

67

@Indistinguishable

I was getting to you.

OK, I was nitpicking with my previous mention of googles above but it points toward my problem.

I have no problems with A, B, and C. I remember being delighted at the elegance of the diagonal proof when I first came across it many years ago. I could easily see that it “works” and why. But since then, I’ve come to question the way the proof is canonically presented, that is, as a square with a one-to-one correspondence between the x and y axes. It just can’t be so, imo. I won’t bore you by referring you to some of my previous posts in this regard.

Cheers

68

Alright. I, too, take some issue with the way the result is often presented, though perhaps not the same issues as you (it’s not entirely clear to me what you are referring to when you say “It just can’t be so”). But if you have no problem with A, B, and C, then I have no problem with you.

69

Just remember: whatever words mathematicians use when they describe this result, however much you might dislike the particular wording they employ (and I dislike much of this wording myself), ultimately, all they mean is the assertion in C which you agree with. The mathematicians aren’t making factually incorrect claims; at worst, they’re redefining pre-existing ordinary language perversely and misguidedly. But all the same, even if in a bizarre language, ultimately, they are making correct claims.

[In general, this is the case whenever one has issue with some claim in standard mathematics; the standard mathematics is almost never wrong (that is, it will almost always properly adhere to the rules it sets out for itself). Rather, at most, one could disagree that the formal concept which goes by some name in standard mathematical practice really does correspond (in some situation or another) to the informal concept(s) which go by that name in ordinary language]

70

@Stealth

Nope. If you refer to your quote of me in which I paraphrased your post #59, k is said to be infinite. 10 is in the expression for base 10.

Throughout your post you refer to k but neglect the fact we are talking about it as infinite. As k (x axis) increases linearly from 0, the counters or naturals (y axis) expand exponentially as (10^k)-1. When k=3, n = 999, k=4, n=9999 and so on. 4 by 9999 is not a square and it only gets more obvious as k increases. There is no reason to think that when k reaches infinity (fanciful, but we are just sayin’) that the list somehow squares itself up to provide us with a one-to-one correspondence between the x and y axes so we can produce a diagonal. This is the hidden (and I posit erroneous) basis for Cantor’s diagonal proof.

71

Thinking about things in terms of squares is tripping you up. So don’t think about squares. Think about the game.
Bob has no winning strategy for the Bob-Cantor game, right? That means Bob cannot make a move on turn 1 such that for every move Cantor makes on turn 2 there is a move Bob can make on turn 3 such that for every move Cantor makes on turn 4, Bob wins the game.

That means there cannot be any function f(x, y) from pairs of naturals to colors such that for every function g(x) from naturals to colors there is some natural b such that for every natural c, f(b, c) = g©.

Again, that’s exactly what was shown by the fact that Bob is doomed to lose the Bob-Cantor game.

But a function f(x, y) from pairs of naturals to colors amounts to same thing as a function f(x) from naturals to (functions from naturals to colors). So, that last statement amounts to the same as that there cannot be any function f(x) from naturals to (functions from naturals to colors) such that for every function g(x) from naturals to colors there is some natural b such that for every natural c, f(b)© = g©.

That is, there cannot be any function f(x) from naturals to (functions from naturals to colors) such that for every function g(x) from naturals to colors, there is some natural b such that f(b) = g.

That is, there cannot be any function f(x) from naturals to (functions from naturals to colors) such that every function g(x) from naturals to colors is in the range of f.

That is, there cannot be any surjection f(x) from naturals to (functions from naturals to colors).

Are you ok with all this? If not, at what point are you not ok with it?

We can go a color further just by switching terminology, though it doesn’t actually change the meaning one color. Rewriting that last line, we get:

There cannot be any surjection from naturals to (countably long sequences of colors) [where, in standard mathematical terminology, “countably long sequence of _s” is simply defined to mean “function from naturals to _s”].

And rewriting it again using that same definition, we get:

There cannot be any countably long sequence of (countably long sequence of colors) which contains every countably long sequence of colors.

But these all mean exactly the same thing, once you recognize what “countably long sequence of _” is defined to mean, in standard mathematical terminology.

72

Um. What? What is n? What is its relation to k? Why does that have anything to do with what we’re talking about?

Let’s run through Indistinguishable’s proof again:

First, we say that L(x) is a function that maps every natural number x to a sequence (possibly infinite) of decimal digits.

Next, we will simply construct another sequence of digits that cannot possibly be in the range of L – that is, it cannot be equal to any L(x), no matter what value we choose for x.

To do this, we define our sequence S in terms of the function L:

S(L) = { s[sub]0[/sub], s[sub]1[/sub], s[sub]2[/sub], … }, such that:
[indent]s[sub]k[/sub] = 0 if the kth digit in L(k) is odd
s[sub]k[/sub] = 9 if the kth digit in L(k) is even[/indent]

That is to say, the sequence S(L) is simply defined as a sequence of numbers, the kth of which always differs from the kth digit of L(k).

Therefore, no L(x) can be equal to S(L), no matter what x you pick.

Now, if you think there’s something wrong with this, can you explain to me how S(L) could possibly exist in the range of L? We have just defined S(L) so that it differs from every sequence in the range of L! What this means is that no matter what item you pick from the range of L, it will not equal S(L). That seems like a pretty good establishment of the fact that there is no possible bijection between natural numbers and all possible sequences of digits, yes?

73

:slight_smile: Serves me right for doing a find-and-replace… The words “color” here should be “bit”.

Anyway, go through post #71 slowly. Every step within it is just swapping one phrase for another phrase which, in standard mathematical terminology, is defined to mean the exact same thing. Tell us where, if anywhere, you get stuck on it.

74

Or, why don’t you tell us what, exactly, the Cantorian claim is which is erroneous (spell it out very precisely)? Then, we can tell you why (if it really is a standard way of expressing Cantor’s theorem) that claim has, in standard mathematical jargon by definition, the same exact meaning as the fact you agree to, that Cantor can assure a win in the Bob-Cantor game.

75

Back to you guy’s tomorrow. It’s beddy-bye for me.

76

Bullshit. No one, except for possibly you, is talking about k being infinite.

(by the way, let me interrupt my thoughts and refer to the fact that you’ve never bothered to respond to my response about your proposal of hypothesizing unicorns, which pretty much, to my mind anyway, negates your counter-argument about an “expanding” table which never “reaches” to infinity or aleph-naught or whatever–like I said, just pretend the table/unicorn is already there, the resulting contradiction demonstrates the impossibility of such existence).

Anyway, back to k. Are you familiar at all with mathematical induction? It’s one of the defining (Peano axioms) properties of the natural numbers. It says:

If S(n) is a proposition about some natural number n, and:

  1. S(0) is true,

  2. Whenever S(n) is true, S(N+1) is also true,

then it follows that S(n) is true for all natural numbers n.

Here’s an erroneous use of mathematical induction:

Let S(n) be the proposition that n is a finite number.

It’s trivial to see that this proposition satisfies the hypotheses of mathematical induction. “For any natural number n, n is a finite number” is a true proposition.

Of course, that’s not the erroneous part. It would be erroneous to therefore state, “The set of natural numbers is a finite set”. This is hopefully obvious, but a lot of misuses I’ve seen of induction boil down to a similar mistake.

Back to Cantor; Cantor’s proof can be stated in terms of indcution: Suppose the function f is a bijection from the naturals to the reals (as I said before, this is a free assumption we can make, based on the fact that it will lead to contradiction, negating the possibility of such a bijection).

Go through Cantor’s diagonalization process of constructing a real number (call it x) that cannot be in the image of f (the fact that it cannot be in the image is what we will prove with induction):

(To simplify indexing, I’ll start with 1 rather than 0).

  1. f(1) cannot be x because it differs from x in the first decimal place.

  2. If f(n) is not equal to x, then f(n+1) cannot be equal to x since it differs from x at the (n+1)st decimal place.

Therefore, f(n) is not equal to x for ALL natural numbers n.

To be honest, it only occurred to me as I was writing that last bit that this proof doesn’t hinge in any necessary way on induction; the fact that f(n+1) doesn’t map to x doesn’t really follow from f(n) not mapping to x–it really just follows from the Cantor diagonal construction of x.

However, in spite of that, I’m not going to abandon this post, because I think the punch line is still relevant. The punch line is this:

For all (finite) natural numbers n (or k–obviously the label is irrelevant), f(n) cannot possibly be equal to x.

Do you understand the quantifier “for all”? In the previous statement, there is no “inifinte” n (or k) being referred to; hence my “Bullshit” comment prefacing this entire post.

To summarize: For all k, f(k) cannot be equal to x. Each of these k are FINITE numbers. The total collection of all of these k is an infinite set. However, we are making no comments at all about this infinite set. What Cantor’s proof demonstrates is that none of the (infinitely many) natural (finite) numbers will map onto x, therefore the bijection f cannot exist.

77

What I’ve shown – that if 1. two sets can’t be put in a bijection with each other, and 2. one set is a proper subset of the other, then the set which is a proper subset of the other necessarily is of a lesser cardinality – works for sets with an arbitrary number of elements; remember, I didn’t use the numbers four or eight anywhere, and even asked you to forget that you can count that far. And there’s not much of a difference between four and infinity other than that you can’t count to infinity; if your problem with the result lies in the impossibility of practically counting that far, then you should have the same problem declaring that a set with 10[sup]10[sup]100[/sup][/sup] + 1 elements is larger than a set with only 10[sup]10[sup]100[/sup][/sup] elements – you can’t count that far any more than you can count to infinity.

Anyway, there’s more capable people than me making better arguments, so I’m gonna leave the playing field to them.

78

adhay, the word is “googol,”, not “google.” There’s a difference:

79

Thank you Wendell.

OK guys,

After reading a bit more, I’m willing to admit I was wrong in much of what I’ve said and agree that the reals are of a higher cardinality than the naturals. The evidence does seem overwhelming. Thanks for your perseverance. I still have a question about the diagonal proof, however. I’m going lay out my reasoning in much the same way as Indistinguable did with his game and I’d like you to agree or disagree with reason on a point-by-point basis. Please indulge me.

Let’s pretend that the topic reads “What’s up with Cantor’s Diagonal Proof?” as it should have.

Assuming base 10, k = the number of decimal places and n = the number of naturals produced, the range of y = 0 to n-1

A) In order for the proof to work, there must be (assumed) a one-to-one correspondence between the x and y axes. If max y > max x, we could not be sure that our constructed new number did not lie somewhere in the list “below” the diagonal. If max y<max x, we could not produce a “full” real. I’m assuming that all reals are the same length, but in our thought experiment, this does not pertain.

B) If we start at k=n=0 and increase k linearly, n increases exponentially. Thus when k=1, n=10 and the range of y = 0 to 9 or 0 to (10^k)-1, when k=2, the range of y = 0 to 99 and so on on. As k increases toward infinity, the table becomes less of a square and more of a ribbon, then a flat string, then a hair, then … . All the way toward infinity, max y>max x>.

C) Thus, while k is finite no matter how large, there is not a one-to-one correspondence between the x and y axes and no diagonal is possible.

And here’s the sticking point:

D) Somehow, if Cantor’s proof is to work, when k reaches infinity (I assume that’s what those ellipses to right of the last digit of each number represented in the table mean), the table becomes a square. My question is, wtf?

Thanks again for your attention.

80

I’m not going to get in the way of the mathematicians. I just want to remind any non-mathematicians lurking that the definition of infinity is “without end”. Nothing ever reaches infinity. That is a contradiction in terms. If you use “reach” in any of your thinking about infinity you are guaranteed to reach a wrong result.

Back to the mathematicians.