Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable 
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? 
 A: 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$.
A: To remedy confusions like yours and to avoid the needless case analyses, I prefer to define $X$ to be countable if there is a surjection from $\mathbb{N}$ to $X$. This definition is equivalent to a few of the many definitions of countability, so we are not losing any generality. It is a matter of convention whether we allow finite sets to be countable or not (though, amusingly, finite sets are the only ones whose elements you could ever finish counting).
So, if $A$ and $B$ be countable, let $f:\mathbb{N}\to A$ and $g:\mathbb{N}\to B$ be surjections. Then the two sequences 
$(f(n):n\geqslant 1) = (f(1), f(2), f(3), \dotsc)$ and 
$(g(n):n\geqslant 1) = (g(1), g(2), g(3), \dotsc)$ eventually cover all of $A$ and $B$, respectively; 
we can interleave them to create a sequence that will surely cover $A\cup B$:
$$(h(n):n\geqslant 1) := (f(1), g(1), f(2), g(2), f(3), g(3), \dotsc).$$
An explicit formula for $h$ is $h(n) = f((n+1)/2)$ if $n$ is odd, and $h(n) = g(n/2)$ if $n$ is even.
A: Hint:
Case 1: Without loss of generality, suppose $A$ is finite with cardinality $n$ and $B$ is countably infinite. Then there exist bijections $f_{A}: A \to \mathbb{N}_{n} = \{1, 2, \dots, n\}$ and $f_{B}: B \to \mathbb{N}$. Is $A \cup B$ finite or countably infinite? How would you define such a bijection?
Case 2: Suppose $A$ and $B$ are both finite. Same thought process as case 1.
Case 3: Suppose $A$ and $B$ are both infinite. Same thought process as case 1.
A: First way:
If A and B are countable that you can numerate them.
$A=\{a_1,a_2,...\}$ and $B=\{b_1,b_2,...\}$.
So this means that you can numerate $A\cup B =\{a_1,b_1,a_2,b_2,...\}$.
Second way:
If A or B are finite then it is trivial. If they both are infinite, then there is a bijection between A and odd natural numbers, because they are both countable infinite. The same with B and even natural numbers. So it is not hard to define a bijection from $A\cup B$ to $\mathbb{N}$.
A: Hint: Suppose first that $A$ and $B$ are disjoint. Solve the problem.$^*$ If $A$ and $B$ are not disjoint, apply the result for disjoint sets to $(A\setminus B) \cup B$, using that $A \setminus B$ and $B$ are disjoint and $(A\setminus B) \cup B = A \cup B$.
$^*$: the finite cases are easy, you do them. Suppose $A$ and $B$ countably infinite. We have bijections $f_A: \Bbb N \to : A$, $f_B: \Bbb N \to B$. Define $f$ using $f_A$ and $f_B$ (hint inside a hint: odds and evens).
A: Here is one way. If $A=\varnothing$ or $B=\varnothing$ then the result is trivial. So we assume that nor $A$ neither $B$ are empty. We use two theorems:


*

*$\mathbb{N} \times \mathbb{N} \quad $ is countable.
This is easy to show with the mapping $(m,n) \to 2^{m-1}(2n-1)$. It is a bijection between $\mathbb{N} \times \mathbb{N}$ and $\mathbb{N}$.

*If $A \subset B$ and $B$ is countable then $A$ is countable.


Now call $\mathbb{N}_i=\{1,2, \cdots, i \}$. Write 
$A=(a_1, a_2, \cdots )$, $B=(b_1, b_2, \cdots )$.
We map $A \cup B$ to $\mathbb{N}_n \times \mathbb{N}_m$ 
with the function $f(a_i, b_j)=(i,j)$. It could happens
that $A$ is infinite and $n=\infty$, and likewise for $B$ infinite. In any case $\mathbb{N}_n \times \mathbb{N}_m \subset \mathbb{N} \times \mathbb{N}$ which is countable. Then $A \cup B$ is countable.
