ThmDex – An index of mathematical definitions, results, and conjectures.
Result R262 on D16: Countable set
Countable union of countable sets is countable
Formulation 0
Let $J$ be a D16: Countable set such that
(i) $X_j$ is a D16: Countable set for each $j \in J$
(ii) $\bigcup_{j \in J} X_j$ is the D77: Set union of $\{ X_j \}_{j \in J}$
Then $\bigcup_{j \in J} X_j$ is a D16: Countable set.
Subresults
R4627
R3506: Finite union of countable sets is countable
Proofs
Proof 0
Let $J$ be a D16: Countable set such that
(i) $X_j$ is a D16: Countable set for each $j \in J$
(ii) $\bigcup_{j \in J} X_j$ is the D77: Set union of $\{ X_j \}_{j \in J}$
Due to results
(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$