# Why is Axiom of Choice required for the proof of countable union of countable sets is countable?

I know that this question has been asked a lot here, some of them are duplicate of each other. I’ve read every single of them, but my problem has not been resolved. I can just memorize that Axiom of Choice (AC) is needed, but I want to be clear of this, logically.

Note : “Countable” here means infinitely countable.

Recall the proof, it goes like this:

First, I have countably many of countable sets. Let me enumerate them to $\langle A_i\rangle_{i\in\mathbb{N}}$. For each $i$, $A_i$ is countable. Since $A_i$ is countable for each $i$, there exists a bijection $h_i:\mathbb{N}\rightarrow A_i$ for each $i$. Then this is where Axiom of Choice (AC) comes into play. There are countably many $A_i$, so I have to choose ‘countably many’ times. Then I’ve got $h_i:\mathbb{N}\rightarrow A_i$ for each $i$ I want.

But why is AC needed?

What I understand about AC is, if I have a collection of non-empty sets, and I want to construct a new set by picking an element from each set in the collection, then AC allows me to pick them to ‘construct’ my new set. This is explicitly stated in its logical formula. For example, if I have a collection $\mathcal{A}=\lbrace A_i\rbrace_{i\in\mathbb{N}}$ where $A_i$ is non-empty for each $i$ and I want to construct a new set $\lbrace a_i\rbrace_{i\in\mathbb{N}}$ such that $a_i\in A_i$ for each $i$, then I need AC to guarantee that such set can be made. However, if my collection $\mathcal{A}=\lbrace A_i\rbrace_{i=0}^n$ is finite, then I can construct the new set without AC, i.e., it can be proved that such $\lbrace a_i\rbrace$ can be constructed without the need of AC.

But what I don’t understand is, why am I not even permitted to just pick an element and manipulate them? Return to the same example, if I have a collection $\mathcal{A}=\lbrace A_i\rbrace_{i\in\mathbb{N}}$ where $A_i$ is non-empty for each $i$, then I know that there exists $a_i\in A_i$ for each $i$. Am I permitted to manipulate $a_i$ for each $i$?, like constructing $\lbrace a_i\rbrace$ by the Axiom of Pair? Can I construct a set $A_i’:=A_i-\lbrace a_i\rbrace$ for each $i$? Each $a_i$ exists logically, and I want to put bracket around them like this $\lbrace a_i\rbrace$. This is allowed by the Axiom of Pair. Of course, I cannot make $\lbrace a_i\rbrace_{i\in\mathbb{N}}$ since this is not implied by any axiom (even by the Axiom of Union or Axiom of Infinity) except AC.

Most answer I found here is, I cannot even 'pick' an element from each set infinitely many times without AC (not to mention constructing a new set from them). Some people even said that each $A_i$ in the proof being countable does not mean that its enumeration is given. Well, in that case, can't I just say that since it does not have enumeration, then it's not countable and hence a contradiction to the assumption? An enumeration must exists. Some might say that it exists but is not given. Then what does 'given' mean in logic? Even in the proof that utilizes AC, we claim that a choice function exists, but not clearly stated 'which' choice function. We only know that it exists and use it to finish the proof. Why is this situation is different from knowing that each bijection $h_i$ exists for each $i$. Why are we permitted to manipulate existing choice function, but not allowed to manipulate existing bijection? Is this related to the fact that it is formulated in First-order logic?

Thank you!

• Your concerns are exactly the kinds of things I wondered about for many years (since roughly 40 years ago), and while I now know more about the issues involved than 40 years ago, what I've most come to realize (this perhaps by the early 1990s for those keeping score) is that it's probably fruitless to worry about AC usage without the proper background. It's like trying to understand topology by reading descriptions at the "rubber sheet geometry" level -- there are too many words with specific precise meanings that are not used in the same way by non-experts in the field. – Dave L. Renfro Sep 21 '16 at 17:01
• An assumption is hidden in the phrase "just picking" the members of the sequence of functions. When written in logical syntax, it amounts to applying Countable Choice, as stated in the A from Rene Schipperus. – DanielWainfleet Sep 21 '16 at 23:31
• I don't think I really understood this until I thought to be skeptical about "picking" just a single element, and figuring out what's going on there. – Hurkyl Sep 22 '16 at 4:31
• My understanding is that the axiom of choice is only "controversial" in cases when there are an uncountably infinite number of choices to make. Those are the cases where "weird" things like the Banach-Tarski paradox and the prisoner hat paradox can happen. Here, it looks like there are not an uncountably infinite number of choices to make. Some people would distinguish "the axiom of countable choice" from "the axiom of choice" and it looks like, at most, the former is used to establish that the union of a countable number of countable sets is countable. – Michael Sep 22 '16 at 12:27
• For the prisoner hat paradox, see "countably infinite hat variant" here: en.wikipedia.org/wiki/Prisoners_and_hats_puzzle – Michael Sep 22 '16 at 12:45

A weak form of AC is used, for while each countable set $A_i$ has a bijection $f_i\colon A_i\rightarrow \mathbb{N}$ this bijection is not unique and AC is required to chose the sequence $\langle f_i:i\in\mathbb{N}\rangle$.

• I know that if I want to construct the sequence $\langle f_i:i\in\mathbb{N}\rangle$, then AC (or its weak form) is needed. But such sequence is not needed in the proof. $f_i$ (or $h_i$ in the post) is just a symbol of each bijection. It can be expressed by other symbols. I only want to use $h_i$ to construct a new function, not to form a set or sequence. – Tommjjerry Sep 21 '16 at 14:27
• The point is not so much that you need a sequence, but that you must chose $f_3$, say, from the many possibilities for $g:A_3\rightarrow\mathbb{N}$, and $f_4$ and $f_5$ etc. In order to define your map you need all of these infinitely many choices to be made all at once, that is where AC comes to the rescue. – Rene Schipperus Sep 21 '16 at 14:33
• Besides answering where the (countable) axiom of choice is used it should be mentioned that the reason why it is used is that without it, it is known to some (e.g. Jech) that the result does not hold. Indeed, for non-believers, the real line is the countable union of countable sets. (I don't know any of this, I just know that others do.) – Airymouse Sep 21 '16 at 16:45
• A sequence $\langle f_i:i\in\mathbb N\rangle$ is needed later in the proof. One $f_i$ is not enough. The proof proceeds by assembling all infinitely many of the chosen $f_i$'s into an enumeration of the union $\bigcup_{i\in\mathbb N}A_i$. – Andreas Blass Sep 21 '16 at 18:29
• Thank you everyone. I think I understand now. Yep, such sequence is needed indeed. I've been thinking since submitting the question. I had to write down the proof formally (with logical symbols). The reason it is needed is because, formally, I'm not allowed to write down infinitely long logical quantifiers (each quantifier for each bijection to choose). But with AC, you only make one quantifier for the entire sequence of bijections. Such a handy axiom. – Tommjjerry Sep 21 '16 at 19:38

Fixing $\alpha: \mathbb N \to \mathbb N \times \mathbb N$ a bijection, the function you (presumably) want to construct is $$n \mapsto h_{\alpha(n)_1}(\alpha(n)_2).$$ In order to make the bijection you want to make/have this definition make sense, you need the function $i \mapsto h_i$, as it is part of the composition. This is the same as the sequence $\langle h_i\rangle_{i \in \mathbb N}$.

If it sounds obvious to you that this function should be available, that's good, because we use AC as an axiom in most everyday mathematics.

Some might say that it exists but is not given. Then what does 'given' mean in logic?

Usually, given means that there is a function which gives it. In this case, that would be a function $i \mapsto h_i$.

I am not sure if this constitutes a full answer, but I hope I can clear some of your confusions. It may not be technically correct at some points (do correct me if this is indeed the case), but this is how I view the situation intuitively. I hope to see a better explanation myself, too!

Each of the sets $A_i$ are countable, so there is a bijection $H_i\colon\mathbb N\to A_i$. But there are many such bijections, infinitely many in fact, and there is no "preferred bijection". What I mean by lack of preferred bijection is that without any additional structure, you cannot "choose" or "write out" the function $h_i$. This is what it means for the bijection to exist but not be given.

Suppose you can prove that the union $A=\bigcup_{i\in\mathbb N}A_i$ is countable. That means that there exists a bijection $h\colon\mathbb N\to A$. Again, it only exists instead of being given, but you only have to pick a bijection once. From this bijection you can construct functions $f_i\colon h^{-1}(A_i)\to A_i$, and it is easy to check that they are in fact bijections.

Each set $h^{-1}(A_i)$ can be naturally bijected with $\mathbb N$. Just identify the smallest element with $0$, the second smallest with $1$, and so on. This bijection is "given" since you can give it explicitly for all $i$ at the same time. Composing with these bijections, you produce bijections $g_i\colon\mathbb N\to A_i$.

Therefore from the single enumeration of $A$ you produce simultaneously an enumeration for each $A_i$. But this amounts to making infinitely many choices simultaneously, by choosing bijections $\mathbb N\to A_i$ for all $i$ in one go. This should not be possible if you have no form of AC at your disposal. That is, countability of $A$ proves more than should be possible without AC. Therefore it is not provable without AC.

Side note: The bijections $\mathbb N\to h^{-1}(A_i)\subset\mathbb N$ produced above also give rise to a bijection $\mathbb N\to\mathbb N^2$. If you can argue that this is impossible without choice (as is the case), you have shown that $A$ is not countable without choice.