Countable Union of Countable Sets is Countable/Proof 1

From ProofWiki
Jump to: navigation, search


Let the axiom of countable choice be accepted.

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


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


$\displaystyle S = \bigcup_{n \mathop \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 mapping defined by:

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

where $n$ is the (unique) smallest natural number such that $x \in S_n$.

From the Well-Ordering Principle, such an $n$ exists; hence, the mapping $\phi$ exists.

Since each $f_n$ is an injection, it (trivially) follows that $\phi$ is an injection.

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

From Composite of Injections is Injection, the mapping $\alpha \circ \phi: S \to \N$ is an injection.

Hence, $S$ is countable.


Axiom of Countable Choice

This theorem depends on the Axiom of Countable Choice.

Although not as strong as the Axiom of Choice, the Axiom of Countable Choice is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.