Countable Union of Countable Sets is Countable/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let the axiom of countable choice be accepted.

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


Proof

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

Define:

$\displaystyle S = \bigcup_{n \mathop \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, it follows by Surjection from Natural Numbers iff Countable that $\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, it follows by Surjection from Natural Numbers iff Countable that there exists a surjection $\alpha: \N \to \N \times \N$.

Since the composition of surjections is a surjection, the mapping $\phi \circ \alpha: \N \to S$ is a surjection.

By Surjection from Natural Numbers iff Countable, it follows that $S$ is countable.

$\blacksquare$


Sources