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