[proofplan]
We choose numerical labels for the index set and for each set in the family. For each element of the union, we select the first indexed set containing it, using the well-ordering of $\mathbb{N}$, and record both that first index label and the element's label inside that set. This produces an injection from the union into $\mathbb{N} \times \mathbb{N}$, and countability follows from the countability of $\mathbb{N} \times \mathbb{N}$.
[/proofplan]
[step:Choose injections that enumerate the index set and each member set]
Let
\begin{align*}
U := \bigcup_{i \in I} A_i.
\end{align*}
Since $I$ is a [countable set](/page/Countable%20Set), the [Equivalent Characterisations of Countability](/theorems/753) give an injective map
\begin{align*}
f: I &\to \mathbb{N}.
\end{align*}
For each $i \in I$, since $A_i$ is countable, the same characterisation gives an injective map
\begin{align*}
g_i: A_i &\to \mathbb{N}.
\end{align*}
[/step]
[step:Assign each element of the union to the first indexed set containing it]
For each $x \in U$, define
\begin{align*}
S_x := \{f(i) \in \mathbb{N} : i \in I \text{ and } x \in A_i\}.
\end{align*}
Because $x \in U$, there exists $i \in I$ with $x \in A_i$, so $S_x$ is non-empty. By the [Well-Ordering Principle](/theorems/721), $S_x$ has a least element; denote it by $m_x \in \mathbb{N}$. Since $m_x \in S_x$, there exists $i_x \in I$ such that $x \in A_{i_x}$ and $f(i_x) = m_x$. This $i_x$ is unique because $f$ is injective.
[guided]
Fix an element $x \in U$. The difficulty is that $x$ may belong to more than one of the sets $A_i$, so we need a deterministic choice of which containing set to use. Define
\begin{align*}
S_x := \{f(i) \in \mathbb{N} : i \in I \text{ and } x \in A_i\}.
\end{align*}
Since $x \in U = \bigcup_{i \in I} A_i$, there is at least one index $i \in I$ such that $x \in A_i$. Therefore $f(i) \in S_x$, and $S_x$ is a non-empty subset of $\mathbb{N}$.
The Well-Ordering Principle applies because $S_x \subset \mathbb{N}$ is non-empty. Hence $S_x$ has a least element, which we denote by $m_x \in \mathbb{N}$. Since $m_x$ is an element of $S_x$, the definition of $S_x$ gives at least one index $i_x \in I$ such that $x \in A_{i_x}$ and $f(i_x) = m_x$. If $j_x \in I$ also satisfied $f(j_x) = m_x$, then $f(i_x) = f(j_x)$, and injectivity of $f$ would imply $i_x = j_x$. Thus $i_x$ is uniquely determined.
[/guided]
[/step]
[step:Define the encoding map into $\mathbb{N} \times \mathbb{N}$]
Define the map
\begin{align*}
h: U &\to \mathbb{N} \times \mathbb{N} \\
x &\mapsto (m_x, g_{i_x}(x)).
\end{align*}
This is well-defined because $m_x \in \mathbb{N}$, $x \in A_{i_x}$, and $g_{i_x}: A_{i_x} \to \mathbb{N}$.
[/step]
[step:Prove that the encoding map is injective]
Let $x,y \in U$ and suppose $h(x) = h(y)$. By equality of ordered pairs,
\begin{align*}
m_x = m_y
\quad \text{and} \quad
g_{i_x}(x) = g_{i_y}(y).
\end{align*}
Since $f(i_x) = m_x$ and $f(i_y) = m_y$, the equality $m_x = m_y$ gives $f(i_x) = f(i_y)$. Injectivity of $f$ implies $i_x = i_y$. Therefore
\begin{align*}
g_{i_x}(x) = g_{i_x}(y).
\end{align*}
Since $g_{i_x}: A_{i_x} \to \mathbb{N}$ is injective and $x,y \in A_{i_x}$, we conclude that $x = y$. Hence $h$ is injective.
[guided]
Take $x,y \in U$ and assume $h(x) = h(y)$. By the definition of $h$, this means
\begin{align*}
(m_x, g_{i_x}(x)) = (m_y, g_{i_y}(y)).
\end{align*}
Equality in the Cartesian product $\mathbb{N} \times \mathbb{N}$ is componentwise, so
\begin{align*}
m_x = m_y
\quad \text{and} \quad
g_{i_x}(x) = g_{i_y}(y).
\end{align*}
The first equality identifies the chosen containing set. Indeed, by construction,
\begin{align*}
f(i_x) = m_x
\quad \text{and} \quad
f(i_y) = m_y.
\end{align*}
Thus $f(i_x) = f(i_y)$. Since $f: I \to \mathbb{N}$ is injective, it follows that $i_x = i_y$.
Now both elements are being evaluated by the same injection. Substituting $i_y = i_x$ into the second component equality gives
\begin{align*}
g_{i_x}(x) = g_{i_x}(y).
\end{align*}
The construction of $i_x$ and $i_y$ gives $x \in A_{i_x}$ and $y \in A_{i_y} = A_{i_x}$. Since $g_{i_x}: A_{i_x} \to \mathbb{N}$ is injective, the equality of images implies $x = y$. Therefore $h$ is injective.
[/guided]
[/step]
[step:Conclude countability from the countability of $\mathbb{N} \times \mathbb{N}$]
By the [Countability of Product of Natural Numbers](/theorems/754), the set $\mathbb{N} \times \mathbb{N}$ is countable. Since $h: U \to \mathbb{N} \times \mathbb{N}$ is injective, the [Equivalent Characterisations of Countability](/theorems/753) imply that $U$ is countable. Recalling that $U = \bigcup_{i \in I} A_i$, this proves that
\begin{align*}
\bigcup_{i \in I} A_i
\end{align*}
is countable.
[/step]
