Building a bijection from a finite union of countable sets to $\mathbb{N}$

Question

Let $A_1,...A_k$ be countable sets, I need to prove that the union $\bigcup_{i=1}^{k}A_i$ is countable by explicitly building a surjection.

I can't assume that the sets are disjoint.

I can easily build an injection $g:\bigcup_{i=1}^{k}A_i\rightarrow \mathbb{N}\times\mathbb{N}$ by defining $g(a)=(f_{i}(a),i)$ where $f_i$ is the first bijection from the bijections $f_i,...f_k$ that maps $A_i\rightarrow\mathbb{N}$ such that $a\in A_i$.

However, this map $g$ obviously isn't surjective.

Any ideas for building such map?

Answer 1

Let $f_i: A_i \to \mathbb{N}$ be a bijection for all $0 \leq i < k$, and fix some bijection $h: \mathbb{N} \to \{1, \ldots, k\} \times \mathbb{N}$. Define $g: \mathbb{N} \to \bigcup_{i = 1}^k A_i$ by $$ g(n) = f_{x}(y), \text{ where } (x,y) = h(n). $$ It is easy to check that this is surjective.

For completeness, we can construct $h: \mathbb{N} \to \{1, \ldots, k\} \times \mathbb{N}$ as follows: $$ h(n) = \left( n - k \left\lfloor \frac{n}{k} \right\rfloor + 1, \left\lfloor \frac{n}{k} \right\rfloor \right). $$

---

Note that we can actually prove, without the axiom of choice, that there is a bijection between $\mathbb{N}$ and $\bigcup_{i = 1}^k A_i$. Since we have only finitely many $A_i$, picking the $f_i$ does not require choice. So the function $\bigcup_{i = 1}^k A_i \to \mathbb{N} \times \mathbb{N}$ you constructed in the question does not require choice. Composing this with a bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ gives an injection $\bigcup_{i = 1}^k A_i \to \mathbb{N}$. The inverse $f_1^{-1}: \mathbb{N} \to A_1$ gives an injection $\mathbb{N} \to \bigcup_{i = 1}^k A_i$. So we have injections in both directions, and hence by Schröder-Cantor-Berstein there must be a bijection.