# Union of two countable sets is countable [Proof]

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-

• 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. – 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.

• Please define the term: "enumerate" – model_checker Sep 30 '16 at 11:56
• "Arranged in the given form". It's a pretty standard term. – 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.

• No, $h$ is not injective if $A$ and $B$ are not disjoint. – zarathustra Sep 30 '16 at 9:08
• True, but you don't need a bijection. – phong Sep 30 '16 at 9:09
• So what does this bring to the OP, who already build the function $h$? – zarathustra Sep 30 '16 at 9:12
• 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... – phong Sep 30 '16 at 9:14
• So why not addressing this point in your answer? The function $h$ you describe is exactly what the OP is already considering. – zarathustra Sep 30 '16 at 9:15