Proving the union of countably many countable sets is countable without axiom of choice. Let $\{\mathrm a _ n \mid \mathrm n \in \omega\}$ be a countably family of countable sets. Prove $\bigcup _{n\in \omega} a _i$ is countable. 
We can't suppose axiom of choice but, to balance things out we can suppose there's a family of bijections $\mathcal f _ n :\omega\ \rightarrow\ \mathcal a _ n\ $ for each $n$ in $\omega$ . 
I started by making each set from the family disjoint to each other by defining $\mathrm b_0 = \mathrm a_0$, $\mathrm b_n = \bigcup_{i = 0}^{n-1} a_i$ and so on. It all seemed to work fine since $\bigcup_{n\in \omega} b_i = \bigcup_{n\in \omega} a_i$ and i was then almost able to arrange the elements of each set in some sort of table from which i could build a bijection from $\omega \times\omega $ to $\omega$.  
To do so, i needed to define new functions $\mathcal g_n$'s from the $\mathcal f_n$'s i had. First i can define $g_0 = f_0$. But then i can't figure out how to index the next elements in $b_1$ without overlaping nor using axiom of choice.  
Any wise advice will be truly appreciated. 
 A: Fix $n_0$. We have $f_{n_0}$ injects $a_{n_0}$ into $\mathbb{N}$. Consider the following injection $g_{n_0}\circ f_{n_0}$, where $g_{n_0}:m\mapsto p_{n_{0}}^m$ and $p_{n_0}$ is the $n_0$-th prime number under the usual ordering.
Then $\bigcup_{n\in\mathbb{N}}(g_n\circ f_n)$ is the desired injection from $\bigcup_{n\in\mathbb{N}} a_n$ to $\mathbb{N}$.
A: The proof is similar to show that the rationals are countable. 
Let {$A_i$}$_{i=1}^\infty$ be a countable family of countable sets. Consider an array whose first columns enumerates every member of $A_1$, and the second column enumerate every member of $A_2$ and so on.
\begin{bmatrix}
    A_{(1,1)}       &  & A_{(2,1)} &  \rightarrow& A_{(3,1)} & \\
    \downarrow       &  & \uparrow&  & \downarrow \\
    A_{(1,2)} & \rightarrow& A_{(2,2)}& &A_{(3,2)} \\
           &  &  &  & \downarrow\\
    A_{(1,3)}       & \leftarrow & A_{(2,3)} & \leftarrow & A_{(3,3)}\\
    \downarrow       \\
\end{bmatrix}
Take into account three things:


*

*Some columns might be finite

*Number of columns might be finite

*Some elements might be repeated
From the enumeration above, {$A_i$}$_{i=1}^\infty$ is countable.
