- #1
tauon
- 90
- 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:
[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?
[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?