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