Proof that a countable union of countable sets is countable

Proof

1. Let $I$ be a countable set, and let $(A_i)_{i \in I}$ be a family of sets with each $A_i$ countable. Let $U = \bigcup_{i \in I} A_i$ be their union.
2. Since $I$ is countable, there is an injective function $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, there is a choice function $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, $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, there is an injective function $\psi \colon \N \times \N \to \N$.
12. The composite $\psi \circ \phi \colon U \to \N$ is injective, as a composition of injections. So $U$ is countable.