Countable unions of at most countable sets, assuming $\mathrm{AC}_\omega$

Assume the Axiom of Countable Choice (The Axiom of Countable Choice ($\mathrm{AC}_\omega$)). Let $(A_n)_{n \in \mathbb{N}}$ be a family of at most countable sets (Finite, countably infinite, countable, uncountable) indexed by $\mathbb{N}$. Then

$U = \bigcup_{n \in \mathbb{N}} A_n$

is at most countable.

The hypothesis $\mathrm{AC}_\omega$ is not decoration and it is not removable. It is spent at exactly one step, step 3.1 below, where one surjection $\mathbb{N} \to A_n$ is selected for every $n$ at once. Each $A_n$ has such surjections, in general many of them, and the countability assumption provides no rule for singling one out. Without some choice principle the theorem is not available at all: ZF alone does not prove it, conditionally on the consistency of ZF, as recorded among this page's false statements and discussed in the remarks below, where that item is named and linked. The consistency hypothesis is not a formality and cannot be dropped: the separation rests on an external independence result that this library quotes rather than proves, and it cannot be stated without it.

• An at most countable index set is no more general. If $I$ is at most countable and $(A_i)_{i \in I}$ are at most countable, then either $I$ is empty, and the union is $\varnothing$, or a surjection $r : \mathbb{N} \to I$ exists (A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$) and $\bigcup_{i \in I} A_i = \bigcup_{n \in \mathbb{N}} A_{r(n)}$, which the theorem covers. That reindexing uses no choice.

• The two-set union needs no choice at all, and neither does any union of finitely many sets: with $A$ and $B$ both at most countable and nonempty, fix surjections $f, g : \mathbb{N} \to A, B$ (two choices made one after the other, which is ordinary existential instantiation, not a choice principle) and put $u(0,k) = f(k)$ and $u(n,k) = g(k)$ for $n \ne 0$, a surjection $\mathbb{N} \times \mathbb{N} \to A \cup B$. This is the form used in The irrationals are uncountable, and keeping it separate from the countable case is the whole point of flagging step 3.1.

• The failure without choice is not a technicality about exotic sets: if ZF is consistent, then it is consistent with ZF that $\mathbb{R}$ itself is a countable union of countable sets (FALSE: countable unions of countable sets are countable is a theorem of ZF), even though $\mathbb{R}$ is provably uncountable in ZF ($\mathbb{R}$ is uncountable (Cantor's nested intervals, 1874)).