# 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!

• @Asaf: Could you elaborate on why, please? What if $A_1$ and $A_2$ are initially not disjoint, and after that operation both of them have the element {0, 1}, for example? Jul 6, 2011 at 7:16
• $A_1'$ and $A_2'$ contain only ordered pairs, and an ordered pair is equal to another if and only if both the coordinates are equal; since all the pairs in $A_1'$ start with $0$ and all the pairs in $A_2'$ start with $1$ they cannot share any ordered pair and therefore disjoint. Jul 6, 2011 at 7:20
• @Asaf: Hmm, but why do they start with 1? Did you mean to write $\{1\} \times A_2$? Jul 6, 2011 at 7:50
• Yes, I did intend to write that. I had to delete and rewrite my comment once. I guess it is time to do that again :-) Jul 6, 2011 at 8:01
• Since answers were given, I will only add a small comment about turning sets into disjoint sets: Take $A_1'=\{0\}×A_1$ and $A_2'=\{1\}×A_2$. It is easy to prove that $A_1'\cap A_2'=\varnothing$. Jul 6, 2011 at 8:02

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.
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}$.