Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let ${{E_n}}_{n\in \mathbb{N}}$ be a sequence such that every $E_n$ is countable.

Let $g_n : \mathbb{N} \to E_n$ be a bijection for every $n\in \mathbb{N}$.

Let $\alpha (n,k) = g_n(k)$

Let $A$ be the union of $E_n$'s.

Then $\alpha : \mathbb{N} × \mathbb{N} \to A$ is a surjective function.

Since $\mathbb{N} \times \mathbb{N}$ is equipotent with $\mathbb{N}$, there exists a surjective function $f: \mathbb{N}\to A$.

Let $[n]$={$m\in \mathbb{N}$|$f(m)=f(n)$} for every $n\in \mathbb{N}$.

Since $f$ is surjective, for every $n\in \mathbb{N}$, $[n]\ne \emptyset$.

Since $[n] \subset \mathbb{N}$, $[n]$ is well-ordered.

Let $l_n$ designate the least element of $[n]$.

Let $B=\{l_n \in \mathbb{N} | n\in \mathbb{N}\}$

Then $f_{[B]}$ : $B\to A$ is a bijection.

Since $B\subset \mathbb{N}$, $B$ is at most countable. Since $A$ is infinite, $B$ is countable, hence $A$ is countable.

I don't know where i used AC in my argument. Help

share|improve this question
1  
Let $g_n : \mathbb{N} \to E_n$ be a bijection for every $n\in \mathbb{N}$. On this place you have chosen one element from the non-empty set of bijections between $\mathbb N$ and $E_n$, for each $n$. –  Martin Sleziak Jul 22 '12 at 11:31
    
You can pick $g_1$. You can pick $g_2$. You can pick $g_k$ for any fixed $k$. But if you want to create a single object $g$ that is a bijection $g_i$ for each natural $i$, you need infinitely many choices. –  sdcvvc Jul 22 '12 at 11:47
    
@Martin Okay. So, my argument makes sense when it is finite union of countable sets. Am i right? –  Katlus Jul 22 '12 at 12:04
add comment

1 Answer

up vote 6 down vote accepted

You used countable choice when you chose $g_n$.

It is true that for every countable set there is an injection from the said set into $\mathbb N$, however to choose exactly one for every set requires choice. If, however, you are given the injections then the union is in fact countable, since there is no need to choose bijections.

Note that if we only wish to take union over finitely many countable sets then we can choose finitely many injections and the argument follows. Similarly the finite product of countable sets is countable and non-empty, whereas infinite products could be empty even if all sets are finite.

See also the last part in this answer.

share|improve this answer
    
Then is 'Finite union of countable sets is countable' true in ZF? –  Katlus Jul 22 '12 at 11:33
    
Katlus: Yes, this is true because we can choose from finitely many sets. –  Asaf Karagila Jul 22 '12 at 11:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.