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\} ) \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 ?