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.

• Since the axiom of choice is only needed to choose the bijections... Jun 4, 2018 at 8:53
• Also, the axiom of choice tag is for questions related to the necessity or usage of the axiom of choice in a proof. This question is about neither. Jun 4, 2018 at 11:42

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

• I don't get it, since each function $\mathcal f _ n$ goes from $\omega$ to each specified set, are you suggesting to take the inverse of it? I have just edited my question to specify the $\mathcal f _ n$ functions go from $\omega\$ to $\mathcal a _n$ . Jun 4, 2018 at 2:56
• Yes. Let $f_n$ be any function that injects $a_n$ into $\omega$. Observe that the existence of the following family of functions $\{f_n:n\in\omega\}$ is all that is needed from the axiom of choice since we need to choose $f_n$ for infinitely many $n$. Jun 4, 2018 at 4:11

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.

• But this way you would be using Axiom of Choice to build the arangement aren't you? Jun 4, 2018 at 5:07