Exercise 7.7

Proof. Since $A_2\ne \varnothing$, there is an $a_2\in A_2$. Since we know they exist, let $f_A:A_1\to A_2$ and $f_B:B_1\to B_2$ be injections. We construct an injection $F:A_1^{B_1}\to A_2^{B_2}$. So, for any $g\in A_1^{B_1}$, define $F(g)=h$, where $h\in A_2^{B_2}$ is defined by

for $b\in B_2$, noting that ${f_B}^{-1}$ is a function with domain $f_B(B_1)$ since it is injective.

To show that $F$ is injective, consider $g_1,g_2\in A_1^{B_1}$ where $g_1\ne g_2$. Then there is a $b_1\in B_1$ where $g_1(b_1)\ne g_2(b_1)$. Let $b_2=f_B(b_1)$ so that clearly $b_2\in f_B(B_1)$ and $b_1={f_B}^{-1}(b_2)$. Then clearly

since $g_1(b_1)\ne g_2(b_1)$ and $f_A$ is injective. Thus $F(g_1)\ne F(g_2)$, which shows that $F$ is injective since $g_1$ and $g_2$ were arbitrary. □

Proof. We construct a bijection $F:A^{B\times C}\to {(A^B)}^C$. So, for any $f\in A^{B\times C}$, we have that $f:B\times C\to A$. Define $g:C\to A^B$ by $g(c)=h$ for any $c\in C$, where $h:B\to A$ is defined by $h(b)=f(b,c)$. Then assign $F(f)=g$.

To show that $F$ is injective, consider $f,f^{\prime }\in A^{B\times C}$ where $f\ne f^{\prime }$. Then there is a $(b,c)\in B\times C$ where $f(b,c)\ne f^{\prime }(b,c)$. Also let $g=F(f)$, $g^{\prime }=F(f^{\prime })$, $h=g(c)$, and $h^{\prime }=g^{\prime }(c)$. Then, by definition, we have $h(b)=f(b,c)\ne f^{\prime }(b,c)=h^{\prime }(b)$ so that $g(c)=h\ne h^{\prime }=g^{\prime }(c)$. From this, it follows that $F(f)=g\ne g^{\prime }=F(f^{\prime })$, which shows that $F$ is injective since $f$ and $f^{\prime }$ were arbitrary.

Now consider any $g\in {(A^B)}^C$ and any $(b,c)\in B\times C$. Let $h=g(c)\in A^B$, and then assign $f(b,c)=h(b)$. Clearly then $f:B\times C\to A$ so that $f\in A^{B\times C}$. So let $g^{\prime }=F(f)$ and consider any $c\in C$. Let $h=g(c)$ and $h^{\prime }=g^{\prime }(c)$ so that $h^{\prime }(b)=f(b,c)$ by the definition of $F$. Consider any $b\in B$ so that $h(b)=f(b,c)=h^{\prime }(b)$ by the definition of $f$. Since $b$ was arbitrary, this shows that $g(c)=h=h^{\prime }=g^{\prime }(c)$. Since $c$ was also arbitrary, this shows that $F(f)=g^{\prime }=g$. Lastly, since $g$ was arbitrary, this shows that $F$ is surjective. □

Proof. First consider any $f\in E=X^{{\mathbb{Z}}_{\text{+}}}$. Then define $g(n)=f(n)+1$ for $n\in {\mathbb{Z}}_{\text{+}}$ so that clearly $g\in {{\mathbb{Z}}_{\text{+}}}^{{\mathbb{Z}}_{\text{+}}}=D$. Now define the function $h:E\to D$ by $h(f)=g$. It is then trivial to show that $h$ is an injection.

Now, for $n\in {\mathbb{Z}}_{\text{+}}$, define $x_n=1$ and $x_i=0$ when $i\in {\mathbb{Z}}_{\text{+}}$ and $i\ne n$. Clearly then $x=x\in X^{{\mathbb{Z}}_{\text{+}}}$, and it is easily shown that the function defined by $f(n)=x$ is an injection from ${\mathbb{Z}}_{\text{+}}$ to $X^{{\mathbb{Z}}_{\text{+}}}$ Also clearly the identity function on ${\mathbb{Z}}_{\text{+}}$ is an injection since it is a bijection. It then follows from Lemma 1 that there is an injection $f_1:{{\mathbb{Z}}_{\text{+}}}^{{\mathbb{Z}}_{\text{+}}}\to {(X^{{\mathbb{Z}}_{\text{+}}})}^{{\mathbb{Z}}_{\text{+}}}$, noting that clearly $X^{{\mathbb{Z}}_{\text{+}}}\ne \varnothing$.

We presently have that there is a bijection $f_2:{(X^{{\mathbb{Z}}_{\text{+}}})}^{{\mathbb{Z}}_{\text{+}}}\to X^{{\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}}$ by Lemma 2 , which is of course also an injection. Finally, since ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ has the same cardinality as ${\mathbb{Z}}_{\text{+}}$ (by Corollary 7.4), it follows that there is an injection from ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ to ${\mathbb{Z}}_{\text{+}}$. Since also the identity function on $X$ is an injection, we have again that there is an injection $f_3:X^{{\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}}\to X^{{\mathbb{Z}}_{\text{+}}}$ by Lemma 1 . Thus clearly then $f_3\circ f_2\circ f_1$ is an injection from ${{\mathbb{Z}}_{\text{+}}}^{{\mathbb{Z}}_{\text{+}}}=D$ to $X^{{\mathbb{Z}}_{\text{+}}}=E$.

Therefore, since there is an injection from $E$ to $D$ as well as from $D$ to $E$, it follows from Exercise 7.6 part (b) that $D$ and $E$ have the same cardinality as desired. □