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

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

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

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