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

## 2 Replies to “Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.28”

1.  Alice says:

Hello, I followed a link to your blog and I like this post in particular. You put forward some educated arguments.

2.  Raleigh Mosakowski says:

Very good.