Originally Posted by

**undefined**

So, as above, let $\displaystyle A$ be the powerset of $\displaystyle \{1,2,...,n\}$ and let $\displaystyle B$ be the set of $\displaystyle n$-digit binary numbers (leading zeroes allowed).

Define $\displaystyle f: A \to B, f: a \mapsto b$ such that for all $\displaystyle i, 0 < i \leq n$, $\displaystyle i \in a$ if and only if the $\displaystyle i$th bit of $\displaystyle b$ is 1.

$\displaystyle f$ is one-to-one because for any $\displaystyle a_1 \in A, a_2 \in A, a_1 \neq a_2$ there exists an element $\displaystyle i$ which is either in $\displaystyle a_1$ but not in $\displaystyle a_2$ or vice versa; because otherwise $\displaystyle a_1 = a_2$. Therefore the $\displaystyle i$th bit of $\displaystyle f(a_1)$ differs from that of $\displaystyle f(a_2)$ and $\displaystyle f(a_1) \neq f(a_2)$.

$\displaystyle f$ is onto because every $\displaystyle b \in B$ can be used to construct an $\displaystyle a \in A$. Simply build up $\displaystyle a$ by deciding for all $\displaystyle i, 0 < i \leq n$ whether $\displaystyle i \in a$ or $\displaystyle i \not \in a$ according to the $\displaystyle i$th bit of $\displaystyle b$.

Therefore, $\displaystyle f$ is bijective and $\displaystyle |A| = |B|$.