Finite union of countable sets is countable.

Question

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$

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

Answer 2

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.

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

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

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