countably infinite union of countably infinite sets is countable

Solution 1:

The answer depends on your set theory.

If your set theory includes the Axiom of (Countable) Choice, then you can proceed as follows:

1. For each $n\in\mathbb{N}$, select a bijection $f_n\colon X_n\to\mathbb{N}$. (This step requires the Axiom of Countable Choice);
2. Select a bijection $g\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$; there are several explicit examples of this. For example, the Cantor pairing function $g(p,q) = \frac{(p+q)(p+q+1)}{2}+q$.
3. Define $f\colon \bigcup\limits_{n\in\mathbb{N}}(X_n\times\{n\})\to \mathbb{N}$ by mapping $(x,n)$ to $g(f_n(x),n)$.

This defines a bijection between the disjoint union of the $X_n$ onto $\mathbb{N}$. To get a bijection in the case where the $X_n$ are not disjoint, note that $\bigcup\limits_{n\in\mathbb{N}} X_n$ embeds into the disjoint union (map $x$ in the union to $(x,m)$ where $m$ is the smallest $n\in\mathbb{N}$ such that $x\in X_n$), which is bijectable to $\mathbb{N}$; then use the Cantor-Bernstein Theorem applied to this embedding and to embedding that maps $\mathbb{N}$ to $X_1$ into the union to get a bijection.

However, if your set theory does not include the Axiom of Choice, then the answer may be that the union need not be bijectable with $\mathbb{N}$. In particular, it is consistent with ZF that the real numbers are a countable union of countable sets, and of course the real numbers are not bijectable with $\mathbb{N}$.

Solution 2:

If you want to show that the countable union of countable subsets is countable, you can use Cantor-Schroeder-Bernstein (I don't think it uses AC --even in summer :) ), and set up injections between $\mathbb N$ and $\mathbb N \times \mathbb N $, and the other-way-around , by generalizing this:

take any two primes , say 2,3, and map : $(a,b)\rightarrow 2^a3^b$ ( you can see that, to generalize to a product of k-copies of $\mathbb N$, just take k different primes; if you want an actually countably-infinite product, this is maybe more delicate), and an injection in the opposite direction is given by , e.g., n->(n,0,0,...).

And, BTW, any choice of injections in CSBernstein allows to construct an actual bijection.

EDIT: I think it is not too hard to show the map (a,b)->$2^a3^b$ is an injection; if we had $2^a3^b=2^{a'}3^{b'}$, it would follow that $2^{a-a'}3^{b-b'}=1$; by simple divisibility arguments, each of the factors on the left-hand side would have to divide 1; it then follows that a-a'=0 and b-b'=0, i.e., a=a', b=b'.

EDIT#2 : Please see some of the caveats in the comments section about concluding that the union of countables is countable.