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

28.  Show that the union of two countable sets is countable.

Solution: We assume that A and B are two countable sets.
We will consider following cases.
Case 1:
If bothA and B are finite, then $A\cup B$ is finite and hence countable.
Case 2:
We assume that one of A and B is finite and the other is countable infinite. We assume without loss of generality that A is finite.
Since B is countably infinite, there exists a function
$f:B \rightarrow \mathbb{Z^+}$
This is a one-to-one correspondence, that is,
$f(b_i)=i$
For $b_i \epsilon B$ and $i \epsilon \mathbb{Z^+}$
Let us consider
C=A-B
Thus,
$A \cup B = B\cup C$
If $C=$Ø
Then $A \cup B = B$
This is countably infinite.
Therefore, we assume that $C\neq$Ø
Also we suppose that
$C=\left \{ c_1,c_2,...,c_n \right \}$
We consider the function
$g:B \cup C \rightarrow \mathbb{Z^+}$
Where $g(c_j)=j$
And $g(b_i)=n+i$
Clearly, g is one-to-one and onto.
Thus,$B \cup C$ is countable.
But $B \cup C = A \cup B$
So, $A \cup B$ is countable.
Case 3:
We suppose that both A and B are infinite and $A\cap B=$Ø
Since A and B are both countable, there exist functions
$p:\mathbb{Z^+} \rightarrow A$
$q:\mathbb{Z^+} \rightarrow B$
These are one-to-one correspondences.
We also consider the function
$r:\mathbb{Z^+} \rightarrow A \cup B$
Where $r(n)=p\left ( \frac{n}{2} \right )$
If n is even
And $r(n)=q\left ( \frac{n+1}{2} \right )$
If n is odd
Since p,q are one-to-one, so r is also one-to-one.
Similarly, since p,q are onto, so r is also onto.
Therefore, r is a one-to-one correspondence, and hence,r is countable.
Case 4:
We suppose that both A and B are infinite and $A \cap B=$Ø
We assume that C=B-A
Then,
$A \cup B= A \cup C$
And
$A \cap C=$Ø
If C is countably infinite, then
$A \cup B= A \cup C$
Is countable by the previous case
If C is finite, then
$A \cup B= A \cup C$
Is countable by case 2
Therefore, $A \cup B$ is countable.

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

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

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

25. Show that the set of all integers greater than -100 is countable.

Solution: In order to prove that the set of all integers greater than -100 is countable, it suffices to prove that the set of integers $\mathbb{Z}$ is countable. This follows from the fact that the subset of a countable set is countable.

We can the list the integers in a sequence
0,1,-1,2,-2,3,-3,…
We define a function
$f:\mathbb{N} \rightarrow \mathbb{Z}$

This is defined as
$f(n)=\left\{\begin{matrix} \frac{n}{2}&\text{n is even} \\ \frac{-(n-1)}{2}& \text{n is odd}\end{matrix}\right.$

We now show that $f$ is a bijection.
First we show that it is injective by case analysis on the parity of $\mathbb{N}$
Case 1
If $m,n$ are two even natural numbers
Then
$f(m)=\frac{m}{2}$
$f(n)=\frac{n}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Case 2
If $m,n$ are two odd natural numbers
Then
$f(m)=-\frac{m-1}{2}$
$f(n)=-\frac{n-1}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Therefore $f$ is injective.
We now show that $f$ is surjective by case analysis on the sign of some integer $t$ in $\mathbb{Z}$
Case 1
If $t$ is positive, then $t$ will appear in an even position in the sequence.
Thus,
$f(2k)=\frac{2k}{2}$
$=t$
With
$t=k$
This implies that for every positive value $t$ in $\mathbb{Z}$ there is a natural number $2k$
Case 2
If $t$ is negative, then $t$ will appear in an odd position in the sequence.
Thus,
$f(2k-1)=-\frac{(2k-1)-1}{2}$
$=t$
With
$t=-k$
This implies that for every negative value $t$ in $\mathbb{Z}$ there is a natural number $2k-1$
Therefore, $f$ is surjective
Hence, $\mathbb{Z}$ is countable set.
Now we define the sequence
$a_n=n-100$
$>-100$
For $n \in \mathbb{N}$
This is clearly a subset of $\mathbb{Z}$ and so is countable.