##### Claim

The union of two countable sets is countable.

##### Proof

We will prove this in three cases.

1. Let both $A$ and $B$ be finite. Then $A \cup B$ is finite, and therefore is also count-

able.

2. Assume one of $A$ and $B$ is finite and the other is countably infinite. Assume that $A$ is finite. Since $B$ is countably infinite, there exists a function $f : B \to \mathbb{N}$ which is a one-to-one correspondence. For $b_i \in B$ and $i \in \mathbb{N}$, let $f(b_i) = i$. Let $C = A-B$. Therefore $A \cup B = B \cup C$. If

$C$ is an empty set , then $A \cup B = B \cup C$ and is countably infinite. If $C$ is a non-empty set, let $C = \{{c_1, c_2, \dots c_n\}$. Define a new function $g : B \cup C \to \mathbb{N}$ via $g(c_j) = j$ and $g(b_i) = n + i$. Therefore $g$ is a one to one correspondence. Therefore $B \cup C$ is countable and $B \cup C = A \cup B$, so $A \cup B$ is also countable.

3. Let $A$ and $B$ be infinite. Let $C = A-B$. Then $A \cup B = A \cup C$. If $C$ is countably infinite then $A \cup B = A \cup C$ is countable by part 2. If $C$ is finite then $A \cup B = A \cup C$ is also finite and therefore countable.

$\blacksquare$