Prove union of sets is countable

Question

Question:

Let $ A_{1}, A_{2}, ...$ be a sequence of sets, each of which is countable. Prove that the union of all the sets in the sequence is countable.

My attempt:

We know that for each set in the sequence, $ \exists \ f: \mathbb{N} \to A_{k}$ a bijection. Now I'm not sure how to prove that the union of all these sets is countable.

Answer 1

Have you seen the proof that the rational numbers are countable, where you arrange them in a grid?

List the elements in each set in a similar grid, with $A_1$ in the first row, $A_2$ in the second row, etc. Then define a similar function in a zig-zag manner through the grid. This should be a bijection between $\mathbb{N}$ and your union.

Answer 2

Associate a prime $p_k$ to $A_k$ such that $p_i\neq p_j$ if $i\neq j$, let $f_k:A_k\rightarrow \mathbb{N}-\{0\}$ a bijection, define $f:\bigcup_k A_k\rightarrow \mathbb{N}$ by $f(a_k)=p_k^{f_k(a_k)}, a_k\in A_k$, $f$ is injective.

Answer 3

Do you know the "Cantor Diagonal" ? list the elements of $A_1$ as $a_{11}, a_{12}, ...., a_{1n},.....$ And continue for $A_2$, and the $A_k$ has: $a_{k1}, a_{k2}, ...., a_{kn}, ...$. Thus you have an infinite square,and you can rearrange these terms in the following order: $a_{11}, a_{21}, a_{22}, a_{31}, a_{32}, a_{33}, a_{41}, a_{42}, a_{43}, a_{44},....$ and this list is countably infinite hence the union is countable.