Online Course Discussion Forum

ll-A Homework 7.24

 
 
Picture of Felix Yang
ll-A Homework 7.24
by Felix Yang - Saturday, 27 January 2018, 1:57 PM
 

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!

 
Picture of David Reynoso
Re: ll-A Homework 7.24
by David Reynoso - Monday, 29 January 2018, 10:43 AM
 

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\}.$$

Picture of Felix Yang
Re: ll-A Homework 7.24
by Felix Yang - Monday, 29 January 2018, 7:15 PM
 

Thanks!