---
tag: 87T5JN3P1Q
kind: proof
name: Proof that a countable union of countable sets is countable
msc: ["03E10"]
proves: 0Z8FM54P86
uses: [0HTGB13FE2, 0YXEQWRGP0, 0ZG61TFBES, 05Q6G4EH2G, 05GK32H72H, 0PVG1CRAJN, 01BX15HSRR, 08G4XH86JC, 01FPXMTBX1]
sources:
  - url: https://proofwiki.org/wiki/Countable_Union_of_Countable_Sets_is_Countable
    locator: Proof 1
---

## Proof

1. Let $I$ be a [[countable|0ZG61TFBES]] set, and let $(A_i)_{i \in I}$ be a [[family of sets|05Q6G4EH2G]] with each $A_i$ countable. Let $U = \bigcup_{i \in I} A_i$ be their [[union|05GK32H72H]].
2. Since $I$ is countable, there is an [[injective function|0PVG1CRAJN]] $e \colon I \to \N$.
3. For each $i \in I$, let $J_i$ be the set of injective functions from $A_i$ to $\N$. Each $J_i$ is nonempty, because $A_i$ is countable.
4. Let $X = \{J_i : i \in I\}$, a set of nonempty sets. By the [[axiom of choice|0HTGB13FE2]], there is a [[choice function|0YXEQWRGP0]] $c$ on $X$.
5. For $i \in I$, put $g_i = c(J_i)$. Then $g_i \colon A_i \to \N$ is injective.
6. Let $x \in U$. The set $N_x = \{e(i) : i \in I,\ x \in A_i\}$ is a nonempty subset of $\N$.
7. By the [[well-ordering principle|01BX15HSRR]], $N_x$ has a least element $m_x$. Since $e$ is injective, exactly one $i \in I$ has $e(i) = m_x$. Call it $i(x)$. Then $x \in A_{i(x)}$.
8. Define $\phi \colon U \to \N \times \N$ by $\phi(x) = (e(i(x)),\ g_{i(x)}(x))$.
9. The map $\phi$ is injective. Suppose $\phi(x) = \phi(y)$. Then $e(i(x)) = e(i(y))$, so $i(x) = i(y)$, because $e$ is injective. Call this index $i$.
10. Then $g_i(x) = g_i(y)$ with $x, y \in A_i$. Since $g_i$ is injective, $x = y$.
11. The set $\N$ is countable, through the identity map. By the [[product of countable sets is countable|08G4XH86JC]], there is an injective function $\psi \colon \N \times \N \to \N$.
12. The composite $\psi \circ \phi \colon U \to \N$ is [[injective|01FPXMTBX1]], as a composition of injections. So $U$ is countable.

## Idea

Each element of the union gets two labels: the label of the first set that contains it, and its label inside that set. Two labels make a pair of natural numbers, and pairs of natural numbers can be coded as single natural numbers. The axiom of choice is used to fix one labelling of each set $A_i$ at once.