Cfrgtkky

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?

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:

1. The product of two countable sets is countable. Therefore $Bbb{Ntimes N}$ is countable.


2. 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{Ntimes 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:

1. Make then $S_n$'s disjoint, by considering, perhaps $S_ntimes{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_nsetminusbigcup_{k<n}S_k$, which will remove the duplicates and perhaps empty out a few of the sets. Either option works.




2. 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{Ntimes 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.

Take $A_1={a_{11},a_{12},...},A_2={a_{21},a_{22},...},...,A_n={a_{n1},a_{n2},...}$ be your countable sets. Every countable set can be enumerated.

Now the union $cup_{j=1}^{infty} A_{i}$ is a matrix which is infinite horizontically and vertically.

Now take $B_{1}={a_{11}},B_2={a_{21},a_{12}},B_3={a_{31},a_{22},a_{13}},...$ and so on $B_n={a_{n1},a_{(n-1)2},a_{(n-2)3},...,a_{1n}}$. These are the finite diagonals that you can form. Now we wrote the infinite union of infinite sets $A_i$ into the infinite union of finite sets $B_i$ and $cup_{i}A_i=cup_{i}B_i$.

There is no difference in our problem if $B_n$ has $n$ elements if it has one element.

It's like you have countable union of singletons which is in fact in one to one correspondance with the set of the naturals $mathbb N$.

Hint: supposing that the $S_n$ are disjoint, use the bijection $Bbb{Ntimes N}longrightarrowBbb N$ ($Bbb N$ starting form 0)

$$(n,m)longmapstofrac{(n+m)(n+m+1)}2 + n.$$

A common pitfall with the "countable union of countable sets" questions is to assume that each countable set in the original collection has an enumeration (bijection with N) already given.

That the sets in the collection are countable is given but the enumeration may be given (implicitly or explicitly) or may not.

If the enumeration of each set (bijection with N) is not given in the hypothesis, the ability to pick one enumeration for each set in the collection requires at a minimum the countable Axiom of Choice.

If an enumeration for each set in the collection is given in the hypothesis, like in "countable union of copies of N", the walk on the finite diagonals described above does exhaust the sets in the original collection (i.e. the "$j$"th element in the "$k$"th set is reached after a finite number of steps for any $k$ and $j$).

Only then the Axiom of Choice is not required; the original hypothesis provides enough order, without need for the well ordering prowess of Axiom of Choice.

In the crazy world of set theory the union of a countable copies of N may be countable while under the same assumptions the union of a countable number of sets of pairs may be uncountable.