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”

Leave a Reply

Your email address will not be published. Required fields are marked *