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.


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!

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

enter image description here

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.