0

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...............

herashefat
  • 919

1 Answers1

0

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$?

Noah Schweber
  • 245,398
  • Thanks for the detailed answer ....I was under the impression that the injectivity of F follows from the injectivity of f ,,,,As for the last two questions I cannot answer them since I do not still understand this well.... – herashefat Oct 27 '20 at 23:17
  • @herashefat Yes, the injectivity of $F$ follows from the injectivity of $f$, but that takes proof (which is what the last part of my answer does). If you don't understand this yet, where do you first run into trouble? For example, do you see that $(*)$ implies that for each $s\in S_1$ there is some $t\in S_2$ such that $f(s)=f(t)$? – Noah Schweber Oct 27 '20 at 23:20
  • Thanks Dr Schweber could explain surjectivity by any chance ? This is still hard for me thanks for your patience – herashefat Oct 27 '20 at 23:31
  • @herashefat Well, suppose $T\subseteq B$. Do you see a way to get a related subset of $A$? (HINT: think about $f^{-1}$ ...) – Noah Schweber Oct 27 '20 at 23:41
  • Apply f inverse to T?? But how this shows surjectivity of F?? – herashefat Oct 28 '20 at 00:09
  • @herashefat OK, when you say "apply inverse to $T$" what specific set are you building? The point is that this set should be something which $F$ sends to $T$ (so that $T$ is in the image of $F$, as hoped). – Noah Schweber Oct 28 '20 at 00:17
  • Would not a mapping say X to f(x) be surjective by construction??. So to answer the question we are building a set in A that maps to T?? – herashefat Oct 28 '20 at 00:54
  • @herashefat Yes, the goal is to find some subset of $A$ such that $F(A)=T$. – Noah Schweber Oct 28 '20 at 01:51
  • So the mapping F(X)= f(x) which is surjective by construction does the job?? – herashefat Oct 28 '20 at 03:11