# Proof verification: A countable union of countable sets is countable

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!

• Why is $\alpha$ injective? What about $(1,8)$ and $(2,2)$? – Michael Burr Sep 19 '18 at 9:05
• @Michael Burr: Thanks for your response but please, how should I define $\alpha$ or should I just say there exists $\alpha$? – Omojola Micheal Sep 19 '18 at 9:08
• @Michael Burr: I have edited it but how do I construct such a function? – Omojola Micheal Sep 19 '18 at 9:11
• What if $x$ is in multiple sets, how is $\phi$ defined in this case? – Michael Burr Sep 19 '18 at 9:26
• @Michael Burr: I have re-defined $x$ to be in $S_n$ for each $n\in\Bbb{N}$. Then, that suffices I think! – Omojola Micheal Sep 19 '18 at 9:45

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.

• +1! Thank you very much! I also know of this approach! Thanks anyways! – Omojola Micheal Sep 19 '18 at 10:37
• What do you say about my own proof? – Omojola Micheal Sep 19 '18 at 10:38
• Your Approach is essentially the same as the diagonal argument above. – FWE Sep 19 '18 at 11:11
• Just a general remark: this approach hides the appeal to the axiom of choice very well. – Asaf Karagila Sep 19 '18 at 11:29
• true. However, it appears useful to have this idea in the back-head as a guidance. – FWE Sep 19 '18 at 11:34