Exercise 5.4

Proof. Suppose that $m\le n$. Since $X\ne \varnothing$, there is an $x_0\in X$. Now, for any $x\in X^m$ we have that $x=\left(x_1,\dots ,x_m\right)$ where each $x_i\in X$. Then define

for $i\in \left\{1,\dots ,n\right\}$. Clearly $y_i\in X$ for every $i\in \left\{1,\dots ,n\right\}$ so that $y=\left(y_1,\dots ,y_n\right)\in X^n$. Then set $f(x)=y$ so that $f:X^m\to X^n$.

To show that $f$ is injective consider $x$ and $x^{\prime }$ in $X^m$ so that $x=\left(x_1,\dots ,x_m\right)$ and $x^{\prime }=\left(x_1^{\prime },\dots ,x_m^{\prime }\right)$ where both $x_i$ and $x_i^{\prime }$ are of course in $X$ for any $i\in \left\{1,\dots ,m\right\}$. Also suppose that $x\ne x^{\prime }$ so that it follows that there is an $i\in \left\{1,\dots ,m\right\}$ where $x_i\ne x_i^{\prime }$. Let $y=\left(y_1,\dots ,y_n\right)=f(x)$ and $y^{\prime }=\left(y_1^{\prime },\dots ,y_n^{\prime }\right)=f(x^{\prime })$. Then, since clearly $1\le i\le m$, we have $y_i=x_i\ne x_i^{\prime }=y_i^{\prime }$ by the definition of $f$. Hence we have $f(x)=y\ne y^{\prime }=f(x^{\prime })$, which shows that $f$ is injective since $x$ and $x^{\prime }$ were arbitrary. □

Proof. Consider any $x\in X^m\times X^n$ so that $x=(a,b)$ where $a\in X^m$ and $b\in X^n$. Then we have that $a=\left(a_1,\dots ,a_m\right)$ and $b=\left(b_1,\dots ,b_n\right)$ where $a_i,b_j\in X$ for every $i\in \left\{1,\dots ,m\right\}$ and $j\in \left\{1,\dots ,n\right\}$. Then define

for any $k\in \left\{1,\dots ,m+n\right\}$, noting that for $m<k\le m+n$ we have $m+1\le k\le m+n$, and hence $1\le k-m\le n$ so that $b_{k-m}$ is defined. Now set $g(x)=y=\left(y_1,\dots ,y_{m+n}\right)$ so that clearly $g(x)\in X^{m+n}$ since each $y_k\in X$. Thus $g$ is a function from $X^m\times X^n$ to $X^{m+n}$.

To show that $g$ is injective, consider any $x=(a,b)$ and $x^{\prime }=(a^{\prime },b^{\prime })$ in $X^m\times X^n$ where $x\ne x^{\prime }$. Also let $y=\left(y_1,\dots ,y_{m+n}\right)=g(x)$ and $y^{\prime }=\left(y_1^{\prime },\dots ,y_{m+n}^{\prime }\right)=g(x^{\prime })$. Since $x\ne x^{\prime }$, it must be that $a\ne a^{\prime }$ or $b\ne b^{\prime }$. In the former case we have that $a=\left(a_1,\dots ,a_m\right)$ and $a^{\prime }=\left(a_1^{\prime },\dots ,a_m^{\prime }\right)$ since they are both in $X^m$. Since $a\ne a^{\prime }$ there is an $i\in \left\{1,\dots ,m\right\}$ where $a_i\ne a_i^{\prime }$. Then, since clearly $1\le i\le m$, we have that $y_i=a_i\ne a_i^{\prime }=y_i^{\prime }$. In the latter case we have that $b=\left(b_1,\dots ,b_n\right)$ and $b^{\prime }=\left(b_1^{\prime },\dots ,b_n^{\prime }\right)$ since they are both in $X^n$. Then, since $b\ne b^{\prime }$, we have that there is an $i\in \left\{1,\dots ,n\right\}$ such that $b_i\ne b_i^{\prime }$. Let $k=m+i$ so that clearly $k-m=i$. Also $m<m+i=k\le m+n$ since $0<1\le i\le n$ so that $y_k=b_{k-m}=b_i\ne b_i^{\prime }=b_{k-m}^{\prime }=y_k^{\prime }$. Hence in both cases there is a $k\in \left\{1,\dots ,m+n\right\}$ such that $y_k\ne y_k^{\prime }$ so that $g(x)=y=\left(y_1,\dots ,y_{m+n}\right)\ne \left(y_1^{\prime },\dots ,y_{m+n}^{\prime }\right)=y^{\prime }=g(x^{\prime })$. Since $x$ and $x^{\prime }$ were arbitrary, this shows that $g$ is indeed injective.

Now consider any $y=\left(y_1,\dots ,y_{m+n}\right)\in X^{m+n}$, and define $a_i=y_i$ for any $i\in \left\{1,\dots ,m\right\}$ and $b_j=y_{m+j}$ for any $j\in \left\{1,\dots ,n\right\}$, noting that $y_{m+j}$ is defined since $0<1\le j\le n$ implies that $m<m+j\le m+n$. Then let $a=\left(a_1,\dots ,a_m\right)$, $b=\left(b_1,\dots ,b_n\right)$, and $x=(a,b)$ so that clearly $x\in X^m\times X^n$. Let $y^{\prime }=g(x)$ as defined above so that $y^{\prime }=\left(y_1^{\prime },\dots ,y_{m+n}^{\prime }\right)$. Consider any $k\in \left\{1,\dots ,m+n\right\}$. If $1\le k\le m$ then we have by the definition of $g$ that $y_k^{\prime }=a_k=y_k$. On the other hand, if $m<k\le m+n$, then we have $y_k^{\prime }=b_{k-m}=y_{m+(k-m)}=y_k$. Thus in both cases $y_k^{\prime }=y_k$ so that clearly $g(x)=y^{\prime }=\left(y_1^{\prime },\dots ,y_{m+n}^{\prime }\right)=\left(y_1,\dots ,y_{m+n}\right)=y$ since $k$ was arbitrary. This shows that $g$ is surjective since $y$ was arbitrary.

Therefore we have shown that $g$ is bijective as desired. □

Proof. First, we know that $X\ne \varnothing$ so that there is an $x_0\in X$. So, for any $x=\left(x_1,\dots ,x_n\right)\in X^n$, define

for any $i\in {\mathbb{Z}}_{\text{+}}$. Then set $h(x)=y=\left(y_1,y_2,\dots \right)$ so that clearly $h(x)\in X^{\omega }$. Thus $h$ is a function that maps $X^n$ into $X^{\omega }$.

To show that $h$ is injective, consider $x$ and $x^{\prime }$ in $X^n$ where $x\ne x^{\prime }$. Clearly we have that $x=\left(x_1,\dots ,x_n\right)$ and $x^{\prime }=\left(x_1^{\prime },\dots ,x_n^{\prime }\right)$, and let $y=\left(y_1,y_2,\dots \right)=h(x)$ and $y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=h(x^{\prime })$. Since $x\ne x^{\prime }$, there must an $i\in \left\{1,\dots ,n\right\}$ where $x_i\ne x_i^{\prime }$. Then we have $y_i=x_i\ne x_i^{\prime }=y_i^{\prime }$ by the definition of $h$ since obviously $1\le i\le n$. It then follows that $h(x)=y=\left(y_1,y_2,\dots \right)\ne \left(y_1^{\prime },y_2^{\prime },\dots \right)=y^{\prime }=h(x^{\prime })$, which shows that $h$ is injective since $x$ and $x^{\prime }$ were arbitrary. □

Proof. Consider any $x=(a,b)\in X^n\times X^{\omega }$ so that clearly $a=\left(a_1,\dots ,a_n\right)\in X^n$ and $b=\left(b_1,b_2,\dots \right)\in X^{\omega }$. Then define the sequence

for any $i\in {\mathbb{Z}}_{\text{+}}$, noting that when $n<i$ we have $n+1\le i$ so that $1\le i-n$ so that $b_{i-n}$ is defined. We then of course set $k(x)=y=\left(y_1,y_2,\dots \right)$ so that clearly $k(x)\in X^{\omega }$. Therefore $k$ is a function from $X^n\times X^{\omega }$ to $X^{\omega }$.

To show that $k$ is injective consider $x$ and $x^{\prime }$ in $X^n\times X^{\omega }$ where $x\ne x^{\prime }$. Of course we have $x=(a,b)$ and $x^{\prime }=(a^{\prime },b^{\prime })$ where $a,a^{\prime }\in X^n$ while $b,b^{\prime }\in X^{\omega }$. It then follows that $a=\left(a_1,\dots ,a_n\right)$, $a^{\prime }=\left(a_1^{\prime },\dots ,a_n^{\prime }\right)$, $b=\left(b_1,b_2,\dots \right)$, and $b^{\prime }=\left(b_1^{\prime },b_2^{\prime },\dots \right)$, where every $a_i$, $a_i^{\prime }$, $b_j$, and $b_j^{\prime }$ are in $X$ (for $i\in \left\{1,\dots ,n\right\}$ and $j\in {\mathbb{Z}}_{\text{+}}$). Also, let $y=\left(y_1,y_2,\dots \right)=k(x)$ and $y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=k(x^{\prime })$. Now, since $x\ne x^{\prime }$, we have that either $a\ne a^{\prime }$ or $b\ne b^{\prime }$. If $a\ne a^{\prime }$ then there is an $i\in \left\{1,\dots ,n\right\}$ where $a_i\ne a_i^{\prime }$. We then have that $y_i=a_i\ne a_i^{\prime }=y_i^{\prime }$ by the definition of $k$, since obviously $1\le i\le n$. If, on the other hand, $b\ne b^{\prime }$, then there is an $i\in {\mathbb{Z}}_{\text{+}}$ such that $b_i\ne b_i^{\prime }$. Then clearly $n<n+i$ since $0<i$ so that $y_{n+i}=b_{(n+i)-n}=b_i\ne b_i^{\prime }=b_{(n+i)-n}^{\prime }=y_{n+i}^{\prime }$, noting that clearly $n+i\in {\mathbb{Z}}_{\text{+}}$. Hence in either case there is an $i\in {\mathbb{Z}}_{\text{+}}$ such that $y_i\ne y_i^{\prime }$ so that $k(x)=y=\left(y_1,y_2,\dots \right)\ne \left(y_1^{\prime },y_2^{\prime },\dots \right)=y^{\prime }=k(x^{\prime })$. This shows that $k$ is injective since $x$ and $x^{\prime }$ were arbitrary.

Now consider any $y=\left(y_1,y_2,\dots \right)\in X^{\omega }$ and set $a_i=y_i$ for any $i\in \left\{1,\dots ,n\right\}$ so that clearly $a=\left(a_1,\dots ,a_n\right)\in X^n$. Also, for any $j\in {\mathbb{Z}}_{\text{+}}$, let $b_j=y_{n+j}$ so that clearly $b=\left(b_1,b_2,\dots \right)\in X^{\omega }$. Let $x=(a,b)$ so that clearly $x\in X^n\times X^{\omega }$. Now set $y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=k(x)$ as defined above. Consider any $i\in {\mathbb{Z}}_{\text{+}}$. If $1\le i\le n$ then $y_i^{\prime }=a_i=y_i$ by the definition of $k$. If $n<i$ then $y_i^{\prime }=b_{i-n}=y_{n+(i-n)}=y_i$. Hence $y_i^{\prime }=y_i$ for every $i\in {\mathbb{Z}}_{\text{+}}$ so that $k(x)=y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=\left(y_1,y_2,\dots \right)=y$, which shows that $k$ is surjective since $y$ was arbitrary.

This completes the proof that $k$ is bijective. □

Proof. Consider any $x=(a,b)\in X^{\omega }\times X^{\omega }$ so that clearly $a=\left(a_1,a_2,\dots \right)$ and $b=\left(b_1,b_2,\dots \right)$. Now define

for any $i\in {\mathbb{Z}}_{\text{+}}$. Note that $i∕2$ and $(i+1)∕2$ are in ${\mathbb{Z}}_{\text{+}}$ if $i$ is even or odd, respectively by Lemma 1 so that $y_i$ is defined. Clearly we have that $y_i\in X$ for any $i\in {\mathbb{Z}}_{\text{+}}$ so that $y=\left(y_1,y_2,\dots \right)\in X^{\omega }$. Setting $l(x)=y$, we then have that $l$ is a function from $X^{\omega }\times X^{\omega }$ to $X^{\omega }$.

To show that $l$ is injective, consider $x=(a,b)$ and $x^{\prime }=(a^{\prime },b^{\prime })$ in $X^{\omega }\times X^{\omega }$ where $x\ne x^{\prime }$. Also set $y=\left(y_1,y_2,\dots \right)=l(x)$ and $y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=l(x^{\prime })$. Since $x\ne x^{\prime }$, we have that either $a\ne a^{\prime }$ or $b\ne b^{\prime }$. If $a\ne a^{\prime }$ then there is an $i\in {\mathbb{Z}}_{\text{+}}$ such that $a_i\ne a_i^{\prime }$. Then, since clearly $2i$ is even, we have $y_{2i}=a_{(2i)∕2}=a_i\ne a_i^{\prime }=a_{(2i)∕2}^{\prime }=y_{2i}^{\prime }$. On the other hand, if $b\ne b^{\prime }$ then there is a $j\in {\mathbb{Z}}_{\text{+}}$ where $b_j\ne b_j^{\prime }$. Set $k=2j-1$, noting that

so that $k\in {\mathbb{Z}}_{\text{+}}$. Clearly also $(k+1)∕2=j$. Since obviously $k$ is odd, we have $y_k=b_{(k+1)∕2}=b_j\ne b_j^{\prime }=b_{(k+1)∕2}^{\prime }=y_k^{\prime }$. Hence in both cases we have that there is a $k\in {\mathbb{Z}}_{\text{+}}$ where $y_k\ne y_k^{\prime }$ so that $l(x)=y=\left(y_1,y_2,\dots \right)\ne \left(y_1^{\prime },y_2^{\prime },\dots \right)=y^{\prime }=l(x^{\prime })$. Since $x$ and $x^{\prime }$ were arbitrary, this shows that $l$ is injective.

Now consider any $y=\left(y_1,y_2,\dots \right)\in X^{\omega }$. For any $i\in {\mathbb{Z}}_{\text{+}}$, define $a_i=y_{2i}$ and $b_i=y_{2i-1}$, noting again that $2i-1\in {\mathbb{Z}}_{\text{+}}$ (and clearly $2i\in {\mathbb{Z}}_{\text{+}}$). Then set $a=\left(a_1,a_2,\dots \right)$, $b=\left(b_1,b_2,\dots \right)$, and $x=(a,b)$. Now let $y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=l(x)$ and consider any $i\in {\mathbb{Z}}_{\text{+}}$. If $i$ is even then we have by the definition of $l$ that $y_i^{\prime }=a_{i∕2}=y_{2(i∕2)}=y_i$. If $i$ is odd then let $j=(i+1)∕2$ so that clearly $i=2j-1$. Then $y_i^{\prime }=b_{(i+1)∕2}=b_j=y_{2j-1}=y_i$. Hence in either case we have $y_i^{\prime }=y_i$ so that $l(x)=y^{\prime }=\left(y_1^{\prime },y_2^{\prime },\dots \right)=\left(y_1,y_2,\dots \right)=y$ since $i$ was arbitrary. Since $y$ was arbitrary this shows that $l$ is surjective.

Thus we have shown that $l$ is bijective as desired. □

Proof. Consider any $x\in {\left(A^{\omega }\right)}^n$ so that $x=\left(x_1,\dots ,x_n\right)$ where $x_i\in A^{\omega }$ for any $i\in \left\{1,\dots ,n\right\}$. Then let $x_{\mathit{ij}}=x_i(j)$ for $i\in \left\{1,\dots ,n\right\}$ and $j\in {\mathbb{Z}}_{\text{+}}$ so that clearly $x_{\mathit{ij}}\in A$, from which it follows that each $x_{\mathit{ij}}\in B$ as well since $A\subset B$. Consider any $k\in {\mathbb{Z}}_{\text{+}}$. Since $n\ne 0$ (since $n\in {\mathbb{Z}}_{\text{+}}$), it follows from the Division Theorem from algebra that there are unique integers $q$ and $0\le r<n$ where $k=\mathit{qn}+r$. Suppose for a moment that $q<0$ so that $q+1\le 0$. Then we have that $k=\mathit{qn}+r<\mathit{qn}+n=(q+1)n\le 0\cdot n=0<k$ (since $k\in {\mathbb{Z}}_{\text{+}}$) since $r<n$ and $n>0$ (so that $(q+1)n\le 0\cdot n$ since $q+1\le 0$). This is of course a contradiction so it must be that $q\ge 0$. Then set $i=r+1\ge 1$ and $j=q+1\ge 1$ so that $i\in \left\{1,\dots ,n\right\}$ and $j\in {\mathbb{Z}}_{\text{+}}$. Set $y_k=x_{\mathit{ij}}$ so that clearly $y_k\in B$ since $x_{\mathit{ij}}$ is. It then follows that $y=\left(y_1,y_2,\dots \right)\in B^{\omega }$. Then set $m(x)=y$ so that clearly $m$ is a function from ${\left(A^{\omega }\right)}^n$ to $B^{\omega }$.

To show that $m$ is injective, consider any $x$ and $x^{\prime }$ in ${\left(A^{\omega }\right)}^n$ where $x\ne x^{\prime }$. Then $x=\left(x_1,\dots ,x_n\right)$ and $x^{\prime }=\left(x_1^{\prime },\dots ,x_n^{\prime }\right)$ where each $x_i$ and $x_i^{\prime }$ are in $A^{\omega }$ for $i\in \left\{1,\dots ,n\right\}$. As before set $x_{\mathit{ij}}=x_i(j)$ and $x_{\mathit{ij}}^{\prime }=x_i^{\prime }(j)$ for $i\in \left\{1,\dots ,n\right\}$ and $j\in {\mathbb{Z}}_{\text{+}}$, and also let $y=m(x)$ and $y^{\prime }=m(x^{\prime })$. Now, since $x\ne x^{\prime }$, there is an $i\in \left\{1,\dots ,n\right\}$ where $x_i\ne x_i^{\prime }$. It then follows that there is a $j\in {\mathbb{Z}}_{\text{+}}$ such that $x_{\mathit{ij}}=x_i(j)\ne x_i^{\prime }(j)=x_{\mathit{ij}}^{\prime }$. Now let $k=(j-1)n+(i-1)$ so that it follows from the definition of $m$ that $y_k=x_{\mathit{ij}}$ and $y_k^{\prime }=x_{\mathit{ij}}^{\prime }$ since the quotient $q$ and remainder $r$ are unique by the Division Theorem. Hence $y_k=x_{\mathit{ij}}\ne x_{\mathit{ij}}^{\prime }=y_k^{\prime }$ so that clearly $m(x)=y=\left(y_1,y_2,\dots \right)\ne \left(y_1^{\prime },y_2^{\prime },\dots \right)=y^{\prime }=m(x^{\prime })$. This shows that $m$ is injective as desired since $x$ and $x^{\prime }$ were arbitrary. □