Set Theory – Countably Infinite Union of Countably Infinite Sets is Countable

elementary-set-theory

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? (By equinumerous I mean there exists a one-to-one and onto function $f:X_n \to \mathbb{N}$.)

Is this statement false as it stands?

Best Answer

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

Related Question