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.

Leave a Reply

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