# Error in a proof that union of a countable number of at most countable sets is at most countable

According to the Set Theory book I am studying, the Axiom of Choice is required to prove that the union of a countable number of at most countable sets is itself at most countable. I seem to have proven this without using choice but I am certain that I made a mistake somewhere! As I use a lot of custom macros, I posted the proof here. I hope this isn't breaking any rules.

I'm pretty sure the error is in Lemma 1 and something that I am doing assumes/requires choice (or well-ordering) but I do not know what. Any help in pointing out the problem would be much appreciated!

"First, since each $A_n$ is at most countable, we have $|A_n| \le \aleph_0$ so that by Lemma 1 there is a function $f_n$ from $\mathbb{N}$ onto $A_n$ since clearly $\mathbb{N}$ is well-ordered."
You are using countable choice to choose these $f_n$'s. All you know is that the set $$F_n:= \{f:\mathbb{N}\to A_n \mid f\ \text{is onto}\}$$ is nonempty for each $n$. How do you select a specific $f_n$ from each of them? In other words, how do you know that $$\prod_{n\in\mathbb{N}} F_n$$ is nonempty?
• What I do not understand is why do we need the AoC to choose a particular sequence $f_n$ but we evidently do not need to choose among the possible sequences that enumerate the countable system of sets (I write it as a sequence in my proof but the book leaves it as a general countable system). It seems to be sufficient here to say that such a sequence exists even though there could be many such sequences. (2/3) – kyp4 Sep 29 '17 at 3:55
• Lemma 1 is perfectly correct except that you need to assume $B$ is nonempty for the reverse direction. – Eric Wofsey Sep 29 '17 at 4:39