Online Course Discussion Forum

ll-A Homework 7.24

 
 
YangFelix的头像
ll-A Homework 7.24
YangFelix - 2018年01月27日 Saturday 13:57
 

How do you find a natural bijection for 7.24, I think I know how to do but just confused about the last part how to proof injective and surjective.


Thanks!

 
ReynosoDavid的头像
Re: ll-A Homework 7.24
ReynosoDavid - 2018年01月29日 Monday 10:43
 

Maybe trying with a couple of small values of $n$ could give a hint into what the bijection is. Remember, the hint is to think of the elements of the set $A$ as written in base $2$.

If $n=1$, then $A=\{0,1\}$ and $B=\{1\}$. So, $P(B) = \{\varnothing, \{1\}\}$ and the bijection is $$0=0_2\mapsto\varnothing,\ 1=1_2\mapsto\{1\}.$$

If $n=2$, then $A=\{0,1,2,3\}$ and $B=\{1,2\}$. So, $P(B) = \{\varnothing, \{1\}, \{2\},\{1,2\}\}$ and the bijection is $$0=0_2\mapsto\varnothing,\ 1=1_2\mapsto\{1\},\ 2=10_2\mapsto\{2\},3=11_2\mapsto\{1,2\}.$$

YangFelix的头像
Re: ll-A Homework 7.24
YangFelix - 2018年01月29日 Monday 19:15
 

Thanks!