While working on the theorem below, I constructed the following proof:
Theorem. If $\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ is a sequence of countable sets, then
$$
\bigcup_{n\in\mathbb N}E_{n}
$$is countable.
Proof. Let $S=\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ be a sequence of countable sets. Moreover, let $x_{n,m}$ be the $m$th element of the $n$th set in $S$. Construct a sequence of sequences
$$
\mathcal S=\left\langle\left\langle x_{n-m+1,m}\right\rangle_{m\in\mathcal N_n}\right\rangle_{n\in\mathbb N},
$$
where $\mathcal N_{n}=\left\{k\in\mathbb N:k\leqslant n\right\}$. Then $\mathcal S$ contains all the elements of
$$
T=\bigcup_{n\in\mathbb N}E_{n}.
$$
Observe that $\mathcal S$ is a surjection $\mathbb N\to T$, because for every $n\in\mathbb N$, $\mathcal S$ yields a finite, and thus countable, subsequence. Furthermore, because $\mathcal S$ may contain duplicate elements, an $U\subseteq\mathbb N$ can be found such that $\mathcal S$ is an injection $U\to T$. We have then found a bijection $\mathcal S:U\to T$. Hence, $T$ is countable. $\blacksquare$
Does it sound convincing?
Edit: I just realized that I cannot pinpoint duplicates because of how $\mathcal S$ is constructed, can I? 🙁
Best Answer
You’re trying to list $T$ as $$\langle x_{1,1},x_{2,1},x_{1,2},x_{3,1},x_{2,2},x_{1,3},\ldots\rangle\;,\tag{1}$$ but instead you’ve constructed the sequence
$$\Big\langle\langle x_{1,1}\rangle,\langle x_{2,1},x_{1,2}\rangle,\langle x_{3,1},x_{2,2},x_{1,3}\rangle,\ldots\Big\rangle\;,$$
a related but definitely different animal. It’s actually easier to say what $n\in\Bbb N$ corresponds to $x_{k,\ell}$ in the list $(1)$ than to go in the forward direction. Count the elements of $(1)$ that precede $x_{k,\ell}$. They certainly include all $x_{i,j}$ such that $i+j<k+\ell$, and there are
$$\sum_{n=2}^{k+\ell-1}n=\frac{(k+\ell-1)(k+\ell)}2-1$$
of those. (The summation starts at $2$ because we always have $i+j\ge 2$.)
Let $m=k+\ell$; it also includes all $x_{m-i,i}$ such that $1\le i\le\ell$, and there are $\ell-1$ of those. Thus,
$$\frac{(k+\ell-1)(k+\ell)}2-1+\ell-1=\frac{(k+\ell-1)(k+\ell)}2+\ell-2$$
terms of $(1)$ precede $x_{k,\ell}$, and $x_{k,\ell}$ is therefore term number
$$\frac{(k+\ell-1)(k+\ell)}2+\ell-1$$
of the sequence $(1)$.