# Find bijection between power set and the product of two elements set

Suppose $$A = \{ 1,...,n \}$$. Prove that $$\exists$$ a bijection of $$\mathcal{P}(A) = \{ B : B \subset A \}$$ (power set of A) and the set $$X^n$$ where $$X = \{ 0,1 \}$$. In addition, Prove that $$\mathcal{P}(A)$$ if finite.

## my work:

I have an idea how to construct this bijection: Notice that $${n \choose i}$$ is the number of subsets of $$A$$ of size $$i$$. Now, let $$B \subseteq A$$. Let $$N(B)$$ denote the sum of the elements of $$B$$. For example, if $$B = \{1,2,3 \} \subset A$$, then $$N(B) = 1+2+3 = 6$$ and we can define $$f : \mathcal{P}(A) \to X^n$$ as

$$f(B) = (\underbrace{1,1,1,....,1}_{N(B) times}, 0 , 0,0,0,0 )$$

This is still not a bijection as elements of the form (1,1,0,1,1,1,....) have no $$B$$ that get mapped to it. Any hint into how to construct this function? Is my strategy correct?

• Maybe take a small, fixed value for $n$ (e.g. 3) and explicitly write out its power set, then see if there's a nice way to associate it to triplets of 1s and 0s? I would suggest making the empty set map to (0, 0, 0) and {1, 2, 3} map to (1, 1, 1), if that's a bit of a hint. – ConMan May 13 '20 at 2:22
• I don't think your function is well defined,. Any $B \subseteq A$ that contains $n$ and any other element would have $N(B) >n$, but you only have $n$ many spaces for 0s and 1s. Also, it isn't injective as $\{1,2\}$ and $\{3\}$ have the same value under $B$. The bijection you want doesn't really care that $A$ contains exactly the numbers $1,...,n$. It only cares that it contains exactly $n$ elements, so you shouldn't be looking for a "numerical" function. – James May 13 '20 at 2:49

The natural way to do this is to define $$f_S\in X^n$$ by $$f_S(x)=\begin{cases}1\,,x\in S\\0,\,x\notin S\end{cases}$$.
This defines a bijection between $$P(A)$$ and the function space $$X^n$$.
You can see from this that $$P(A)$$ has order $$2^n$$.