Countable Union of Countable Sets is Countable

Theorem

Let the axiom of countable choice be accepted.

Then it can be proved that a countable union of countable sets is countable.

Proof 1

Let $\left\langle{S_n}\right\rangle_{n \in \N}$ be a sequence of countable sets.

Define:

$\displaystyle S = \bigcup_{n \in \N} S_n$

For all $n \in \N$, let $\mathcal F_n$ denote the set of all injections from $S_n$ to $\N$.

Since $S_n$ is countable, $\mathcal F_n$ is non-empty.

Using the axiom of countable choice, there exists a sequence $\left\langle{f_n}\right\rangle_{n \in \N}$ such that $f_n \in \mathcal F_n$ for all $n \in \N$.

Let $\phi : S \to \N \times \N$, where $\times$ denotes the cartesian product, be the injection defined by:

$\phi \left({x}\right) = \left({n, f_n \left({x}\right)}\right)$

where $n$ is the least natural number such that $x \in S_n$.

Because $\N$ is well-ordered, such a least $n$ exists.

Since $\N \times \N$ is countable, there exists an injection $\alpha: \N \times \N \to \N$.

The composition of injections is an injection, so the mapping $\alpha \circ \phi: S \to \N$ is an injection.

That is, $S$ is countable.

$\blacksquare$

Proof 2

Let $\left\langle{S_n}\right\rangle_{n \in \N}$ be a sequence of countable sets.

Define:

$\displaystyle S = \bigcup_{n \in \N} S_n$.

For all $n \in \N$, let $\mathcal F_n$ be the set of all surjections from $\N$ to $S_n$.

Since $S_n$ is countable, $\mathcal F_n$ is non-empty.

Using the axiom of countable choice, there exists a sequence $\left\langle{f_n}\right\rangle_{n \in \N}$ such that $f_n \in \mathcal F_n$ for all $n \in \N$.

Let $\phi: \N \times \N \to S$, where $\times$ denotes the cartesian product, be the surjection defined by:

$\phi \left({m, n}\right) = f_m \left({n}\right)$

Since $\N \times \N$ is countable, there exists a surjection $\alpha: \N \to \N \times \N$.

Because the composition of surjections is a surjection, the mapping $f = \phi \circ \alpha$, where $\circ$ denotes composition, is a surjection from $\N$ to $S$.

The preimage (under $f$) of any two distinct elements of $S$ are non-empty and disjoint subsets of $\N$.

So their smallest elements, which exist because $\N$ is well-ordered, are distinct.

Therefore, the mapping $F: S \to \N$ defined by:

$F \left({x}\right) = \min f^{-1} \left({x}\right)$

is an injection.

$\blacksquare$

Sources

• Steven A. Gaal: Point Set Topology (1964)... (previous)... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability