0
$\begingroup$

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?

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

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.

$\endgroup$

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.