Bijection between Power Set of Natural numbers and Power Set of integers

Question

There is for sure more than one method to do this , however I want to understand the hint provided in my book .The book says to use the bijection between N and Z given by f(n)=n/2 if n is even and f(n)= (1-n)/2 if n is odd .I think I can prove one to one , but why is f(n) onto ?? More importantly how does this translate into a bijection between P(N) and P(Z)?? is it automatic? I believe some explanation is required but I cannot figure it out...............

Answer 1

Thinking in terms of the specific sets may make this look more mysterious than it actually is: what we're seeing here is an instance of a more general phenomenon.

Namely:

Suppose there is a bjiection between $A$ and $B$. Then there is also a bijection between $\mathcal{P}(A)$ and $\mathcal{P}(B)$.

To see this, suppose $f:A\rightarrow B$ is a bijection and I have a set $S$ of elements of $A$. The function $f$ only takes as input individual elements of $A$, so something like "$f(S)$" doesn't make sense; nonetheless, do you see a way to use $f$ to turn $S$ into a subset $\hat{S}$ of $B$?

Just apply $f$ to each of the elements in $A$: that is, set $$\hat{S}=\{f(x): x\in S\}.$$

Let's give the construction above a name, call it "$F$." That is, $F$ is the function

$$F:\mathcal{P}(A)\rightarrow\mathcal{P}(B): S\mapsto\{f(x): x\in S\}.$$

Can you see how to use the fact that our original function $f$ is a bijection to show that $F$ is also a bijection between $\mathcal{P}(A)$ and $\mathcal{P}(B)$?

I'll sketch how to prove injectivity (proving surjectivity is similar). Suppose $F(S_1)=F(S_2)$; we want to show that $S_1=S_2$. Well, by definition of $F$ we have $$(*)\quad\{f(x): x\in S_1\}=\{f(x): x\in S_2\}.$$ To show that $S_1\subseteq S_2$ (the converse containment is proved identically), note that $(*)$ implies that given $s\in S_1$ there is some $t\in S_2$ such that $f(s)=f(t)$. What does this tell you about $s$ and $t$, and what properties of $f$ are you using to show this? And do you see why this means $S_1\subseteq S_2$?