Exercise 6.6

Proof. We construct a bijection $f:P\left(A\right)\to X^n$. So, for any $Y\in P\left(A\right)$ we have that clearly $Y\subset A$. Then set

for any $i\in \left\{1,\dots ,n\right\}=A$. Now set $f(Y)=x=\left(x_1,\dots ,x_n\right)$, noting that clearly $f(Y)\in X^n$ since each $x_i\in \left\{0,1\right\}=X$. Hence $f$ is a function from $P\left(A\right)$ to $X^n$.

To show that $f$ is injective consider $Y$ and $Y^{\prime }$ in $P\left(A\right)$ where $Y\ne Y^{\prime }$. Also let $x=f(Y)$ and $x^{\prime }=f(Y^{\prime })$ as defined above. Since $Y\ne Y^{\prime }$, we can without loss of generality assume that there is an $i\in Y$ where $i\notin Y^{\prime }$. It then follows that $x_i=1\ne 0=x_i^{\prime }$ by the definition of $f$. Hence clearly $f(Y)=x=\left(x_1,\dots ,x_n\right)\ne \left(x_1^{\prime },\dots ,x_n^{\prime }\right)=x^{\prime }=f(Y^{\prime })$, which shows that $f$ is injective since $Y$ and $Y^{\prime }$ were arbitrary.

Now consider any $x\in X^n$ and let $Y=\left\{i\in A\mid x_i=1\right\}$. Clearly $Y\subset A$ so that $Y\in P\left(A\right)$. Let $x^{\prime }=f(Y)$ and consider any $i\in \left\{1,\dots ,n\right\}=A$. If $i\in Y$ then $x_i=1=x_i^{\prime }$ by the definitions of $Y$ and $f$. It $i\notin Y$ then $x_i\ne 1$ so that it has to be that $x_i=0$ since $x_i\in X=\left\{0,1\right\}$. Also, by the definition of $f$, we have that $x_i^{\prime }=0=x_i$. Thus in either case $x_i=x_i^{\prime }$ so that $x=x^{\prime }=f(Y)$ since $i$ was arbitrary. Since $x$ was arbitrary, this shows that $f$ is surjective.

Therefore $f$ is a bijection from $A$ to $X^n$ as desired. □

Proof. First, if $A=\varnothing$ then clearly $P\left(A\right)=P\left(\text{∅}\right)=\left\{\text{∅}\right\}$ is finite. So assume in what follows that $A\ne \varnothing$. Since $A$ is finite and nonempty there is a bijection $f$ from $A$ to $B=\left\{1,\dots ,n\right\}$ for some $n\in {\mathbb{Z}}_{\text{+}}$. Let $X=\left\{0,1\right\}$ so that by part (a) there is a bijection $g$ from $P\left(B\right)$ to $X^n$. For any $Y\in P\left(A\right)$ clearly the mapping $h(Y)=\left\{i\in B\mid f^{-1}(i)\in Y\right\}$ is a bijection from $P\left(A\right)$ to $P\left(B\right)$. It then follows that $g\circ h$ is bijection from $P\left(A\right)$ to $X^n$. Since clearly $X^n$ is a finite cartesian product of finite sets, it follows from Corollary 6.8 that $X^n$ is finite so that $P\left(A\right)$ must be as well since there is a bijection between them. □