Exercise 7.3

Proof. Similar to Exercise 6.6 part (a), we construct such a bijection $f$ from $P\left({\mathbb{Z}}_{\text{+}}\right)$ to $X^{\omega }$. For any $A\in P\left({\mathbb{Z}}_{\text{+}}\right)$ we have that $A\subset {\mathbb{Z}}_{\text{+}}$. Then, for $i\in {\mathbb{Z}}_{\text{+}}$, set

and set $f(A)=x$ so that clearly $f(A)\in X^{\omega }$.

To show that $f$ is injective consider $A$ and $A^{\prime }$ in $P\left({\mathbb{Z}}_{\text{+}}\right)$ where $A\ne A^{\prime }$. Without loss of generality, we can assume that there is an $i\in A$ where $i\notin A^{\prime }$, noting that of course $i\in {\mathbb{Z}}_{\text{+}}$ since $A\subset {\mathbb{Z}}_{\text{+}}$. Let $x=x=f(A)$ and $x^{\prime }=x^{\prime }=f(A^{\prime })$. Then $x_i=1\ne 0=x_i^{\prime }$ by the definition of $f$ since $i\in A$ but $i\notin A^{\prime }$. Thus clearly $f(A)=x\ne x^{\prime }=f(A^{\prime })$, which shows that $f$ is injective since $A$ and $A^{\prime }$ were arbitrary.

Now consider any $x=x\in X^{\omega }$ and define the set $A=\left\{i\in {\mathbb{Z}}_{\text{+}}\mid x_i=1\right\}$ so that clearly $A\subset {\mathbb{Z}}_{\text{+}}$ and hence $A\in P\left({\mathbb{Z}}_{\text{+}}\right)$. Let $x^{\prime }=x^{\prime }=f(A)$ and consider $i\in {\mathbb{Z}}_{\text{+}}$. If $i\in A$ then $x_i^{\prime }=1=x_i$ by the definitions of $A$ and $f$. If $i\notin A$ then $x_i\ne 1$ since otherwise $i\in A$ by definition. Since $x_i\in X=\left\{0,1\right\}$ it clearly must be that $x_i=0$. We then also have that $x_i^{\prime }=0$ by the definition of $f$, and thus $x_i=0=x_i^{\prime }$. Since $x_i=x_i^{\prime }$ in both cases and $i$ was arbitrary, it follows that $x=x^{\prime }=f(A)$. This proves that $f$ is surjective since $x$ was arbitrary.

Hence it has been shown that $f$ is a bijection as desired. □