# Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.26

26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.

Solution:

We have to show that the set of all rational numbers of the form n/5 where n is an integer, is countable.
We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection $f: \mathbb{Z^+} \rightarrow A$
(c) there exists an injection $g: A \rightarrow \mathbb{Z^+}$

Proof
$(a) \Rightarrow (b)$
If A is countably infinite, then there exists a bijection
$f: \mathbb{Z^+} \rightarrow A$
And then (b) follows
If A is finite, then there is a bijection
$h:\left \{ 1,...,n \right \} \rightarrow A$
For some n
Then the function $f: \mathbb{Z^+} \rightarrow A$ defined by
$f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.$
Is a surjection
$(b) \Rightarrow (c)$
We assume that $f: \mathbb{Z^+} \rightarrow A$ is a surjection. We claim that there is an injection $g: A \rightarrow \mathbb{Z^+}$
To define g we note that if
$a\epsilon A$
Then
$f^{-1}(\left \{a \right \})\neq \phi$
Hence, we set
$g(a)=min f^{-1}(\left \{a \right \})$
Now we note that if
$a \neq a'$
Then
$f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi$
Implies
$min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})$
Hence
$g(a)\neq g(a')$
And $g: A \rightarrow \mathbb{Z^+}$ is an injection
$(c) \Rightarrow (a)$
We assume that $g: A \rightarrow \mathbb{Z^+}$ is an injection. We want to show that A is countable.
Since
$g:A \rightarrow g(A)$
Is a bijection and
$g(A)\subset \mathbb{Z^+}$
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We define the function
$f:\mathbb{Z} \times \mathbb{Z^+}\rightarrow \mathbb{Q}$
As
f(n,5)=n/5
Since each rational number is of the form n/5 for some $n \epsilon \mathbb{Z}$, it follows that f is surjective.
Since $\mathbb{Z} \times \mathbb{Z^+}$ is countably infinite, that is, the Cartesian product of countable sets is countable, it follows from part (b) of the above proposition and replacing $\mathbb{Z^+}$ by an arbitrary countably infinite set (using composition of functions), that rational numbers of the form n/5 is countable.

## 4 Replies to “Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.26”

1. That is a good tip particularly to those fresh to the blogosphere.

Short but very accurate info… Thank you for sharing this one.