Theorem: If $A$ and $B$ are both countable sets, then their union $A\cup B$ is also countable.

I am trying to prove this theorem in the following manner:

Since $A$ is a countable set, there exists a bijective function such that $f:\mathbb{N}\to A$. Similarly, there exists a bijective function $g:\mathbb{N}\to B$. Now define $h:\mathbb{N}\to A\cup B$ such that: $$h(n)=\begin{cases} f(\frac{n+1}{2})&\text{, n is odd}\\ g(n/2) & \text{, n is even} \\ \end{cases}$$ So in essence, $h(1)=f(1)$, $h(2)=g(1)$, $h(3)=f(2)$ and so on. Now we have to show that h is a bijection.

h(n) is one-one:

Proof: If $h(n_1)=h(n_2)$ then, if $n_1$ and $n_2$ are both either odd or even, we get $n_1=n_2$. But if, suppose $n_1$ is odd and $n_2$ is even, this implies that: $$f\left(\frac{n_1+1}{2}\right)=g\left(\frac{n_2}{2}\right)$$ How can one deduce from this equality that $n_1=n_2$?

I tried to think about this and realized that if $A\cap B=\phi$ then this case is impossible as it would imply that there is a common element in both sets. On the other hand, if we assume that $A\cap B\neq \phi$, then either $f\left(\frac{n_1+1}{2}\right)\in A\cup B$ or $g\left(\frac{n_2}{2}\right)\in A\cup B$....Beyond this I'm clueless.

Edit: Solution by the author-

enter image description here

  • 1
    $\begingroup$ If $A$ and $B$ are disjoint sets then your mapping $h$ is bijective, because in that case $n_1$ and $n_2$ can be both either even or odd only. If these sets are not disjoint then the mapping $h$ can not be injective. $\endgroup$ – Prince Thomas Nov 7 '17 at 4:37

Your proof: we can take an example: $A=\{2n : n\in \mathbb{N}\}$ and $B=\{3n: n\in \mathbb{N}\}$. We can take $f(n) = 2n$ and $g(n) = 3n$. Then, you have, for example, $h(5) = f(3) = 6$ and $h(6) = g(3) = 6$, then $h$ is not injective.

For the proof, you can see this question.


A set $S$ is countable iff its elements can be enumerated.

Since $A$ is countable, you can enumerate $A=\{a_1,a_2,a_3,...\}$.

Since $B$ is countable you can enumerate $B=\{b_1,b_2,...\}$

Enumerate the elements of $A\cup B$ as $\{a_1,b_1,a_2,b_2,...\}$ and thus $A\cup B$ is countable.

  • $\begingroup$ Please define the term: "enumerate" $\endgroup$ – model_checker Sep 30 '16 at 11:56
  • $\begingroup$ "Arranged in the given form". It's a pretty standard term. $\endgroup$ – Landon Carter Oct 2 '16 at 12:54

Let $f_1 : \mathbb{N}\to A$ and $f_2 : \mathbb{N}\to B$ be two bijections.

Let $g_1 : \mathbb{N}\to 2\mathbb{N}$ such that $g_1(n)=2n$ and $g_2 : \mathbb{N}\to 2\mathbb{N}+1$ such that $g_2(n)=2n+1$.

Then $h : \mathbb{N} \to A\cup B$ such that $h(n)\begin{cases} f_1\circ g_1^{-1} \text{ if }n\text{ is even}\\ f_2\circ g_2^{-1} \text{ if }n\text{ is odd} \end{cases}$ is the surjection you are looking for.

  • $\begingroup$ No, $h$ is not injective if $A$ and $B$ are not disjoint. $\endgroup$ – zarathustra Sep 30 '16 at 9:08
  • $\begingroup$ True, but you don't need a bijection. $\endgroup$ – phong Sep 30 '16 at 9:09
  • $\begingroup$ So what does this bring to the OP, who already build the function $h$? $\endgroup$ – zarathustra Sep 30 '16 at 9:12
  • $\begingroup$ Yes it does, the considerations of OP on the intersection of $A$ and $B$ are unnecessary. If you associated twice the same element of $A\cup B$ two to different naturals, $A\cup B$ is still countable... $\endgroup$ – phong Sep 30 '16 at 9:14
  • $\begingroup$ So why not addressing this point in your answer? The function $h$ you describe is exactly what the OP is already considering. $\endgroup$ – zarathustra Sep 30 '16 at 9:15

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.