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?

  • $\begingroup$ The product of sets is empty iff at least on of the sets is empty. $\endgroup$ – William Elliot Sep 29 '17 at 1:40
  • 2
    $\begingroup$ @WilliamElliot How do you prove that if a product is empty, then one of the sets is empty? $\endgroup$ – John Griffin Sep 29 '17 at 1:47
  • $\begingroup$ Does this mean that Lemma~1 is actually correct? I am a little confused by your answer due to not having studied the AoC in depth yet (as it's the next chapter in the book). I did just read/skim that chapter and it confirmed a lot of things I suspected about it. In that chapter they prove this theorem using choice and do mention choosing the sequences as you do. (1/3) $\endgroup$ – kyp4 Sep 29 '17 at 3:51
  • $\begingroup$ 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) $\endgroup$ – kyp4 Sep 29 '17 at 3:55
  • 1
    $\begingroup$ Lemma 1 is perfectly correct except that you need to assume $B$ is nonempty for the reverse direction. $\endgroup$ – Eric Wofsey Sep 29 '17 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.