Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
@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? – confused Jul 6 '11 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. – Asaf Karagila Jul 6 '11 at 7:20
@Asaf: Hmm, but why do they start with 1? Did you mean to write $\{1\} \times A_2$? – confused Jul 6 '11 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 :-) – Asaf Karagila Jul 6 '11 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$. – Asaf Karagila Jul 6 '11 at 8:02
up vote 2 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.