# Where is the axiom of choice used in Rudin's proof of “the countable union of countable sets is countable”?

Baby Rudin proves that the countable union of countable sets is countable. From reading other proofs online, the axiom of choice has to be invoked; however, I'm not seeing immediately where that is used here.

Theorem 2.12. Let $$\{E_n\}$$, $$n=1,2,...$$ be a sequence of countable sets, and put $$S= \bigcup_{n=1}^\infty E_n.$$ Then S is countable.

Proof. Let every set $$E_n$$ be arranged in a sequence $$\{x_{nk}\}, k=1,2,3,…,$$ and consider the infinite array

in which the elements of $$E_n$$ form the $$n$$th row. The array contains all elements of S. As indicated by the arrows, these elements can be arranged in a sequence $$\begin{equation} (17) \ \ \ x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32};… \end{equation}$$ If any two of the sets $$E_n$$ have elements in common, these will appear more than once in (17). Hence there is a subset $$T$$ of the set of all positive integers such that $$S\sim T$$, which shows that $$S$$ is at most countable. Since $$E_1 \subset S$$, and $$E_1$$ is infinite, $$S$$ is infinite, and thus countable.

Does "picking" the elements of each $$E_n$$ and arranging them in a sequence invoke AC? That doesn't seem right, since then it seems like the classic "$$\mathbb{Q}$$ is countable" argument would also invoke choice. Is AC hidden in the "there is a subset $$T$$ of the set of all positive integers such that $$S\sim T$$, which shows that $$S$$ is at most countable" part?

Thanks so much. Any help/insight would be really appreciated.

• "the classic "$\mathbb{Q}$ is countable" argument would also invoke choice" -- usually you exhibit one particular enumeration of $\mathbb{Q}$ to argue this. You don't say, "the fractions with denominator 1 are countable, and so are those with denominator 2, and so on for each denominator $n$". But if you did just say that, you'd be in exactly the same boat, and you'd need the Axiom of (Countable) Choice. – Steve Jessop Jul 13 '15 at 1:21

Yes, you need choice in order to pick a particular sequence for each of the $E_n$s -- remember that all you know about them for the purpose of this proof is that at least one sequence exists; this leaves open the possibility that there will be many sequences and no principled way to select one particular among them.

You're given as an assumption that there is some way to arrange each $E_n$ in a row, but what you need in order to construct a bijection $f:\mathbb N\to S$ is that you use the same enumeration of $E_1$ when you define $f(1)$ as when you define $f(3), f(6), f(10)$, and so on. Likewise, you need to use the same enumeration of $E_n$ each time you pick a number from it. It is remembering a particular choice of sequence for each of the infinitely many $E_n$s that requires you to put those choices into a single mathematical object, and then you need the Axiom of Choice to make sure that such an object exists.

You don't run into this problem when showing that $\mathbb Q$ is countable, because there you know enough about the sets that you can specify a particular sequence to use in each case, and therefore there's no need to make arbitrary choices.

Showing $\mathbb Q$ is countable does not require AC. Showing that a countable union of countable sets is countable does require some form of AC.

Yes, AC is used right at the start where he says let every element of the sequence etc.

Saying $E_1$ is countable says that the elements of $E_1$ can be arranged in a sequence. There are many ways to do this; we have to choose one. We also have to choose one for $E_2$ and one for $E_3$... we have infinitely many "choices" to make.

Proving that $\mathbb N$ is countable does not require any such "choices", because, say, the elements of the form $(1,m)$ are already arranged in a sequence for us.

• But if the elements of E can not be arranged in a sequence, can E be countable? – marty cohen Jul 12 '15 at 21:00
• @martycohen: Yes, of course they can be arranged in a sequence. The problem is that there are many ways to do that, and in order to get a sequence of $\bigcup E_n$, you need to be sure that you use the same sequence for $E_1$ when you define $f(1)$ as when you defined $f(3), f(6), f(10)$, and similarly for each of the other rows. It is remembering a particular choice of sequence for each of the infinitely many $E_n$s that requires you to put those choices into a set, and then you need the Axiom of Choice to make sure that set exists. – Henning Makholm Jul 12 '15 at 21:03
• @marty: remember that what the Axiom of Choice says is (equivalent to) "the Cartesian product of non-empty sets is non-empty". In this case, we have the set of enumerations of $E_1$ (call it $P_1$), the set of enumerations of $E_2$, etc, and any element of the product of those countably many $P_i$ indexed using $\mathbb{N}$, leads to an enumeration of $E$ and we're done. So what we need is the "obvious" (hence an acceptable axiom, at least one hopes so...) "fact" that the infinite product of those $P_i$ sets is non-empty. – Steve Jessop Jul 13 '15 at 1:33