Rigorous proof that countable union of countable sets is countable
First of all, let me assure you there is no general "explicit" bijection. The reason is that the axiom of choice is needed to choose enumerations for each countable set (separately). In its absence, it is consistent that a countable union of countable sets can be uncountable (in fact, it could be equal to the real numbers!).
But suppose that we are given enumerated sets, namely $S_n$ and $f_n$ which is an injection from $S_n$ to $\Bbb N$. In this case we can explicitly define an bijection from $\bigcup S_n$ into $\Bbb N$.
But why? That would be working quite hard to make all the indices fall into place. Instead we want to use the following theorems:
- The product of two countable sets is countable. Therefore $\Bbb{N\times N}$ is countable.
- An infinite subset of a countable set is countable.
So it suffices to show that there is an injection into a countable set, and we're done.
We might want to say, map $s_{n,m}$ to the ordered pair $(n,f_n(s_{n,m}))$, which will be an injection from $\bigcup S_n$ into $\Bbb{N\times N}$. But what if the $S_n$'s are not pairwise disjoint? Then you might have an element mapped into two places at once.
To overcome this difficulty we can do one of two things:
Make then $S_n$'s disjoint, by considering, perhaps $S_n\times\{x_n\}$, where $x_n$ is a set which will guarantee that these are disjoint. We can prove that such $x_n$'s exist. Or perhaps by redefining $S_n'=S_n\setminus\bigcup_{k<n}S_k$, which will remove the duplicates and perhaps empty out a few of the sets. Either option works.
Just do the second option implicitly, by mapping $s_{n,m}$ to $(n,f_n(s_{n,m}))$ if $n$ is the smallest number such that $s_{n,m}\in S_n$.
In either case, this makes the above injection into $\Bbb{N\times N}$ well-defined. So now either that $\bigcup S_n$ is finite or has a bijection with an infinite subset of a countable set, so it is countable.