Exercise 7.1

Proof. First, by Example 7.1, the set of integers $\mathbb{Z}$ is countably infinite so that there is a bijection $f$ from $\mathbb{Z}$ to ${\mathbb{Z}}_{\text{+}}$. We construct a bijection $g$ from $\mathbb{Z}\times \mathbb{Z}$ to ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$. For any $(a,b)\in \mathbb{Z}\times \mathbb{Z}$ define $g(a,b)=(f(a),f(b))$, noting that clearly $g(a,b)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ since ${\mathbb{Z}}_{\text{+}}$ is the range of $f$. Hence $g$ is a function from $\mathbb{Z}\times \mathbb{Z}$ to ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$.

It is easy to show that $g$ is bijective. First, consider any $(a,b)$ and $(a^{\prime },b^{\prime })$ in $\mathbb{Z}\times \mathbb{Z}$ where $(a,b)\ne (a^{\prime },b^{\prime })$ so that $a\ne a^{\prime }$ or $b\ne b^{\prime }$. If $a\ne a^{\prime }$ then $f(a)\ne f(a^{\prime })$ since $f$ is bijective (and therefore injective). Thus we have that $g(a,b)=(f(a),f(b))\ne (f(a^{\prime }),f(b^{\prime }))=g(a^{\prime },b^{\prime })$. A similar argument shows the same result when $b\ne b^{\prime }$. Since $(a,b)$ and $(a^{\prime },b^{\prime })$ were arbitrary, this shows that $g$ is injective.

Now consider any $(c,d)\in {\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ so that $c,d\in {\mathbb{Z}}_{\text{+}}$. Since $f$ is surjective (since it is a bijection) there are $a,b\in \mathbb{Z}$ where $f(a)=c$ and $f(b)=d$. We then clearly have that $g(a,b)=(f(a),f(b))=(c,d)$ so that $g$ is surjective $(c,d)$ was arbitrary.

Therefore $g$ is a bijection. Now, we know from Corollary 7.4 that ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ is countably infinite so that there must be a bijection $h$ from ${\mathbb{Z}}_{\text{+}}\times {\mathbb{Z}}_{\text{+}}$ to ${\mathbb{Z}}_{\text{+}}$. It then follows that $h\circ g$ is bijection from $\mathbb{Z}\times \mathbb{Z}$ to ${\mathbb{Z}}_{\text{+}}$, which shows the desired result by definition. □

Proof. First we define a straightforward function $f$ from $\mathbb{Z}\times \mathbb{Z}$ to $\mathbb{Q}$. First consider any $(m,n)\in \mathbb{Z}\times \mathbb{Z}$. If $n\ne 0$ then let $q=m∕n$. If $n=0$ then set $q=0$. Setting $f(m,n)=q$ we clearly have that $f$ is a function from $\mathbb{Z}\times \mathbb{Z}$ to $\mathbb{Q}$. Now consider any rational $q$ so that by definition there are integers $m$ and $n$ where $q=m∕n$. It then of course follows that $f(m,n)=m∕n=q$, which shows that $f$ is surjective since $q$ was arbitrary.

Now, from Lemma 1 we know that $\mathbb{Z}\times \mathbb{Z}$ is countably infinite so that there is a bijection $g$ from $\mathbb{Z}\times \mathbb{Z}$ to ${\mathbb{Z}}_{\text{+}}$. Hence $g^{-1}$ is a bijection from ${\mathbb{Z}}_{\text{+}}$ to $\mathbb{Z}\times \mathbb{Z}$. It then follows that the function $f\circ g^{-1}$ is a surjective function from ${\mathbb{Z}}_{\text{+}}$ to $\mathbb{Q}$. From this, it follows from Theorem 7.1 that $\mathbb{Q}$ is countable. Since ${\mathbb{Z}}_{\text{+}}$ is a subset of $\mathbb{Q}$, it has to be that $\mathbb{Q}$ is infinite, and hence must be countably infinite. □