wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Power set of natural numbers
        
(Message started by: Rajan on Mar 31^st, 2010, 1:21am)

Title: Power set of natural numbers
Post by Rajan on Mar 31^st, 2010, 1:21am

For any set A, Cantor's theorem states that the Power set of A cannot be 1-1 with A and is also proved for countably infinite sized A.

However, I devised a construction which tries to achieve this bijection for a countably infinite set. Since it is opposite to an established theorem, there might be a flaw (or not). Can you spot a flaw? Here is the construction...

The power set of whole numbers consists of
0. {}
1. {0}, {1}, {2}, {3},...
2. {0,0}, {0,1}, {1,0}, {1,1}, {0,2},...
3. {1,1,1},{1,1,2},...
... ...

List 0 is of finite size.
We know that there are countably infinite sets in List 1.

Lemma: List 2 is also countably infinite in size. To show this, we can imagine the set {a,b} as the integral grid point (a,b) in 2d space. Each grid point in the first quadrant of this 2-d plane maps to a unique set in list 2. Now the final step - to map whole numbers to each grid point, we can map 0 to the origin and move in a zig zag pattern (see zigzag pattern image below). This pattern maps a whole number to each set in List 2.

Lemma : List 3, 4 and onwards can also be proved to be countably infinite with a similar construction. I am not proving this as the construction seems intuitively similar. (this is one possible flaw, as I have not proved that this can be carried out for every List, but I feel this to be intuitively correct)

Now we have a countably infinite sequence of lists, each of which contains countably infinite sets. We can assign each of these sets to a 2d grid point in the following manner...
For list 1 - {0} maps to {1,0},
{1} maps to {1,1},
{k} maps to {1,k}...

For list 2 - {0,0} maps to {2,0},
{1,0} maps to {2,1},
{0,1} maps to {2,2},
{m,n} maps to {2,p}...

For list 3 - {0,0,0} maps to {3,0},
{1,0,0} maps to {3,1},
{0,1,0} maps to {3,2},
{m,n,k} maps to {3,t}...

and so on...

All these points are on the countably infinite grid points of the 1st quadrant of the 2d plane. We can simply map them to the whole numbers again using the same zigzag trick we used earlier for List 2.
This way, each subset of the power set, no matter its elements (as long as all its elements are finite), can be mapped to a unique finite whole number. QED.

I am sure this is the kind of thing every set theory student goes through in their coursework... I am new to it and cant see the flaw readily (or maybe there is none :-)).

http://www.ams.org/featurecolumn/images/september2007/zigzag.gif

The zigzag shown here is constrained in a 8x8 square. In a 2d plane with 2 sides open, the zigzags continue to get larger and larger.

Title: Re: Power set of natural numbers
Post by pex on Mar 31^st, 2010, 1:53am

Your construction works fine for finite-sized subsets; however, what will you do with the infinite-sized ones? Specifically, in your construction, where does the complete set of whole numbers go?

Title: Re: Power set of natural numbers
Post by rmsgrey on Mar 31^st, 2010, 8:20am

Another minor quibble: {1,1} isn't a subset of the natural numbers - or at least not a different subset from {1}. Also {0,1} and {1,0} are not distinct sets.

Neither of those objections invalidates the original argument - the problem, as pex pointed out, is that the construction only covers the finite subsets. You can use a similar construction to cover the co-finite subsets (those whose complements are finite) but there's still a vast (uncountable by Cantor's theorem) number of infinite subsets whose complements are also infinite which you have to take account of somehow...

Title: Re: Power set of natural numbers
Post by pex on Mar 31^st, 2010, 8:29am

Actually, there is a much simpler construction that achieves exactly the same result as yours: just sort each subset {x₁, x₂, x₃, ..., x_n} so that

x₁ < x₂ < x₃ < ... < x_n

and assign to it the natural number

(2^x₁)*(3^x₂)*(5^x₃)*...*(p_n^x_n).

Title: Re: Power set of natural numbers
Post by Grimbal on Mar 31^st, 2010, 8:33am

Or 2^x₁ + 2^x₂ + 2^x₃ + ... + 2^x_n

Title: Re: Power set of natural numbers
Post by pex on Mar 31^st, 2010, 8:41am

on 03/31/10 at 08:33:48, Grimbal wrote:

Or 2^x₁ + 2^x₂ + 2^x₃ + ... + 2^x_n

Yeah, that's a lot more economical.

Title: Re: Power set of natural numbers
Post by Rajan on Mar 31^st, 2010, 10:15am

Thanks for the responses... Pex's and Grimbal's construction were beautiful.

rmsgrey - that gives me some food for thought. This stuff borders on crazy... my mind start to numb after a few minutes of thought. No wonder Mathematicians were extremely touchy about it.

Title: Re: Power set of natural numbers
Post by Grimbal on Apr 1^st, 2010, 8:55am

People who think they can prove something mathematicians have tried and failed to prove for centuries, must be crazy.

And that seems to apply even when the person is actually right in his claim.
http://en.wikinews.org/wiki/Russian_mathematician_declines_Fields_Medal
;D