# Countable union of countable sets, proof without AC?

1. Nov 6, 2012

### tauon

Pretty much every proof of this I've seen uses the axiom of countable choice at some part or another, and I never got why, since it's pretty cumbersome. Here's the sketch of a proof I wrote for the "fact" that a countable union of countable sets is countable:

$$Let \ P:=\{\pi\in\mathbb{N}|\ \pi \ is \ prime\},\ \mathcal{E}:=\{{\pi}^n|\ \pi\in P,\ n\in{\mathbb{N}}^*\}\subset\mathbb{N},\ p:\mathbb{N}\rightarrow P \ a \ bijective \ function, \ p(i)=p_i\in P,\\ and\ let\ \mathcal{F}\ be \ a\ countable\ family\ of\ countable\ sets.\\ Since \ \mathcal{F}\ is \ countable,\ there\ is\ a\ bijective\ function\ f:P\rightarrow\mathcal{F},\ f(\pi):=S_{\pi}\in\mathcal{F},\ and \ since \ every \ set \ in \ \mathcal{F} \ is \ countable \\ for \ any \ f(p_i):=S_{p_i}\in\mathcal{F}\ there \ is \ a \ bijective \ function \ \alpha_i:{p_i}^{\mathbb{N}}\rightarrow S_{p_i},\ where \ {p_i}^{\mathbb{N}}:=\{{p_i}^n|\ n\in{\mathbb{N}}^*\}\ and \ \alpha_i ({p_i}^k)=s_{{p_i}^k}\in S_{p_i} .\\ Then\\ \bigcup_{S\in\mathcal{F}}S = \bigcup_{\pi\in P}S_{\pi}=\bigcup_{i\in\mathbb{N}}S_{p_i}=\bigcup_{i\in\mathbb{N}}\bigcup_{k\in{\mathbb{N}}^*}\{s_{{p_i}^k}\}=\bigcup_{\epsilon\in\mathcal{E}}\{s_{ \epsilon }\}\ (q.e.d.)$$

As I see it, I'm only using the definition and one property of cardinality, and a few properties of natural numbers (primes in particular), none of which (at least to my knowledge) require the use of the axiom of choice. But I'm no expert... Does this proof (implicitly) use some version of the axiom of choice? If so, where?

2. Nov 6, 2012

### Erland

For each $i$, there are infinitely many such bijections from ${p_i}^{\mathbb{N}}$ to $S_{p_i}$, and the theorem, in its general formulation, does not tell which one of them to choose and call $\alpha_i$. We need countable choice to select one such bijection for each $i$.