# 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?

-
Yes. It is possible to come up with such bijection. – Asaf Karagila Jan 7 '13 at 16:35

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$$

-

Take $\phi(S)$ to be such number that its $k$th bit is $1$ iff $k \in S$.

-

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?

-