Exercise 7.5

Solution for $(j)$. We claim $J$ is countable. Consider $I={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n=0}^{\infty }{I}_n$ where $I_n$ is the set of sequences with $n$ elements. Each $I_n$ is countable by Theorem $7.6$ so $I$ is countable by Theorem $7.5$. Identifying each finite subset in $J$ with the finite sequence with the same elements in increasing order, we see that $J\subseteq I$, and so $J$ is countable by Corollary $7.3$. □

Proof. For any $f\in A$, clearly the mapping $g(f)=(f(0),f(1))$ is a bijection from $A$ to ${{\mathbb{Z}}_{\text{+}}}^2$. Since ${{\mathbb{Z}}_{\text{+}}}^2$ is a finite cartesian product of countable sets, it follows that it is also countable by Theorem 7.6. Hence there is a bijection $h:{{\mathbb{Z}}_{\text{+}}}^2\to {\mathbb{Z}}_{\text{+}}$. It is then obvious that $h\circ g$ is a bijection from $A$ to ${\mathbb{Z}}_{\text{+}}$ so that $A$ is countable. □

Proof. By the definition of ${{\mathbb{Z}}_{\text{+}}}^n$, $B_n={{\mathbb{Z}}_{\text{+}}}^n$, which is clearly a finite cartesian product of countable sets. Thus $B_n$ is countable by Theorem 7.6. □

Proof. Since $n$ was arbitrary in part (b), we showed that $B_n$ is countable for any $n\in {\mathbb{Z}}_{\text{+}}$. Thus $C={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in {\mathbb{Z}}_{\text{+}}}{B}_n$ is a countable union of countable sets, which is itself also countable by Theorem 7.5 as desired. □

Proof. We proceed to show, as in Theorem 7.7, that any function $g:{\mathbb{Z}}_{\text{+}}\to D$ is not surjective. So denote

where of course each $x_{\mathit{nm}}\in {\mathbb{Z}}_{\text{+}}$ since $x_n\in D$ and so is a function from ${\mathbb{Z}}_{\text{+}}$ to ${\mathbb{Z}}_{\text{+}}$. Now set

so that clearly $y=y$ is an element of $D$. Now consider any $n\in {\mathbb{Z}}_{\text{+}}$. If $x_{\mathit{nn}}=0$ then $y_n=1\ne 0=x_{\mathit{nn}}$, and if $x_{\mathit{nn}}\ne 0$ then $y_n=0\ne x_{\mathit{nn}}$. Thus clearly $g(n)=x_n\ne y$ since the $n$th element of each differs. This shows that $g$ cannot be surjective since $y\in D$ and $n$ was arbitrary. It then follows from Theorem 7.1 that $D$ is not countable. □

Proof. For brevity define $X=\left\{0,1\right\}$. First let $F_N$ be the set of all eventually zero functions $f:{\mathbb{Z}}_{\text{+}}\to X$ that are zero for $n\ge N$, where of course $N\in {\mathbb{Z}}_{\text{+}}$. Then clearly $F={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{N\in {\mathbb{Z}}_{\text{+}}}{F}_N$.

We show that each $F_N$ is countable. So consider any $N\in {\mathbb{Z}}_{\text{+}}$. If $N=1$ then clearly $f:{\mathbb{Z}}_{\text{+}}\to X$ defined by $f(n)=0$ for $n\in {\mathbb{Z}}_{\text{+}}$ (which could be denoted $(0,0,\dots )$) is the only element of $F_N=F_1$ so that $f_N$ is clearly finite and therefore countable. If $N>1$ then for $x=\mathit{xN}-1\in X^{N-1}$ define

for $n\in {\mathbb{Z}}_{\text{+}}$. It then trivial to show that $g$ defined by $g(x)=y=y$ is a bijection from $X^{N-1}$ to $F_N$. Now, since $X=\left\{0,1\right\}$ is finite, $X^{N-1}$ is finite by Corollary 6.8. Since this is in bijective correspondence with $F_N$, it follows that it must also be finite and therefore countable.

Thus $F={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{N\in {\mathbb{Z}}_{\text{+}}}{F}_N$ is a countable union of countable sets, and so is countable by Theorem 7.5 as desired □

Proof. For $N\in {\mathbb{Z}}_{\text{+}}$, let $H_N$ be the set of functions $f:{\mathbb{Z}}_{\text{+}}\to {\mathbb{Z}}_{\text{+}}$ such that $f(n)$ is constant for $n\ge N$. Thus clearly $H={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{N\in {\mathbb{Z}}_{\text{+}}}{H}_N$.

We show that each $H_N$ is countable. So consider $N\in {\mathbb{Z}}_{\text{+}}$. For any $x=\mathit{xN}\in {{\mathbb{Z}}_{\text{+}}}^N$ define

for $n\in {\mathbb{Z}}_{\text{+}}$, and set $g(x)=y=y$. It is then a simple matter to show that $g$ is a bijection from ${{\mathbb{Z}}_{\text{+}}}^N$ to $H_N$. Then, since ${{\mathbb{Z}}_{\text{+}}}^N$ is a finite product of countable sets, it is countable by Theorem 7.6. Hence $H_N$ must also be countable since there is a bijective correspondence between them.

Thus $H={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{N\in {\mathbb{Z}}_{\text{+}}}{H}_N$ is the countable union of countable sets so that it must also be countable by Theorem 7.5. □

Proof. First, let $J_n$ denote the set of $n$-element subsets of ${\mathbb{Z}}_{\text{+}}$ (for $n\in \mathit{pints}$), and let $J_0=\left\{\text{∅}\right\}$ since $\text{∅}$ is the only “zero-element” subset of ${\mathbb{Z}}_{\text{+}}$. Clearly then $J={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in {\mathbb{Z}}_{\text{+}}\cup \left\{0\right\}}{J}_n$. Obviously, $J_0$ is finite and therefore countable. Next, we show that $J_n$ is countable for any $n\in {\mathbb{Z}}_{\text{+}}$.

So consider any such $n\in {\mathbb{Z}}_{\text{+}}$. Clearly ${{\mathbb{Z}}_{\text{+}}}^n$ is countable by Theorem 7.6 since it is a finite product of countable sets. Hence there is a bijection $f:{{\mathbb{Z}}_{\text{+}}}^n\to {\mathbb{Z}}_{\text{+}}$. We now construct an injective function $g:J_n\to {{\mathbb{Z}}_{\text{+}}}^n$. For any $X\in J_n$, we can choose a bijection $h:X\to \left\{1,\dots ,n\right\}$ since it has $n$ elements. Since $X\subset {\mathbb{Z}}_{\text{+}}$, clearly $h^{-1}\in {{\mathbb{Z}}_{\text{+}}}^n$, so set $g(X)=h^{-1}$. To show that $g$ is injective, consider $X$ and $X^{\prime }$ in $J_n$ where $X\ne X^{\prime }$. Without loss of generality, we can assume that there is an $x\in X$ where $x\notin X^{\prime }$. Let $h$ and $h^{\prime }$ be the chosen bijections from $X$ and $X^{\prime }$, respectively, to $\left\{1,\dots ,n\right\}$ so that by definition $g(X)=h^{-1}$ and $g(X^{\prime })={h^{\prime }}^{-1}$. Now let $k=h(x)$ so that $h^{-1}(k)=x$. It has to be that ${h^{\prime }}^{-1}(k)\ne x$ since otherwise $x$ would be in $X^{\prime }$. Hence $h^{-1}(k)=x\ne {h^{\prime }}^{-1}(k)$, which shows that $g(X)=h^{-1}\ne {h^{\prime }}^{-1}=g(X^{\prime })$. Thus $g$ is injective since $X$ and $X^{\prime }$ were arbitrary. It then follows that $f\circ g$ is an injective function from $J_n$ to ${\mathbb{Z}}_{\text{+}}$ so that $J_n$ must be countable by Theorem 7.1.

Since $n$ was arbitrary, this shows that $J_n$ is countable for any $n\in {\mathbb{Z}}_{\text{+}}$. From this, it follows from Theorem 7.5 that $J={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in {\mathbb{Z}}_{\text{+}}\cup \left\{0\right\}}{J}_n$ is also countable since it is clearly a countable union of countable sets. □