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

27. Show that the set of all numbers of the form $a+b\sqrt{2}$ where a and b are integers, is countable.

Solution: 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 now show that the set of all numbers of the form $a+b\sqrt{2}$ where a,b are integers, is countable.
By the above proposition it suffices to construct an injective function
$f:\mathbb{Z^+}\times \mathbb{Z^+} \rightarrow \mathbb{Z^+}$
We define it as
$f(a,b)=2^a3^b$
We assume that
$2^a3^b=2^c3^d$
If
a<c
Then
$3^b=2^{c-a}3^d$
The left side of this equality is an odd number where as the right side is an even number implying
a=c
And
$3^b=3^d$
Then also
b=d
Hence, f is injective and so set of all numbers of the form $a+b\sqrt{2}$ where a,b are integers, is countable.