Proving the Equivalence of Power Sets: A Challenge in Bijection

[issacnewton]

Hi

Here is the problem I am doing. Prove that

^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\sim \mathcal{P}(\mathbb{Z^+})

Where ^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+}) is the set of functions
from \mathbb{Z^+} to \mathcal{P}(\mathbb{Z^+}).

To prove this I will need to come up with some bijection from ^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+}) to \mathcal{P}(\mathbb{Z^+})

I am having hard time with this bijection. How do you map a subset of \mathbb{Z^+} to some function from \mathbb{Z^+} to
\mathcal{P}(\mathbb{Z^+})

I have been able to get some insight into the problem so far. I have proven that
\mathcal{P}(\mathbb{Z^+}) is uncountable. So it means that any function
from \mathbb{Z^+} to \mathcal{P}(\mathbb{Z^+}) can not be onto.

I would appreciate further insight to attack the problem.

thanks

 

[micromass]

Maybe you can start by proving that

\mathcal{P}(\mathbb{Z}^+)\cong {}^{\mathbb{Z}^+}\{0,1\}

 

[issacnewton]

micromass

I have already proved that for any set A

\mathcal{P}(A)\sim \; ^{A}\{\mbox{ yes,no }\}

So putting yes=1 and no=0 and letting A= \mathbb{Z^+} , we get what you
are saying. I have also proved that for any sets A,B,C

^{(A\times B)}C\;\sim \; ^{A}( ^{B}C)

So how do things help me ?

 

[micromass]

Now it suffices to show

\mathbb{Z}^+\times \mathbb{Z}^+ \cong \mathbb{Z}^+

 

[issacnewton]

ok I think I got it

I have already shown that \mathbb{Z^+}\times \mathbb{Z^+}\;\sim\; \mathbb{Z^+}

Also I have shown previously that for any sets A,B,C,D if A\sim B and C\sim D then it follows that

^{A}C \;\sim \;^{B}D\cdots\;(1)

and

\mathcal{P}(A)\;\sim\;\mathcal{P}(B)

So it follows that

\mathcal{P}(\mathbb{Z^+})\;\sim\;\mathcal{P}( \mathbb{Z^+}\times \mathbb{Z^+})\cdots\;(2)

Since for any set A

\mathcal{P}(A)\;\sim\; ^{A}\{0,1\}

we have

\mathcal{P}(\mathbb{Z^+}\times \mathbb{Z^+})\;\sim\; ^{(\mathbb{Z^+}\times \mathbb{Z^+} )} \{0,1\} \cdots\;(3)

But for any sets A,B,C we have

^{(A\times B)}C\;\sim\; ^{A}( ^{B}C)

So we have

^{(\mathbb{Z^+}\times \mathbb{Z^+} )} \{0,1\}\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )\cdots\;(4)

so using equations 2, 3 and 4 ,due to transitivity of \sim we can say that

\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )<br /> \cdots\;(5)

Now

\mathbb{Z^+}\;\sim \mathbb{Z^+}

and

\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}\{0,1\}

It follows from 1 that

^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\;\sim\; ^{\mathbb{Z^+}}(^{\mathbb{Z^+}} \{0,1\} )

Now using 5 , we can say that


^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+})\;\sim\; \mathcal{P}(\mathbb{Z^+})

thanks micromass, that was a lot of typing

I was thinking of coming up with some bijection. I think that's probably lot more difficult
in this case.

 

[issacnewton]

By the way I was wondering, if any bijection could be found between
^{\mathbb{Z^+}}\mathcal{P}(\mathbb{Z^+}) and \mathcal{P}(\mathbb{Z^+}) ?

 

[micromass]

Yes, I think so. Notice that every element of \mathcal{P}(\mathbb{Z}^+) is determined by a sequence of 0 and 1 (where 1 means that the corresponding element is in the subset). For example, the subset

\{1,4,5,10\} is

1,0,0,1,1,0,0,0,0,1,0,0,0,0,...

Now, given an element of {}^{\mathbb{Z}^+}\mathcal{P}(\mathbb{Z}^+). Such an element is a countable list of sequences. So such an element is given by

x_{1,1},x_{1,2},x_{1,3},x_{1,4},x_{1,5},...
x_{2,1},x_{2,2},x_{2,3},x_{2,4},x_{2,5},...
x_{3,1},x_{3,2},x_{3,3},x_{3,4},x_{3,5},...
x_{4,1},x_{4,2},x_{4,3},x_{4,4},x_{4,5},...
x_{5,1},x_{5,2},x_{5,3},x_{5,4},x_{5,5},...

We wish to make an element of \mathcal{P}(\mathbb{Z}^+) of that. So we wish to make one sequence of it. This is possible by following the diagonals. So an associated sequence would be

x_{1,1},x_{1,2},x_{2,1},x_{1,3},x_{2,2},x_{3,1},...

 

[issacnewton]

Micromass, but how do we make sure that every element of \mathcal{P}(\mathbb{Z}^+) has an element associated in {}^{\mathbb{Z}^+}\mathcal{P}(\mathbb{Z}^+) ?

For example consider \{1\} \in \mathcal{P}(\mathbb{Z}^+) . How does your
diagonal argument work here ?