I'm trying to prove that a countable union of countable sets is countable. I read this proof somewhere and re-wrote it in my own way.
MY WORK
Let $\{S_n\}$ be a sequence of countable sets. Define
\begin{align} S=\bigcup_{n=1}^{\infty}S_n\end{align}
It suffices to construct an injection between $S$ and $\Bbb{N}$. Define
\begin{align} \mathcal{F_n}=\{f:f:S_n\to\Bbb{N}\;\text{and}\;f\;\text{is one-one}\},\;\;\forall\, n\in \Bbb{N}\end{align}
Since $\{S_n\}$ is countable, then $\mathcal{F_n}$ is non-empty. Then, by axiom of countable choice, there exists $\{f_n\}$ such that $f_n\in\mathcal{F_n}$, i.e.
\begin{align} f_n:S_n\to \Bbb{N}\end{align}
\begin{align} x\mapsto f_n(x)\end{align}
where $\{f_n\}$ is injective. Let
\begin{align} \phi:S\to \Bbb{N}\times\Bbb{N}\end{align}
\begin{align} x\mapsto \phi(x)=(n,f_n(x))\end{align}
Hence, $\phi$ is injective since $n$ and $\{f_n\}$ are injective. Also, there exists
\begin{align} \alpha:\Bbb{N}\times\Bbb{N}\to\Bbb{N}\end{align}
\begin{align} (n,f_n(x))\mapsto \alpha(n,f_n(x))\end{align}
which is injective. Thus, $\alpha\circ \phi:S\to\Bbb{N}$ is injective and so, $S$ is countable.
Please, can anyone show me how to define $\alpha$ explicitly? I would also love to see other proofs too! Thanks!
Best Answer
Say $$S_1=\{a_{11},a_{12},...\}$$ $$S_2=\{a_{21},a_{22},...\}$$ $$...$$
(be aware that this representation corresponds to a choice of enumerations of the countable sets $S_n$ and thus implicitely uses $AC_\omega$).
Then you can count through all elements of $S=\bigcup_{i=1}^\infty S_i$ in the following way (which you could also use to define your $\alpha$):
Your argument is essenatially the same:
(1) Your $f_n:S_n\rightarrow \mathbb{N}$ are the rows of the above picture $$f_n=(a_{n1},a_{n2},a_{n3},...)$$
(2) Your $\phi$ corresponds to writing the $f_n$ in form of a table with rows $f_n$ (like in above picture)
(3) Your $\alpha$ is the way you can count through that table by taking one diagonal after the other.
(*) You are explicitely using $AC_\omega$ when committing to a set of enumerations $\{f_n\}$ of the countable sets $S_n$. You could say above picture implicitly uses $AC_\omega$ since it uses some choice of enumerations for the $S_n$ from the beginning.
You can find an explicite formal definition for $\alpha$ here.