If two sets are bijective to a common third set, is their union also bijective to that set? If $S_{1}\xrightarrow{\rm BIJ }\mathbb{N}$ and $S_{2}\xrightarrow{\rm BIJ }\mathbb{N}$, can I conclude that ($S_{1}\cup S_{2})\xrightarrow{\rm BIJ }\mathbb{N}$? It makes sense to me but I'm not sure how to prove it formally, and it doesn't seem so obvious that I can go from the first statement to the next without some explanation.
 A: HINT:


*

*First prove the following theorem, every infinite subset of $\Bbb N$ is bijective to $\Bbb N$.

*Next take bijections of $S_1$ with the even numbers (say $f_1$), and $S_2$ with the odd numbers (say $f_2$).

*Write $S_1\cup S_2$ as $(S_1\setminus S_2)\cup S_2$ -- this is a disjoint union. Consider the restriction of $f_1$ to $S_1\setminus S_2$ (say $f_1'$).

*Show that $f_1'\cup f_2$ is a bijection of $S_1\cup S_2$ with an infinite subset of $\Bbb N$.
A: If $S_1$ and $S_2$ are disjoint, it is easy to construct a bijection from $S_1\cup S_2 \to \Bbb N$, since $\Bbb N$ is bijective to two disjoint copies of itself. If $S_1$ and $S_2$ are not disjoint (and $f:S_1\to\Bbb N$, $g:S_2\to\Bbb N$ are bijections), the easiest proof follows from Cantor-Bernstein: There is an injection from $\Bbb N\to S_1\cup S_2$ (namely $f^{-1}$), and and injection from $S_1\cup S_2\to\Bbb N$: map $x\in S_1$ to $2f(x)$ and $x\in S_2\setminus S_1$ to $2g(x)-1$. Thus there is a bijection from $S_1\cup S_2\to\Bbb N$.
A: Hint, split the problem up into two cases.
Case 1: $S_1\cap S_2$ is finite.
Case 2: $S_1\cap S_2$ is infinite.
It is then helpful to note that $\mathbb{N}$ is the disjoint union of a finite set and a countably infinite set (that is, the first $n$ natural numbers and then the set of natural numbers greater than $n$), and it is also the disjoint union of two countably infinite sets (that is, the odd and even natural numbers).
