Bijection between power set and power of the set. This problem courtesy of Allen Clark's "Elements of Abstract Algebra".
Let $N_k=\{1, 2, \ldots, k\}$. Construct a bijection, $\phi: 2^{N_k} \to N_{2^k}$, where $$2^{N_k}=\{S \mid S \subset N_k\}.$$
Can anyone come up with one?
 A: Take $\phi(S)$ to be such number that its $k$th bit is $1$ iff $k \in S$. 
A: Let be$A_k=\{a_0,a_1,...,a_{k-1}\}$ a $k$-set and $S(A_k)$ the set of all subsets of $A_k$ 
and $I_k=\{0,1,...,k-1\}$
For each $B\subset A_k$ we defines a function $$g:S(A_k)\to I_{2^k}$$ with $$g_B=\sum_{a_j\in B} {2^j},g_{\emptyset}=0$$ 
$$g_{A_k}=\sum_{a_j\in A_k}2^j=2^0+2^1+...+2^{k-1}=\frac{1-2^k}{1-2}=2^k-1$$ 
for entire set that from definition is subset of itself. This way we prove that each subset of a k-set 
is numbered by a number from set $I_{2k}=\{0,1,...,2^k-1\}$ or in other words. 
$|S(A_k)|=|I_{2^k}|=2^k$ 
For example for set $A_3=\{a_0,a_1,a_2\}$ we have $S(A_3)\to I_{2^3}=I_8 $ 
$$\emptyset\to 0$$
$$\{a_0\}\to2^0=1$$
$$\{a_1\}\to2^1=2$$ 
$$\{a_0,a_1\}\to2^0+2^1=3$$
$$\{a_2\}\to2^2=4$$
$$\{a_0,a_2\}\to2^0+2^2=5$$
$$\{a_1,a_2\}\to2^1+2^2=6$$
$$\{a_0,a_1,a_2\}\to2^0+2^1+2^2=7$$  
A: For any function $f:N_k\to\{0,1\}$ (this is the form of any element in $2^{N_k}$), define $\phi(f)=\{x\in N_k:f(x)=1\}$. Can you prove that this is bijective?
