Countable Union of Countable Sets is Countable

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.


Informal Proof

Consider the countable sets $S_0, S_1, S_2, \ldots$ where $\displaystyle S = \bigcup_{i \mathop \in \N} {S_i}$.

Assume that none of these sets have any elements in common.

Otherwise, we can consider the sets $S_0' = S_0, S_1' = S_1 \setminus S_0, S_2' = S_2 \setminus \left({S_0 \cup S_1}\right), \ldots$

All of these are countable by Subset of Countable Set‎ is Countable, and they have the same union $\displaystyle S = \bigcup_{i \mathop \in \N} {S_i'}$.

Now we write the elements of $S_0', S_1', S_2', \ldots$ in the form of a (possibly infinite) table:

$\begin{array} {*{4}c} {a_{00}} & {a_{01}} & {a_{02}} & \cdots \\ {a_{10}} & {a_{11}} & {a_{12}} & \cdots \\ {a_{20}} & {a_{21}} & {a_{22}} & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{array}$


where $a_{ij}$ is the $j$th element of set $S_i$.

This table clearly contains all the elements of $\displaystyle S = \bigcup_{i \mathop \in \N} {S_i}$.

Furthermore, we have that $\phi: S \to \N \times \N, a_{ij} \mapsto \left({i, j}\right)$ is an injection.

By Cartesian Product of Countable Sets is Countable, there exists an injection $\psi: \N \times \N \to \N$.

Then $\psi \circ \phi: S \to \N$ is also an injection by Composite of Injections is Injection.

That is to say, $S$ is countable.

$\blacksquare$


Proof 1

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$ 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.

$\blacksquare$


Proof 2

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