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

Question

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!

Answer 1

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$.

Answer 2

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$.

Answer 3

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.