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”

Leave a Reply

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