# If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

My work:
As $A_1$ and $A_2$ are countably infinite, there exists a bijection $\theta_1: \mathbb{N}\to A_1$ and $\theta_2: \mathbb{N}\to A_2$. I need to prove now, that there exists a bijection $\theta : \mathbb{N}\to A_1\cup A_2$ which I am not able to find. Please help.

• Start by defining a bijection $\mathbb{N}\rightarrow\mathbb{N}\cup\mathbb{N}$, e.g. by mapping even numbers into the first and odd numbers into the second bucket. Then compose with your maps. Commented Mar 9, 2014 at 8:10

Define $\phi(2n) = \phi_1(n)$, $\phi(2n-1) = \phi_2(n)$.

Let's look at a trivial example for a moment. Suppose $A = \{a,b,c\}$ and $B = \{d,e\}$. One way of seeing that $A\cup B$ is countable is to right a list containing all the elements. One such list is $a,b,c,d,e$. But this doesn't generalize nicely to countably infinite lists, since we'd never finish $A$.

On the other hand, the list $a,d,b,e,c$, choosing an element from $A$, then an element from $B$, and vice versa, works very well.

In other words, you can explicitly create a list from the two lists you already have.

• Yes, this is actually what I was thinking of, but is this a proper approach?
– Hawk
Commented Mar 9, 2014 at 8:12
• @Hawk: It's certainly valid, especially if you explicitly provide the map! Notice that's all that copper.hat has done. Commented Mar 9, 2014 at 8:14
• You mean, I need to show the map, else it doesn't work right?
– Hawk
Commented Mar 9, 2014 at 8:15
• @Hawk: That depends on what you or your professor considers a complete proof, and the context. Commented Mar 9, 2014 at 8:17
• Okay, I got it, thanks.
– Hawk
Commented Mar 9, 2014 at 8:18