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:(adsbygoogle = window.adsbygoogle || []).push({});

[tex]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.)[/tex]

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Countable union of countable sets, proof without AC?

**Physics Forums | Science Articles, Homework Help, Discussion**