Let \(A = \{1, \ldots, n\}\) . Show there is a bijection of \(\mathcal{P}(A)\) with the cartesian product \(X^n\), where \(X\) is the two-element set \(X = \{0, 1\}\) .
Show that if \(A\) is finite, then \(\mathcal{P}(A)\) is finite.
Solution
1. Map \(\mathcal P(A)\to X^n\) by \(S\mapsto (\chi_S(1),\dots,\chi_S(n))\) where \(\chi_S\) characteristic.
bijection, inverse \((x_i)\mapsto\{i:x_i=1\}\).
2. Hence \(|\mathcal P(A)|=2^n\) finite.
\(X^n\) has \(2^n\) elements.
3. Q.E.D.
2.