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.

*

*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$
 A: 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$.
A: While an inductive approach can certainly work here, there is a more direct argument, outlined below:

Definition:  A set $A$ is countable (either finite or countably infinite) if there exists an injective function
$$\varphi : A \to \mathbb{N}. $$

For each $j \in \{1,2, \dotsc, n\}$, let $A_j$ be a countable set.  Per the definition above, it is sufficient to show that there exists an injective function from $\bigcup_{j=1}^{n} A_j$ to $\mathbb{N}$.  The intuition of the following approach is to first map the union into the disjoint union, then map the disjoint union into a disjoint union of copies of $\mathbb{N}$, and finish by mapping that into $\mathbb{N}$.  One could do this all in one fell swoop, but I think that it is easier to see what is going on if the map is built up in pieces.

*

*Construct an injective function $\varphi_1$ from $\bigcup_{j=1}^{n} A_j$ to $\bigsqcup_{j=1}^{n} A_j$.  That is, construct an injective function from the union of the sets to the disjoint union of the sets.
Recall that
$$\bigsqcup_{j=1}^{n} A_j = \{ (x,k) : x \in A_k \} \subseteq \left(\bigcup_{j=1}^{n} A_j\right) \times \{1,2,\dotsc,n\}. $$
That is, the disjoint union consists of order pairs, where the first term of each pair is an element $x$ of one of the $A_k$, and the second term of the ordered pair indicates which set $x$ belongs to.  For example,
$$ \{a,b,c\} \sqcup \{a,d\} = \{ (a,1), (b,1), (c,1), (a,2), (d,2) \}. $$
An explicit function from the union to the disjoint union is given by
$$ \varphi_1 : \bigcup_{j=1}^{n} A_j \to \bigsqcup_{j=1}^{n} A_j : x \mapsto \begin{cases}
(x,1) & \text{if $x\in A_1$,} \\
(x,2) & \text{if $x\in A_2 \setminus A_1$,} \\
(x,3) & \text{if $x\in A_3 \setminus (A_1 \cup A_2)$,} \\
\dotso \\
(x,n) & \text{if $x \in A_n \setminus (A_1 \cup A_2 \cup \dotsb \cup A_{n-1})$.}
\end{cases}$$
In other words, an element $x$ in the union gets sent to the ordered pair $(x,k)$, where $k$ is the smallest index such that $x \in A_k$.
Exercise: verify that this function is injective.


*Construct an injective function $\varphi_2$ from $\bigsqcup_{j=1}^{n} A_j$ to $\bigsqcup_{j=1}^{n}\mathbb{N}$.
For each $j$, the set $A_j$ is countable, so there is an injective function $\psi_j : A_j \to \mathbb{N}$.  Define
$$\varphi_2 : \bigsqcup_{j=1}^{n} A_j \to \bigsqcup_{j=1}^{n}\mathbb{N} : (x, k) \mapsto (\psi_k(x),k). $$
Exercise: verify that this function is injective.


*Construct an injective function $\varphi_3$ from $\bigsqcup_{j=1}^{n} \mathbb{N}$ to $\mathbb{N}$.
There are a lot of ways to do this, but a fairly straightforward approach is to define
$$\varphi_{3} : \bigsqcup_{j=1}^{n} \mathbb{N} \to \mathbb{N} : (m,k) \mapsto nm + k.$$
Exercise: verify that this function is injective.
It then follows that the function
$$ \varphi = \varphi_3 \circ \varphi_2 \circ \varphi_1 : \bigcup_{j=1}^{n} A_j \to \mathbb{N}$$
is injective (the composition of injective functions is injective), hence $\varphi$ is the desired map.
