finite set of countable sets is countable

Question

I am trying to solve this using Hilbert's paradox.

Say I have a collection of countable sets: $A_1,...,A_n$.

I want to show that there is a bijective function from then union, $A=\cup{A_i}, 1\leq i\leq k$ to $\mathbb{N}$.

I'm thinking to map the elements from each ${A_i}, 1\leq i\leq k-1$ to a prime number $p_i$ raised to a power according to the element's order in its group ${A_i}$ (which can be ordered, since it's countable), and then use elements from group ${A_k}$ to fill in the "gaps" in $\mathbb{N}$.

But then I have a problem with elements from ${A_k}$ whose image is a power of the prime numbers $p_1,...,p_k-1$ which I've used before. I could map them to powers of the prime $p_k$ but then I have the same problem with other elements whose image is a power of $p_k$...

How may I solve this problem (or maybe my approach is incorrect)?

Answer 1

I think this should work.

First, let me translate the "countable" hypothesis into $A_k\simeq \mathbb{N}$ for all $k=0,...,n-1$. Now let $n\mathbb{N}+k$ be $\{{n*j+k | j\in\mathbb{N}\}}$. It is clear that for all $i=0,...,n-1$, $n\mathbb{N}+k\simeq\mathbb{N}$ (via the function $x\mapsto\frac{x-k}{n}$). Now we get: $\mathbb{N}=\bigsqcup_{k=0}^{n-1}(n\mathbb{N}+k)\simeq\bigsqcup_{k=0}^{n-1}(A_k)$ for what we've just said (the first step is properly an equality: the union returns $\mathbb{N}$; the second follows from the hypothesis as seen).

Here, "$\simeq$" means is in bijection with and "$\bigsqcup$" is the disjoint union. We should also notice that all the bijections are explicit (apart from the ones given by the hypothesis).

I suggest you to take $n=3$ to easily see how this works.

Answer 2

A set is countable if its cardinality is less than or equal to $\aleph_0$.

The following two lemmas are left (for now anyway / no time) as exercises.

Lemma 1: Let $(A_i)_{1 \le i \le k}$, $k \ge 1$ be a finite family of countable sets the union of which has cardinality $\aleph_0$. Then there exists a finite family $(B_i)_{1 \le i \le n}$, $n \ge 1$ of mutually disjoint nonempty countable sets with the same union and such that $B_n$ is infinite.

Lemma 2: Let $N$ be a countable subset of $\Bbb N$ such that $\Bbb N \setminus N$ is infinite
and let $A$ be a countably infinite set.
Then there exists a mapping $\Gamma: A \to \Bbb N$ satisfying

$\tag 1 \Gamma \text{ is an injection}$ $\tag 2 \Gamma (A) \cap N = \emptyset$ $\tag 3 \Gamma (A) \cup N = \Bbb N$