# Diagram used to prove if $A_i$ are countable then $\bigcup\limits^{\infty}A_i$ is countable

I'm working my way through the very early stages of Abbott's analysis book, and am stuck on a particular segment regarding cardinality—countable sets in particular. He has not yet introduced the axiom of choice, yet he states in an exercise that the following diagram suffices to prove that an infinite union of a countably infinite collection of countable sets is countable.

How does the following diagram lead to a proof of theorem $1.5.8$ (on the inifinte union of countable sets)? $$\begin{array}{col1col2col3col4} 1 & 3 & 6 & 10 & 15 & \cdots\\ 2 & 5 & 9 & 14 & \cdots\\ 4 & 8 & 13 & \cdots \\ 7 & 12 & \cdots \\ 11 & \cdots \\ \vdots \end{array}$$

So as I said, I'm confused how we can accept any "picture-proof" without even a discussion of the axiom of choice. This is also different from Cantor's diagonalization method, so I'm not sure how this works as a proof.

• @copper.hat There is need for it in order to prove the statement in the title, though, which is what OP aims for. May 14, 2018 at 16:13
• @AloizioMacedo: I don't see how the AOC is needed? May 14, 2018 at 16:21
• @copper.hat You need to collectively select bijections from every $A_i$ when proving that the union is countable. C.f. here, for example. May 14, 2018 at 16:23
• @AloizioMacedo: Thanks, clearly I need a review! May 14, 2018 at 16:26

As was pointed out in the comments, there is no need for the axiom of choice to prove that there is a bijection of $\mathbb{N}$ to $\mathbb{N}^2$, call it $b$, which is obtained as in your diagram.

However, in order to prove the statement in the title of your question, one needs some kind of choice. This is because we are not talking about $\mathbb{N}^2$ in the general case, and we need to collectively select countable bijections.

Explicitly, let $A_i$ be a sequence of sets, select bijections $f_i:A_i \to \mathbb{N}$, and define $$g: \mathbb{N} \times \mathbb{N} \to \bigcup_i A_i$$ $$(m,n) \mapsto f_m(n).$$ You can prove that this is surjective, and hence that $\bigcup_i A_i$ is countable. This last argument, as written, could also be believed to depend on the axiom of choice. This can be circumvented, though. Sketchly, since $g \circ b$ is surjective you can, for every set $(g \circ b)^{-1}(a)$, pick its least element in order to define a right inverse for $g \circ b$, which gives an injection from $\bigcup_i A_i$ to $\mathbb{N}$. And thus you can either appeal to Schroder-Bernstein (which does not use AC) or to the arguably simpler fact that every subset of $\mathbb{N}$ is countable, and the right inverse is a bijection to a subset of $\mathbb{N}$.

However, the AC in the bold text cannot be circumvented (and, indeed, the result is not true without some kind of choice).

Some more discussion can be seen here, for example.

Now, regarding the subjective point of your question:

So as I said, I'm confused how we can accept any "picture-proof" without even a discussion of the axiom of choice.

What follows is a personal POV:

This is arguably a pedagogic issue. Talking about necessity of the axiom of choice when students have other dire needs in mind when learning analysis is maybe not a good option, and best left for later (or simply for another context). This is true even for the need of specification and its correct usage, say. In my country (and, from what I've seen, this happens elsewhere) there is an underlying assumption by students that analysis is the subject where we learn how to prove things (i.e., everything and anything) rigorously. That is not true, imho, and also a bit damaging for the student. Analysis is the subject where we learn estimates, convergence, regularity etc. We learn to "prove things rigorously" in Mathematics as a whole, and even then it is not the ultimate goal of the subject. Nevertheless, context is more important than by-the-book rigour in determining what should go where and when.

Having said that, it would probably not hurt to make a slight mention about the AC after the statement of the exercise. It would satisfy the curious reader, and not make him stray away or overload him with information: he can simply choose to postpone this momentarily without hindering his momentum on his studies.

• Thank you very much for the detailed explanation!
– 高田航
May 14, 2018 at 18:02