Proof P3154
on R262: Countable union of countable sets is countable

P3154

Due to results

we may assume that $J$ is nonempty and that $X_j$ is nonempty for each $j \in J$. Since $X_j$ is a countable set for each $j \in J$, then there exists a surjection $f_j : \mathbb{N} \to X_j$ for each $j \in J$. Consider then the map \begin{equation} F : J \times \mathbb{N} \to \bigcup_{j \in J} X_j, \quad F(i, j) = f_i(j) \end{equation} First, we wish to show that $F$ is a surjection. To this end, fix $x \in \bigcup_{j \in J} X_j$. By the definition of set union, there now exists $i \in J$ such that $x \in X_i$. Since $f_i : \mathbb{N} \to X_i$ is a surjection, there exists $j \in \mathbb{N}$ such that $x = f_i(j) = F(i, j)$. Thus, $F$ is a surjection. Since $J$ (and $\mathbb{N}$) is countable, result R263: Binary cartesian product of countable sets is countable shows that the Cartesian product $J \times \mathbb{N}$ is countable; hence there exists a surjection $G : \mathbb{N} \to J \times \mathbb{N}$. Now result R315: Composition of surjections is surjection states that the composition \begin{equation} F \circ G : \mathbb{N} \to \bigcup_{j \in J} X_j \end{equation} is a surjection, which finishes the proof. $\square$

(i) | R4580: Empty set union equals the empty set |

(ii) | R507: Empty set is countable |

(iii) | R4270: Set union with empty set |

we may assume that $J$ is nonempty and that $X_j$ is nonempty for each $j \in J$. Since $X_j$ is a countable set for each $j \in J$, then there exists a surjection $f_j : \mathbb{N} \to X_j$ for each $j \in J$. Consider then the map \begin{equation} F : J \times \mathbb{N} \to \bigcup_{j \in J} X_j, \quad F(i, j) = f_i(j) \end{equation} First, we wish to show that $F$ is a surjection. To this end, fix $x \in \bigcup_{j \in J} X_j$. By the definition of set union, there now exists $i \in J$ such that $x \in X_i$. Since $f_i : \mathbb{N} \to X_i$ is a surjection, there exists $j \in \mathbb{N}$ such that $x = f_i(j) = F(i, j)$. Thus, $F$ is a surjection. Since $J$ (and $\mathbb{N}$) is countable, result R263: Binary cartesian product of countable sets is countable shows that the Cartesian product $J \times \mathbb{N}$ is countable; hence there exists a surjection $G : \mathbb{N} \to J \times \mathbb{N}$. Now result R315: Composition of surjections is surjection states that the composition \begin{equation} F \circ G : \mathbb{N} \to \bigcup_{j \in J} X_j \end{equation} is a surjection, which finishes the proof. $\square$