Proving that a union of countably infinite sets is countably infinite I am solving Real Analysis over the summer, and this is an exercise in the preliminaries. I need to start off with 2 countably infinite sets and prove that their union is countably infinite as well. I was hoping for some help with this. The book advises to replace the second set, $A_2$, with $B$, where $B=A_2$ \ $A_1$ since $A_1 \cup B$ = $A_1 \cup A_2$ but $A_1$ and $B$ are disjoint, which makes things easier. Can I just map all the odd elements to $\frac{n-1}{2}$ and even elements to $-\frac{n}{2}$? What if the members of the set aren't numbers but some objects, yet there are countably infinitely many of them? Thanks!
 A: Even if the members aren't numbers, since the sets are assumed to be countable infinite, you can essentially label them with natural numbers. Here's how I would go about it. Let $X$ and $Y$ be disjoint, countably infinite sets. (You can prove to yourself that such sets exist.)
Now $X\sim\omega$ and $Y\sim\omega$, so there exist bijections $f\colon X\to\omega$ and $g\colon Y\to\omega$. You can define a new map $\pi\colon X\cup Y\to\omega$ by
$$
\pi(x)=
\begin{cases}
2f(x) &\text{if } x\in X\\
2g(x)+1 &\text{if } x\in Y
\end{cases}
$$
which is well defined since $X\cap Y=\emptyset$. But $\pi$ is injective, since no natural number is both even and odd. So $X\cup Y$ is in bijection with an infinite subset of $\omega$, namely the image of $\pi$, and is thus countably infinite. You can adapt this idea to sets that aren't disjoint with what you mention in your question.
A: The tip in the book is actually very good. We can assume that $A_1$ and $A_2$ are disjoint because otherwose, we can replace $A_2$ by $A_2\setminus A_1$: If $A_2$ becomes finite this way, we are done already. Otherwise, all conditions are the same and we have gained the additional assumption that the sets are disjoint. And then, your proof works fine, here is my version of it:
Let $E:=2\mathbb{N}={\,n\in\mathbb{N}\,\mid\,\exists k\in\mathbb{N}: n=2k\,}$  the set of even numbers and $O=\mathbb{N}\setminus E$. Since $\mathbb{N}\cong E$ by $n\mapsto 2n$ and $\mathbb{N}\cong O$ by $n\mapsto 2n+1$, you can find bijections $A_1\cong E$ and $A_2\cong O$. Hence, there is a bijection $A_1\cup A_2\cong E\cup O = \mathbb{N}$. 
