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.

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

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}$$ 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. 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 '18 at 16:35
  • $\begingroup$ Yeah the exercise was concerning finite unions. Thank you very much. :) $\endgroup$ – Adam Mar 24 '18 at 16:38

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

| cite | improve this answer | |
  • $\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$ – Matrefeytontias Mar 25 '18 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.