Countable set of finite sets is countable (without the axiom of choice). So i have the infinite family of sets:
$$\{A_0, A_1, A_2 \dots\}$$
and $\forall i \in \omega,\; A_i$ is finite. I need to show that $\cup A_i$ is countable  ($\exists f: \cup A_i \rightarrow \omega $ and f is bijection).
I seem to understand it intuitively, but I can't prove it. I also don't have to use the axiom of choice. Any tips ?
 A: Proof with axiom of choice :
For every $i \geq 0$, let $\varphi_i : A_i \rightarrow \mathbb{N}$ be an injective map. Define
$\varphi : \bigcup_{i \geq 0} A_i \rightarrow \mathbb{N}^2$ by
$$\varphi(x)=(i_0, \varphi_{i_0}(x))$$
where $i_0$ is any integer such that $x \in A_{i_0}$. Then it is easy to see that $\varphi$ is injective.
It remains to compose $\varphi$ with an injective map $\mathbb{N}^2 \rightarrow \mathbb{N}$ (which is easy to construct) to get an injection from $\bigcup_{i \geq 0} A_i $ to $\mathbb{N}$, which let you conclude that $\bigcup_{i \geq 0} A_i $ is countable.
A: This statement cannot be proven without appeal to axiom of choice. To be precise, it is consistent with ZF axioms that there is a countable family of sets $A_0,A_1,A_2,\dots$ such that each $A_i$ has two elements, and yet $\bigcup_{i\in\omega}A_i$ is not countable. Families of sets like that are sometimes known as "Russell's socks", because of the relation to (in)famous analogy about how you can't pick out socks from infinitely many pairs of socks without using the axiom of choice.
You can find this result and more interesting results concerning Russell's socks in this paper by Herrlich and Tachtsis.
