Cantor's Argument

[jordan]

One of my professors tried to explain Cantor's Argument today. I'm not sure if he tried to do a dumbed down version or what, but it was kinda weird. He did this thing were we played a game. Player one had a 6x6 grid and player two got a row of 6 boxes. Player one then filled in each row of his grid with 0's and 1's in any order.

 

For example:

000000 -row1

100000 -row2

110000 -row3

001100 -row4

011110 -row5

010101 -row6

 

and then it was player two's job to create a row of six that did not match any of player one's rows. The method was to take row 1 column 1 and put the opposite number in there. For my example that would mean player two puts a 1 in his first box. Then row 2 column 2...and so on. Usuing that method should ensure that player two can always create a unique set.

 

Carry this on for grids of nxn where n is infitine then it seems to be shown that there can always be a row (as created by player two) of infinite 0's and 1's that wasn't in the previous list and therefore there's isn't a 1-1 corespondence between the natural numbers and infinite sets of 0's and 1's.

 

This isn't to say I don't believe Cantor, it's just this particular proof seems wrong. I tried to explain why I think this is wrong to my professor and he just kinda shrugged it off. I wasn't real satisfied with his answer for me. But before I get to my counter-argument I guess I should check to make sure all the above makes sense to everyone. So is that a familiar proof? Or is that just a simplified version or Cantor's? And most important, does all the above make sense?

[matt grime]

What counter argument? Cantor's theorem is precisely that there is not a 1-1 correspondence between the set of binary strings indexed by N and N.

 

Be careful abusing terms as in 'nxn where n is infinite'

[jordan]

I'm not objecting to Cantor's theorem, I'm objecting to the way it was proven above by my professor.

[matt grime]

So what is your counter argument? That is a standard proof for Cantor's argument that there is no bijection between N and P(N), since P(N) is in bijection with the strings of binary digits indexed by N: these are just parametrizations of indicator functions.

[jordan]

Haha...no. I'm not contesting Cantor's argument. Let me ask you this, the proof I outlined in my first post, is that the way Cantor proved it?

[matt grime]

I have no idea what his first proof was. Now, you've twice said you have a problem with this particular proof (I can think of two or three more if you want, well, now i've said that i'm not so sure; there is an analysis proof lurking in the back of my mind) so what is your problem with this proof?

 

"just this particular proof seems wrong"

 

Why?

 

"I'm objecting to the way it was proven above "

 

Again, why?

 

All that is is a nice way of visualizing what the construction of the set:

 

{t in T : t not in f(t)}

 

where f is any injection from T to P(T)

[jordan]

I can't prove any of it in formal math as you have done. I've only made it through calc III.

 

But my argument is this:

 

We can play the game so that every infinite set of 0's and 1's is covered. Do this by first covering all possible combonations of the first digit...namely 0 and 1. Then fill out each infinite sequence with 0's or 1's so it looks like this.

 

00000000000...

10000000000...

01111111111...

11111111111...

 

Then we do this for the first two numbers...

 

00000000000...

11000000000...

01000000000...

10000000000...

00111111111...

11111111111...

01111111111...

10111111111...

 

and now you can even notice that four of these eight are the same as the first four I contructed. So if we continue this pattern I can contruct it so that no matter what move player two makes I have already it covered. And the fact that player player two could always make a sequence not covered by player one was the basis of my professor's proof of Cantor's argument.

 

So I want to know where/if I went wrong. All my professor told me was "something seems wrong there..." and couldn't tell me what.

 

I'm not suggesting that Cantor's argument was wrong, just that the proof provided here is.

[matt grime]

The most obvious error is that you do not produce a list of all possible strings of 0s and 1s. All of your strings are ones that are eventually either all 1s or all 0s. The string

 

10101010101....

 

will appear no where in your list. (Try to tell me where on the list it is. It must be at some finite position, but at any position in the list so produced all of the digits after some point are either 1 or 0.)

 

What you have here is the fact that the finite power set of N is countable, as is the cofinite power set of N, and that is not surprising, but neither of those, nor their union are the same as the power set of N.

 

This is the standard thing that people get wrong when trying to find a flaw in this proof.

[jordan]

I think my flaw as I've figured out was that I forgot the fact that player two's set would be infinite.

 

I'm sure you've heard the story before about the guy who puts 10 balls into a hat and then takes out ball 1. Then 10 more and take out ball two and does this infinite times. And the thing is there are no balls left in the hat when he's done. This is because no matter which ball you try to tell me is left in the hat, I can tell you which step it was actually taken out at.

 

I thought my case was the same sort of logic: no matter what series you give me I can create my list long enough to encompass yours. But I guess I lost sight of the fact that the sets are infinte.

[matt grime]

You also have the order the wrong way round. You must specify your list first, then I get to pick something not on it, and you can't alter the list after you specify it to take my choice into account.