Proving the union of countably many countable sets is countable without axiom of choice.

Question

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.

Answer 1

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}$.

Answer 2

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:

1. Some columns might be finite

2. Number of columns might be finite

3. Some elements might be repeated

From the enumeration above, {$A_i$}$_{i=1}^\infty$ is countable.