Exercise 9.4

Proof. Let ${\left\{A_n\right\}}_{n\in J}$ be an indexed family of countable sets, where the index set $J$ is $\left\{1,\dots ,N\right\}$ or ${\mathbb{Z}}_{\text{+}}$. Assume that each set $A_n$ is nonempty for convenience since this does not change anything. Now, for each $n\in J$, let $B_n$ be the set of surjective functions from ${\mathbb{Z}}_{\text{+}}$ to $A_n$. Since each $A_n$ is countable, it follows from Theorem 7.1 that $B_n\ne \varnothing$. Then, by the axiom of choice, the collection ${\left\{B_n\right\}}_{n\in J}$ has a choice function $c$ such that $c(B_n)\in B_n$ for every $n\in J$.

Now set $f_n=c(B_n)$ for every $n\in J$ so that $f_n\in B_n$ and hence is a surjection from ${\mathbb{Z}}_{\text{+}}$ into $A_n$. Since $J$ is countable, there is also a surjection $g:{\mathbb{Z}}_{\text{+}}\to J$ by Theorem 7.1. Then define $h:{\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}\to {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in J}{A}_n$ by $h(k,m)=f_{g(k)}(m)$ for $k,m\in {\mathbb{Z}}_{\text{+}}$.

We now show that $h$ is surjective. So consider any $a\in {\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in J}{A}_n$ so that $a\in A_n$ for some $n\in J$. Since $g:{\mathbb{Z}}_{\text{+}}\to J$ is surjective, there is a $k\in {\mathbb{Z}}_{\text{+}}$ where $g(k)=n$. Also, since $f_n:{\mathbb{Z}}_{\text{+}}\to A_n$ is surjective, there is an $m\in {\mathbb{Z}}_{\text{+}}$ where $f_n(m)=a$. We then have by definition that

which shows that $h$ is surjective since $a$ was arbitrary.

Lastly, since ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ is countable by Example 7.2, there is a bijection $h^{\prime }:{\mathbb{Z}}_{\text{+}}\to {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. It then follows that $h\circ h^{\prime }$ is a surjection from ${\mathbb{Z}}_{\text{+}}$ to ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in J}{A}_n$, which shows that ${\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{n\in J}{A}_n$ is countable again by Theorem 7.1. □