I am unsuccessfully trying to understand the proof of the fact that countable union of countable sets is countable. The argument presented till now is:
Let $\bigcup S_n$ be a countable union of countable sets $S_n$. Let $x_{nm}$ be the $m$th element of set $S_n$. Then we can map $x_{11}$ to 1, $x_{12}$ to 2, $x_{21}$ to 3, $x_{13}$ to 4 and so on. In a way, the map is "diagonal". But this is not a proof. Moreover, this is not an explicit bijection from $\mathbb N$ to $\bigcup S_n$. Can someone please give me a hint or two so that I can flesh out the proof and make it rigorous?
Best Answer
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:
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.