Countable union of countable sets, proof without AC?

AI Thread Summary
The discussion focuses on the proof that a countable union of countable sets is countable, questioning the necessity of the axiom of countable choice (AC) in the process. The proof presented relies on defining a countable family of countable sets and establishing bijections without explicitly invoking AC. However, it is argued that while the proof appears to avoid AC, it implicitly requires it to select a specific bijection for each set in the family. The participants highlight that the general formulation of the theorem does not specify which bijection to choose, thus necessitating countable choice. Ultimately, the conversation emphasizes the nuanced relationship between cardinality, bijections, and the axiom of choice in set theory.
tauon
Messages
90
Reaction score
0
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,\\ <br /> and\ let\ \mathcal{F}\ be \ a\ countable\ family\ of\ countable\ sets.\\<br /> <br /> 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 \\<br /> for \ any \ f(p_i):=S_{p_i}\in\mathcal{F}\ there \ is \ a \ bijective \ function \<br /> \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} .\\<br /> Then\\ <br /> \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?
 
Physics news on Phys.org
tauon said:
since \ every \ set \ in \ \mathcal{F} \ is \ countable \\<br /> for \ any \ f(p_i):=S_{p_i}\in\mathcal{F}\ there \ is \ a \ bijective \ function \<br /> \alpha_i:{p_i}^{\mathbb{N}}\rightarrow S_{p_i},\ where \ {p_i}^{\mathbb{N}}:=\{{p_i}^n|\ n\in{\mathbb{N}}^*\}\dots
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##.
 
Back
Top