**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.

** **

wohh exactly what I was looking for, regards for putting up.

Hi there! Such a good write-up, thanks!

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

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

A must read article!

useful reference