Question

let H be the set of all functions from a set A to {0,1}. Show that |P(A)| = |H|... (P=powerset)

Answer 1

Try constructing a bijection between \(P(A)\) and \(H\).

Hint: Take for example \(A=\{1,2,3,4,5\}\) and some element \(\{3,4\} \in P(A)\). Now consider the function \[f :A \rightarrow \{0,1\}:\left\{ \begin{matrix} 1 \mapsto 0 \\ 2 \mapsto 0 \\ 3 \mapsto 1 \\ 4 \mapsto 1 \\ 5 \mapsto 0\end{matrix} \right. \;\;\; \in H.\]Now let \(\phi : P(A) \rightarrow H\) be the bijection we wish to construct. I claim it will be of your benefit to set \(\{3,4\} \overset{\phi}{\mapsto} f \). Think about what I am trying to hint at here.