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

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?

• Your title asks for a bijection, and the post asks for a surjection. Which one is it? – Asaf Karagila Apr 3 '20 at 12:06

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.