Take the 2-minute tour ×
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.

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|improve this question
1  
Yes. It is possible to come up with such bijection. –  Asaf Karagila Jan 7 '13 at 16:35
add comment

3 Answers 3

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.

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.