Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable.
I'm really confused because I'm not sure if $A$ and $B$ are finite or infinite. If I have to consider every case, then there will be $4$ cases. Also I'm not sure if $A$ and $B$ are disjoint. If they are not, then their common element would show up only once in $A\cup B$. Is there a way to avoid dealing with all these as separate cases?
Best Answer
No need to separate it in different cases. You can use the fact that a set $A$ is countable if there is an injective function $f : A \rightarrow \mathbb{N}$. Let $g$ and $h$ are these injective functions for $A$ and $B$ respectively. Then you can build an injective function $f$ from $A \cup B$ to $\mathbb{N}$ this way : $f(x) = 2g(x)$ if $x \in A$ and $f(x) = 2h(x)+1$ if $x \in B \backslash A$.