# Proof verification : Union of two countable sets is countable

Sincere request, don't forget to address my doubt at the end of the proof

I have assumed my sets to be disjoint at first but I have also addressed the general scenario as the proof progresses.

Set $$A$$ is said to be countable if there exists a bijection from $$A$$ to $$\mathbb{N}$$. Every countable set is infinite

To show that : Union of two countable sets is countable

Suppose $$A$$ and $$B$$ are countable. Assume at first that $$A\cap B=\phi$$

$$A$$ countable $$\Rightarrow \exists f:A\to \mathbb{N}$$ a bijection.

$$B$$ countable $$\Rightarrow \exists g:B\to \mathbb{N}$$ a bijection.

define. $$h:A\cup B \to N$$ as

$$x\mapsto 2f(x) \;$$ if $$x\in A$$

$$x\mapsto 2g(x)+1$$ if $$x\in B$$

Because $$A\cup B$$ is infinite, it is sufficient to show that $$h$$ is injective in order to show that $$A\cup B$$ is countable.

if $$x=y$$, where $$x,y\in A\cup B$$, since $$A$$ and $$B$$ are disjoint, so, either both $$x$$ and $$y$$ belong to $$A$$ or both belong to $$B$$, and because $$f$$ and $$g$$ are well defined, so is $$h$$

Now let $$h(x)=h(y)$$ where $$x,y \in A\cup B$$

again, $$x$$ and $$y$$ can both belong to $$A$$ or can both belong to $$B$$. Hence injectivity of $$h$$ on $$A\cup B$$ follows directly from the injectivity of $$f$$ and $$g$$ on $$A$$ and $$B$$ respectively

Hence, $$A\cup B$$ is countable.

Now, let $$A$$ and $$B$$ be arbitrary countable sets,

then by above method, $$A\cup B = [A\setminus (A\cap B)]\cup[A\cap B]\cup [B\setminus (A\cap B)]$$ is countable.

Doubt : Is it safe to assume $$A\cap B = \phi$$ in the beginning of the proof? I am doubtful here because $$A$$ and $$B$$ are countable. Please address this problem first

• title says product but body says union !? – J. W. Tanner Sep 11 at 21:40
• I am sorry, edited – Abhay Sep 11 at 21:41
• If you are breaking into cases you do Case 1: $A$ and $B$ can do what ever you darned well want and Case 2: $A$ and $B$ don't do the stuff. So there is nothing wrong with saying Case 1: $A$ and $B$ are disjoint. Case 2: they are not disjoint. – fleablood Sep 11 at 22:31
• But how do you know $A\setminus (A\cap B), B \setminus (A\cap B)$ and $A \cap B$ are countable? And you defined countably infinite. What if some of these are finite? – fleablood Sep 11 at 22:33
• It is customary that "countable" means "finite or countably infinite" so that "uncountable" and "not countable" both mean "uncountably infinite". – DanielWainfleet Sep 12 at 1:07

Your proof is just about fine. It's perfectly acceptable to start with the case $$A \cap B = \emptyset$$ as long as you later address the possibility that $$A \cap B \neq \emptyset$$, which you do.
Edited to add: Tuvasbien is correct to note that the final step of your proof can be simplified. $$A \cup B = A \cup (B \setminus A)$$, and $$A \cap (B \setminus A) = \emptyset$$.