# proof that countable unions are countable

Let $C$ be a countable set of countable sets. We will show that $\cup C$ is countable^{}.

Let $P$ be the set of positive primes (http://planetmath.org/Prime). $P$ is countably infinite^{}, so there is a bijection between $P$ and $\mathbb{N}$. Since there is a bijection between $C$ and a subset of $\mathbb{N}$, there must in turn be a one-to-one function $f:C\to P$.

Each $S\in C$ is countable, so there exists a bijection between $S$ and some subset of $\mathbb{N}$. Call this function $g$, and define a new function ${h}_{S}:S\to \mathbb{N}$ such that for all $x\in S$,

$${h}_{S}(x)=f{(S)}^{g(x)}$$ |

Note that ${h}_{S}$ is one-to-one. Also note that for any distinct pair $S,T\in C$, the range of ${h}_{S}$ and the range of ${h}_{T}$ are disjoint due to the fundamental theorem of arithmetic^{}.

We may now define a one-to-one function $h:\cup C\to \mathbb{N}$, where, for each $x\in \cup C$, $h(x)={h}_{S}(x)$ for some $S\in C$ where $x\in S$ (the choice of $S$ is irrelevant, so long as it contains $x$). Since the range of $h$ is a subset of $\mathbb{N}$, $h$ is a bijection into that set and hence $\cup C$ is countable.

Title | proof that countable unions are countable |
---|---|

Canonical name | ProofThatCountableUnionsAreCountable |

Date of creation | 2013-03-22 12:00:01 |

Last modified on | 2013-03-22 12:00:01 |

Owner | Koro (127) |

Last modified by | Koro (127) |

Numerical id | 9 |

Author | Koro (127) |

Entry type | Proof |

Classification | msc 03E10 |