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$

  • 1
    $\begingroup$ 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). $\endgroup$
    – drhab
    Mar 24, 2018 at 16:35
  • $\begingroup$ Yeah the exercise was concerning finite unions. Thank you very much. :) $\endgroup$
    – Adam
    Mar 24, 2018 at 16:38
  • $\begingroup$ "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). $\endgroup$
    – fleablood
    Mar 28, 2021 at 19:18
  • $\begingroup$ FYI : To obviate the need for worrying about set overlap - see this proof. $\endgroup$ Aug 3, 2021 at 13:10

1 Answer 1


Your proof is indeed valid for a finite union of countable sets. A shorter, more immediate proof goes as follows.

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$.

  • $\begingroup$ It occurs to me that this is only valid for the union of disjoint sets. Will delete shortly, I can't on mobile $\endgroup$ Mar 25, 2018 at 10:39

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.