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 $\sequence {S_n}_{n \mathop \in \N}$ be a sequence of countable sets.

Define:

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


For all $n \in \N$, let $\FF_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 $\FF_n$ is non-empty.


Using the Axiom of Countable Choice, there exists a sequence $\sequence {f_n}_{n \mathop \in \N}$ such that $f_n \in \FF_n$ for all $n \in \N$.

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

$\map \phi {m, n} = \map {f_m} n$


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