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

Assume the Axiom of Countable Choice (The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\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 role of ${\mathrm{A}\mathrm{C}}_{\omega }$. It is spent at exactly one step, step 3.1 below, where a surjection $\mathbb{N}\to A_n$ is selected simultaneously for each nonempty $A_n$. The individual countability hypotheses assert that these sets of surjections are nonempty; they specify no simultaneous selection.

Conditionally on $\mathrm{Con}(\mathrm{Z}\mathrm{F})$, ZF alone does not prove the unrestricted countable-union assertion. The later Relative consistency of the Feferman–Levy choice failures over ZF supplies a local finite-fragment proof of the relative consistency of ZF with the reals a countable union of countable sets. Combined with the choice-free uncountability theorem $\mathbb{R}$ is uncountable (Cantor's nested intervals, 1874), this gives the indicated nonprovability: if ZF proved the union assertion, that consistent extension would prove that the reals are both at most countable and uncountable. These are later metatheoretic orientation references, not hypotheses of the union proof below; the consistency assumption is retained.

• 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 $\mathrm{\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\mathrm{\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 proof isolates its exact use of ${\mathrm{A}\mathrm{C}}_{\omega }$ at step 3.1. It does not infer from that proof cost that the hypothesis is necessary; proving such a lower bound belongs to the later symmetric-model development.