Exercise 5.2

Main Problem.

(a)

Proof. For brevity, let $X=A_1\times \cdots \times A_n$ and $Y=\left(A_1\times \cdots \times A_{n-1}\right)\times A_n$. Suppose that $n>1$ so that $X$ and $Y$ make sense. We construct a bijective function $f:X\to Y$. For any $x=\left(x_1,\dots ,x_n\right)\in X$ we have that $x_i\in A_i$ for $1\le i\le n$. So set $f(x)=(\left(x_1,\dots ,x_{n-1}\right),x_n)$, which is clearly an element of $Y$.

To see that $f$ is injective consider $x=\left(x_1,\dots ,x_n\right)$ and $y=\left(y_1,\dots ,y_n\right)$ in $X$ where $x\ne y$. It then follows that there must be an $i\in \mathit{\mathbb{Z}finn}$ where $x_i\ne y_i$. Let $x^{\prime }=\left(x_1,\dots ,x_{n-1}\right)$ and $y^{\prime }=\left(y_1,\dots ,y_{n-1}\right)$ so that clearly $f(x)=(x^{\prime },x_n)$ and $f(y)=(y^{\prime },y_n)$. Now, if $i=n$, then clearly $f(x)=(x^{\prime },x_n)\ne (y^{\prime },y_n)=f(y)$ since $x_n=x_i\ne y_i=y_n$. On the other hand, if $i\ne n$ then it has to be that $i<n$, and hence $i\le n-1$. It then follows that $x^{\prime }=\left(x_1,\dots ,x_{n-1}\right)\ne \left(y_1,\dots ,y_{n-1}\right)=y^{\prime }$ so that then $f(x)=(x^{\prime },x_n)\ne (y^{\prime },y_n)=f(y)$ again. Since $x$ and $y$ were arbitrary, this shows that $f$ is indeed injective.

Now consider any $y=(\left(x_1,\dots ,x_{n-1}\right),x_n)\in Y$ and let $x=\left(x_1,\dots ,x_n\right)$. It should be obvious that both $x\in X$ and $f(x)=y$ so that $f$ is surjective. Hence $f$ is a bijective function as desired. □

(b)

Proof. First let $A=A_1\times A_2\times \cdots$ and $B=B_1\times B_2\times \cdots$. We construct a bijective $f:A\to B$. So, for any $a\in A$, we have that $a=\left(a_1,a_2,\dots \right)$, where $a_i\in A_i$ for any $i\in {\mathbb{Z}}_{\text{+}}$. Then, for any $i\in {\mathbb{Z}}_{\text{+}}$, define $b_i=(a_{2i-1},a_{2i})$ so that clearly $b_i\in A_{2i-1}\times A_{2i}=B_i$. We then have that $b=\left(b_1,b_2,\dots \right)\in B_1\times B_2\times \cdots =B$. So set $f(a)=b$ so that $f$ is a function from $A$ to $B$.

To show that $f$ is injective, consider $a=\left(a_1,a_2,\dots \right)$ and $a^{\prime }=\left(a_1^{\prime },a_2^{\prime },\dots \right)$ in $A$ where $a\ne a^{\prime }$. For each $i\in {\mathbb{Z}}_{\text{+}}$, define $b_i=(a_{2i-1},a_{2i})$ and $b_i^{\prime }=(a_{2i-1}^{\prime },a_{2i}^{\prime })$ as above and set $b=\left(b_1,b_2,\dots \right)$ and $b^{\prime }=\left(b_1^{\prime },b_2^{\prime },\dots \right)$ so that clearly $f(a)=b$ and $f(a^{\prime })=b^{\prime }$. Since $a\ne a^{\prime }$, it follows that there must be an $i\in {\mathbb{Z}}_{\text{+}}$ where $a_i\ne a_i^{\prime }$.

Case: $i$ is even. Then let $j=i∕2$ so that $j\in {\mathbb{Z}}_{\text{+}}$ by Lemma 1 . We also clearly have that $i=2j$ so that $b_j=(a_{2j-1},a_{2j})\ne (a_{2j-1}^{\prime },a_{2j}^{\prime })=b_j^{\prime }$ since $a_{2j}=a_i\ne a_i^{\prime }=a_{2j}^{\prime }$.

Case: $i$ is odd. Then let $j=(i+1)∕2$ so that $j\in {\mathbb{Z}}_{\text{+}}$ by Lemma 1 . We then clearly have that $i=2j-1$ so that $b_j=(a_{2j-1},a_{2j})\ne (a_{2j-1}^{\prime },a_{2j}^{\prime })=b_j^{\prime }$ since $a_{2j-1}=a_i\ne a_i^{\prime }=a_{2j-1}^{\prime }$.

Hence in all cases, we have that there is a $j\in {\mathbb{Z}}_{\text{+}}$ where $b_j\ne b_j^{\prime }$. It then follows that $f(a)=b=\left(b_1,b_2,\dots \right)\ne \left(b_1^{\prime },b_2^{\prime },\dots \right)=b^{\prime }=f(a^{\prime })$ so that $f$ is injective since $a$ and $a^{\prime }$ were arbitrary.

Lastly, to show that $f$ is surjective, consider any $b\in B$ so that $b=\left(b_1,b_2,\dots \right)$ where $b_i\in B_i=A_{2i-1}\times A_{2i}$ for every $i\in {\mathbb{Z}}_{\text{+}}$. Then, for any $i\in {\mathbb{Z}}_{\text{+}}$, $b_i=(a_i^{\prime },a_i^{\mathit{\prime \prime }})$ where $a_i^{\prime }\in A_{2i-1}$ and $a_i^{\mathit{\prime \prime }}\in A_{2i}$. So consider any $j\in {\mathbb{Z}}_{\text{+}}$. If $j$ is even, then $i=j∕2\in {\mathbb{Z}}_{\text{+}}$ by Lemma 1 . Clearly also $j=2i$. So, define $a_j=a_i^{\mathit{\prime \prime }}$ so that $a_j=a_{2i}=a_i^{\mathit{\prime \prime }}\in A_{2i}=A_j$. On the other hand, if $j$ is odd, then $i=(j+1)∕2\in {\mathbb{Z}}_{\text{+}}$ again by Lemma 1 . Then clearly $j=2i-1$. So, here let $a_j=a_i^{\prime }$ so that $a_j=a_{2i-1}=a_i^{\prime }\in A_{2i-1}=A_j$. Hence $a_j\in A_j$ for all $j\in {\mathbb{Z}}_{\text{+}}$ so that $a=\left(a_1,a_2,\dots \right)\in A$. Then, for any $i\in {\mathbb{Z}}_{\text{+}}$, we have $b_i=(a_i^{\prime },a_i^{\mathit{\prime \prime }})=(a_{2i-1},a_{2i})\in A_{2i-1}\times A_{2i}=B_i$ so that by definition $f(a)=b=\left(b_1,b_2,\dots \right)$. This shows that $f$ is surjective since $b$ was arbitrary.

This completes the proof that $f$ is bijective so that the desired result follows. □