It is written in tag page of Axiom of choice in MSE that Countable union of countable sets is countable is a theorem which follows from AC. Do we really need AC to prove this? Please see following proof from Real Analysis by Bartle and Sherbert. I am not able to figure out if I am using AC here or not.

Theorem If $A(m)$ is a countable set for each $m\in\mathbb{N}$, then the union $A := \bigcup_m A(m)$ is countable.

Proof. For each $m\in\mathbb{N}$, let $f(m)$ be a surjection of $\mathbb{N}$ onto $A(m)$. We define $g: \mathbb{N} \times \mathbb{N} \to A$ by $g(m,n) := \{f(m)\}(n)$.

We claim that $g$ is a surjection. Indeed, if $a \in A$, then there exists a least $m \in \mathbb{N}$ such that $a$ is in $A(m)$ whence there exists a least $n \in\mathbb{N}$ such that $a = \{f(m)\}(n)$. Therefore, $a = g(m,n)$. Since $\mathbb{N}\times\mathbb{N}$ is countable, it follows from the following theorem that there exists a surjection $f : \mathbb{N} \to \mathbb{N}\times\mathbb{N}$ whence $g\circ f$ is a surjection of $\mathbb{N}$ onto $A$. Now again apply the following theorem to conclude that $A$ is countable.

Theorem The following statements are equivalent:
(a) $S$ is a countable set. (b) There exists a surjection of $\mathbb{N}$ onto $S$. (c) There exists an injection of $S$ into $\mathbb{N}$.

Proof. (a)$\implies$(b) If $S$ is finite, there exists a bijection $h$ of some set $\mathbb{N}_n$ onto $S$ and we define $H$ on $\mathbb{N}$ by $$ H(k) :=\begin{cases} h(k), &\text{for $k = 1,\dots, n$,}\\ h(n), &\text{for $k > n$.} \end{cases} $$ Then $H$ is a surjection of $\mathbb{N}$ onto $S$.

If $S$ is countably infinte, there exists a bijection $H$ of $\mathbb{N}$ onto $S$, which is also a surjection of $\mathbb{N}$ onto $S$.

(b)$\implies$(c) If $H$ is a surjection of $\mathbb{N}$ onto $S$, we define $g : S \to \mathbb{N}$ by letting $g(s)$ be the least element in the set $H(-1)(s) := \{n \in \mathbb{N}: H(n) = s\}$. To see that $g$ is an injection of $S$ into $\mathbb{N}$, note that if $s, t \in S$ and $n := g(s) = g(t)$, then $s = H(n) = t$.

(c)$\implies$(a) If $g$ is an injection of $S$ into $\mathbb{N}$, then it is a bijection of $S$ onto $g(S) \subset \mathbb{N}$. and $g(S)$ is countable, whence the set $S$ is countable. Q.E.D.

  • $\begingroup$ If you look at the "Related" list on the side you will find several other questions with the same content, and the same answer more or less. $\endgroup$ – Asaf Karagila Sep 23 '14 at 16:28
  • $\begingroup$ @AsafKaragila One more question in topology I did few days before. "Topology generated by a basis has members which are arbitary union of basis elements." But in this proof we used Generalized distributive law which uses AC in this proof. So basically theorem in "" is dependent on AC only. Are there models in which this is not true $\endgroup$ – Sushil Sep 23 '14 at 16:33
  • $\begingroup$ I'm not even sure what you are asking. Just because the union of countable sets don't have to be countable doesn't mean it doesn't exist somehow. $\endgroup$ – Asaf Karagila Sep 23 '14 at 16:35
  • $\begingroup$ Okay I'll post another question then with good notation $\endgroup$ – Sushil Sep 23 '14 at 16:36

Yes. We really need the axiom of choice. When you say "let $f(m)$ be a surjection" you have chosen a surjection, one of continuum many.

There are infinitely many sets in your union, so you had to make infinitely many choices. This is exactly where the axiom of choice is used.

  • $\begingroup$ Okay I didn't even noticed it $\endgroup$ – Sushil Sep 23 '14 at 16:25
  • $\begingroup$ but we can prove it using axiom of countable choice right? Same proof $\endgroup$ – Sushil Feb 25 '15 at 12:20
  • 3
    $\begingroup$ Yes. You only make countably many choices here. $\endgroup$ – Asaf Karagila Feb 25 '15 at 12:23
  • $\begingroup$ @AsafKaragila I am sorry to come back to this after, well, 4 years. I got confused with "one of continuum many" .. please correct me if I am wrong: there is at least one surjection for each A(m), and there are $\omega$ of those right? by continuum you mean $\aleph_1$? thanks in advance $\endgroup$ – mate89 Dec 17 '18 at 6:05
  • 1
    $\begingroup$ @mate89: Continuum is $2^{\aleph_0}$ which is not necessarily $\aleph_1$, even with choice; and without choice is not necessarily well-ordered either. $\endgroup$ – Asaf Karagila Dec 17 '18 at 6:06

In the absence of countable choice we need to make a clearer distinction between something being countable and it being counted, in the same way that in topology we distinguish between manifolds being orientable and being oriented. A countable set is a set for which there exists a bijection with $\mathbb{N}$ (what you call countable I call at most countable); a counted set is a set equipped with a bijection with $\mathbb{N}$. With this notion it is possible to rescue "a countable union of countable sets is countable" into a statement which requires no choice, namely

"a counted union of counted sets can be counted."

This amounts to the function $g$ being provided as part of the data rather than needing to be conjured up. It is almost always the case in practice that you can actually find countings reasonably explicitly so this is the result you're actually using anyway.


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.