Possible Duplicate:
countably infinite union of countably infinite sets is countable

How to prove the union of two disjoint denumerable sets is denumerable?

I want a direct proof


marked as duplicate by Old John, Michael Greinecker, William, user21436, Jyrki Lahtonen Sep 3 '12 at 11:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


By hypothesis you have disjoint sets $A=\{a_n:n\in\Bbb N\}$ and $B=\{b_n:n\in\Bbb N\}$. You want a bijection $f:\Bbb N\to A\cup B$.

HINT: There is an easy way to define $f$ so that it maps the set of even integers in $\Bbb N$ bijectively to $A$ and the odd ones bijectively to $B$. Where do you think that $f$ should send $2n$? What about $2n+1$?

Added: There are at least a couple of ways to write down such a function. You can say:

For each $n\in\Bbb N$ let $f(2n)=\text{thing}_1$ and $f(2n+1)=\text{thing}_2$.

Alternatively, you can give a two-case definition of $f$ like this:

Let $$f:\Bbb N\to A\cup B:n\mapsto\begin{cases}\text{formula}_1,&\text{if }n\text{ is even}\\\text{formula}_2,&\text{if }n\text{ is odd}\;.\end{cases}$$

The formulas might involve division by $2$, among other things.

  • $\begingroup$ Yeah i thought about that already but i havent learned how to define even&odd numbers.. $\endgroup$ – Katlus May 10 '12 at 6:50
  • 1
    $\begingroup$ @Katlus: I pretty much did it at the end of my answer: the even numbers are the numbers $2n$ such that $n\in\Bbb N$, and the odd numbers are the numbers $2n+1$ such that $n\in\Bbb N$. Or try $$f:\Bbb N\to A\cup B:n\mapsto\begin{cases}\text{something},&\text{if }n\text{ is even}\\\text{something else},&\text{if }n\text{ is odd}\;.\end{cases}$$ $\endgroup$ – Brian M. Scott May 10 '12 at 6:53

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