# Countable union of countable sets(ZF)

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

-
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

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.