Dismiss Notice
Join Physics Forums Today!
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?

  1. Nov 6, 2012 #1
    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:

    [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} .\\
    \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?
  2. jcsd
  3. Nov 6, 2012 #2


    User Avatar
    Science Advisor

    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##.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook