Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Yes. It is possible to come up with such bijection. – Asaf Karagila Jan 7 '13 at 16:35
up vote 1 down vote accepted

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.


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

share|cite|improve this answer

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

share|cite|improve this answer

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.