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?

  • 1
    $\begingroup$ 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. $\endgroup$ – ConMan May 13 '20 at 2:22
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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