# countably infinite union of countably infinite sets is countable

How do you prove that any collection of sets {$X_n : n \in \mathbb{N}$} such that for every $n \in \mathbb{N}$ the set $X_n$ is equinumerous to the set of natural numbers, then the union of all these sets, $\bigcup_{i\in \mathbb{N}}$ $X_i$ is also equinumerous to the set of natural numbers. Also by equinumerous I mean there exists a one-to-one and onto function $f:X_n \to \mathbb{N}$.

Is this statement still false as it stands?

-
By "equivalent"... what exactly do you mean? – Arturo Magidin Aug 2 '11 at 19:37
@Arturo: There exist a one-to-one and onto function $f$ $:$ $A$ $\to$ $N$ – Mark Aug 2 '11 at 19:39
i.e., you want show that "the union of denumerable sets is denumerable". The statement, as given, is false, then; if you take "enough" sets that are bijectable with $\mathbb{N}$, the union may fail to be bijectable to $\mathbb{N}$; for example, $\mathbb{N}\times\mathbb{R}$ is bijectable with $\mathbb{R}$, and $\mathbb{N}\times\mathbb{R}$ is the union $\cup (\mathbb{N}\times\{r\})$ over all $r\in\mathbb{R}$. Each $\mathbb{N}\times\{r\}$ is bijectable with $\mathbb{N}$, but the union is not. – Arturo Magidin Aug 2 '11 at 19:41
This question is not well defined. How big is the collection of the sets? Each of the sets? Do you work in ZFC, or some other theory? – Asaf Karagila Aug 2 '11 at 19:42
I'm assuming $N$ is $\mathbb{N}$ (you can type it with \mathbb{N}); what is $Z_n$, though? – Arturo Magidin Aug 2 '11 at 19:43

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}$.

-

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.

-
It is consistent without choice that $\aleph_1$ is a countable union of countable sets. You have to have choice for that, even if Cantor-Bernstein doesn't require it. – Asaf Karagila Aug 2 '11 at 22:44
Sorry, but isn't the countable union of countable counatble, i.e., $\aleph_0$? – gary Aug 2 '11 at 23:15
@gary: As Asaf says, in the absence of the axiom of choice, it is possible for a countable union of countable sets to be uncountable. For example, there is a model of ZF where $\mathbb{R}$ is a countable union of countable sets. – Zhen Lin Aug 3 '11 at 0:42
Yes, my bad, I keep assuming ZFC automatically; I keep imposing my assumptions on questions; I am becoming senile way too early. – gary Aug 3 '11 at 1:18
@gary: Basically, the problem is that one needs to choose countably many embeddings/bijections into $\mathbb{N}$ simultaneously. On the other hand, the union of countably many sets that come equipped with embeddings into $\mathbb{N}$ can be shown to be countable in ZF, without having to invoke choice; that is, if you have a family $(X_n,f_n)$, $n\in\mathbb{N}$, with $f_n\colon X_n\to \mathbb{N}$ one-to-one for each $n$, then it is easy to prove that $\cup X_n$ is countable; but without having the $f_n$ given, that's when you need AC (at least countably). – Arturo Magidin Aug 3 '11 at 11:15