Online Course Discussion Forum

II-A 7.24 and 7.25

 
 
Picture of Arjun Suryawanshi
II-A 7.24 and 7.25
by Arjun Suryawanshi - Sunday, 31 January 2021, 11:58 AM
 

I don't understand how you would write a bijection for this question.

 
Picture of Areteem Professor
Re: II-A 7.24 and 7.25
by Areteem Professor - Monday, 1 February 2021, 7:25 PM
 

If you want to write a bijection between the sets $A$ and $B$ you need to give a explicit rule that assigns to each element in $A$ and element in $B$, such that every element in $B$ is assignment exactly one element in $A$. (In particular, both sets must have the exact same number of elements).

For example, say in 24 that $n = 3$, so $A = \{0, 1, 2, 3, 4, 5, 6, 7,\}$, and $B = \{1, 2, 3\}$. The elements of $A$, written in binary, are $$000, 001, 010, 011, 100, 101,110, 111,$$ and the elements in $P(B)$ are $$\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}.$$ So a "natural bijection" between these is $$\begin{aligned} 000 &\mapsto \varnothing \\ 001 &\mapsto \{3\} \\ 010 &\mapsto  \{2\} \\ 011 &\mapsto \{2,3\} \\ 100 &\mapsto \{1\} \\  101 &\mapsto \{1,3\} \\ 110 &\mapsto \{1,2\} \\111 &\mapsto \{1,2,3\} \end{aligned}$$

Notice a pattern?