Good night. I have a problem with this exercise:

Prove that the union of two denumerable sets is denumerable.


Be $A,B\subset\mathbb{R}$ where A and B are numerable, in other words $f:\mathbb{N\rightarrow}A$ biyective and $g:\mathbb{N\rightarrow}B$. Be $h:\mathbb{N\rightarrow}A\cup B$ and suppose:

$A=\left\{ a_{1},a_{2},a_{3},...\right\} $

$B=\left\{ b_{1},b_{2},b_{3},...\right\} $

I construct a function biyective such that

$1\rightarrow a_{1}$

$2\rightarrow b_{1}$

$3\rightarrow a_{2}$

$4\rightarrow b_{2}$




Where $h(x)=\begin{cases} 2k+1\rightarrow a_{k}\:k\epsilon\mathbb{N}\\ 2k\rightarrow b_{k}\:k\epsilon\mathbb{N} \end{cases}$

If we see the function $h(x)$ she is $\mathbb{N}$ in other words, $A\cup B$=$\mathbb{N}$ then $h:\mathbb{N\rightarrow}A\cup B$ is biyective.

But i feel my proof is too bad, can someone help me?

  • 1
    $\begingroup$ Almost straight from the get-go, you're assuming $A$ and $B$ are disjoint. This isn't too difficult an issue to amend, but you may want to mention something about it. $\endgroup$ – Aweygan Aug 2 '16 at 22:02
  • $\begingroup$ Your function $h$ need not ba bijection; for instance, if $A \cap B \ne \emptyset$ then $h$ is not a bijection. But $h$ is surjective, and this should help you. $\endgroup$ – Lee Mosher Aug 2 '16 at 22:03
  • $\begingroup$ If you want to construct a bijection, you can let $C = B \setminus A$ and note that $A \cup B = A \cup C$, where $A \cup C$ is a disjoint union. Then you can apply your method to $A$ and $C$ (but be careful that $C$ may not be infinite and could even be empty). $\endgroup$ – Bungo Aug 2 '16 at 22:07
  • $\begingroup$ I edited the tags and clarified the title and question to reflect the apparent intent. If the result is not what you intended, please fix accordingly. :-) $\endgroup$ – Bungo Aug 2 '16 at 22:11

The proof is almost correct, and is actually a good way of approaching the problem. One small error is that $h$ is not actually bijective, since you can have $a_i=b_j$ for some $i, j$. However, $h$ is still surjective, which suffices to show the union is countable.


We describe one way to modify your argument.

We assume that both sets are countably infinite. Suppose that we have defined $h(k)$ for every $k\lt n$.

If $n$ is even, let $h(n)=b_j$, where $j$ is the smallest positive integer such that $b_j\ne h(k)$ for any $k\lt n$.

If $n$ is odd, $h(n)=a_j$, where $j$ is the smallest positive integer such that $a_j\ne h(k)$ for any $k\lt n$.

Now one can verify that $h$ is a bijection from $\mathbb{N}$ to $A\cup B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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