fixedpoint.jp


A simple proof of "a countable union of countable sets is countable" (2019-02-21)

It is well-known that, under the axiom of choice, a countable union of countable sets is countable again. In fact, the axiom of countable choice (\(\text{AC}_\omega\)) is enough for proving the statement as follows.

Let \(\{X_n: n \in \mathbb{N}\}\) be a family of countable sets \(X_n\). We are going to show \(X := \cup_{n \in \mathbb{N}} X_n\) is countable. Without loss of generality we can assume that different \(X_n\)s are disjoint. Consider the countable family \(\mathcal{F}_n\) of injections from \(X_n\) to \(\mathbb{N}\). Because \(\mathcal{F}_n\) is non-empty for each \(n \in \mathbb{N}\) by assumption, \(\text{AC}_\omega\) ensures that the existence of a choice function \(F\) such that \(F(n) \in \mathcal{F}_n.\) On the other hand, there exists a function \(i: X \rightarrow \mathbb{N}\) satisfying that \(x \in X_{i(x)}\) for each \(x \in X,\) as \(X_n\)s are pairwise disjoint. Define \(f: X \rightarrow \mathbb{N}\) by\[f(x) = 2^{i(x)} \cdot 3^{F(i(x))(x)},\]which is an injection from \(X\) to \(\mathbb{N}.\) q.e.d.


© 2006-2023 fixedpoint.jp