Online Course Discussion Forum

II-A 7.24 and 7.25

II-A 7.24 and 7.25

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

Re: II-A 7.24 and 7.25

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?