# Finite union of countable sets is countable.

Question

Is my proof that the union of countable sets is countable correct?

If $$A_1, A_2, A_3,\dots, A_n$$ is a collection of countable sets, then the union: $$A_1\cup A_2\cup A_3 \cup \dots A_n$$ is countable as well.

Attempted Proof

We attempt to prove the claim by induction.

1. Base case: Consider the set $$B=A_2\setminus A_1$$ Clearly, $$B\subseteq A_2$$($$B$$ is countable) and $$A_1\cup B$$ = $$A_1\cup A_2$$.

2. If $$B$$ is finite, then $$B= \{b_1, b_2, b_3, b_4, \dots, b_j \}\quad j\in\mathbb{N}_0$$ and so we can construct a bijection $$f(n)=\begin{cases} b_n\quad n\leq j\\ a_{n-j}\quad n> j \end{cases}$$ If $$B$$ is infinite, then we can construct a bijection $$f(n)=\begin{cases} b_{\frac n2}\quad n\text{ even}\\ a_{\frac{n+1}{2}}\quad n\text{ odd} \end{cases}$$

3. Now, suppose the statement holds for $$n= k\geq 2$$, that is, $$A_1\cup A_2\cup A_3 \cup \dots A_k$$ is a countable set. Observe that $$(A_1\cup A_2\cup A_3 \cup \dots A_k)\cup A_{k+1}$$ is a union of two countable sets which, by the base case, is also countable.

4. Thus, by induction, the statement holds for all $$n\in\mathbb{N}.\qquad\square$$

• Your proof is okay if you are aiming to prove that a finite union of countable sets is countable (not an arbitrary union, as your title suggests). Mar 24, 2018 at 16:35
• Yeah the exercise was concerning finite unions. Thank you very much. :)
Mar 24, 2018 at 16:38
• "Yeah the exercise was concerning finite unions. " Then it's a pretty toothless exercise. It's tempting to settle but it's usually a bad idea to. Be better to spruce this up to consider countable unions as that is also true and important (of course it's obviously not true for uncountable unions). Mar 28, 2021 at 19:18
• FYI : To obviate the need for worrying about set overlap - see this proof. Aug 3, 2021 at 13:10

For any integer $n \gt 2$, one can construct a bijection $\phi$ between $\mathbb N$ and a finite union of $n$ countable sets $A = \bigcup_{i=1}^n A_i$
$$\phi : i \mapsto A_{i \mod n} \left (\left \lfloor \frac{i}{n} \right \rfloor \right )$$
Where $i \mod n$ is the rest of the euclidean division of $i$ by $n$, and $A_m(n)$ is the $n$-th element of the set $A_m$.