2
$\begingroup$

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

  • 0
    @Martin Okay. So, my argument makes sense when it is finite union of countable sets. Am$i$right?2012-07-22

1 Answers 1

6

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.

  • 0
    Katlus: Yes, this is true because we *can* choose from finitely many sets.2012-07-22