# Showing that $S_1 \cup S_2$ is countable [duplicate]

Let's say that $S_1$ and $S_2$ are two countable infinite sets that are disjoint (i.e. $S_1 \cap S_2 = \emptyset$). How would you show that $S_1 \cup S_2$ is also countable?

## marked as duplicate by Asaf Karagila♦, dustin, Mark Bennet, apnorton, Lord_FarinJan 30 '15 at 23:06

• What do you think about the problem? – anomaly Jan 30 '15 at 21:39
• Well, can you think of a way to count the elements of the union? – Mankind Jan 30 '15 at 21:41

So there is a bijection $f: \mathbb{N} \rightarrow S_1$ and another bijection $g: \mathbb{N} \rightarrow S_2$. Then consider $h: \mathbb{N} \rightarrow S_1 \cup S_2$ defined by $h(n) = f({n \over 2})$ if $n$ is even, and $h(n) = g(m)$ where $n = 2m+1$ is odd. So we define a sequence

$$h(0), h(1), h(2), h(3), h(4), h(5), \ldots = f(0), g(0), f(1), g(1), f(2), g(2), \ldots$$

which is (show this formally!) a bijection between $\mathbb{N}$ and $S_1 \cup S_2$.

The set $S=S_{1}\cup S_{2}$ is countable if both sets, $S_{1}$ and $S_{2}$, are countable. It is not necessarily for the subsets of $S$ to be disjoint (or mutually disjoint if there are more than two subsets of $S$). A very similar question to it can be read in Theorem 2.6 in Measures, Integrals and Martingales. There is a proof below this theorem.

• So basically, if S1 U S2 is countable, then both S1 and S2 are countable. Therefore any union or interest between the two is countable right? – a22asin Jan 30 '15 at 23:08
• If $S$ is countable then all of its subsets are countable too, for example $S_{1}\subseteq S$ and $S_{2}\subseteq S$. If $S_{1}$ and $S_{2}$ are countable then $S_{1}\cup S_{2}$ is countable. – UnknownW Jan 30 '15 at 23:36

Your claim follows from the following result. You don't need the sets to be disjoint.

Claim: The union of countable many countable sets is countable.

Proof: Let $\{A_i : i \in I \subseteq \mathbb N\}$ be a countable collection of countable sets.

Since each $A_i$ is countable, we can write $A_i = \{a_j^{(i)} : j \in J_i \subseteq \mathbb N\}$.

Define $f : \displaystyle \bigcup_{i \in I} A_i \to \mathbb N^2$ by $f(x) = (i, j)$ where $i$ is the smallest element in $I$ (which we know exists, since $\mathbb N$ is well-ordered and $I$ is a subset of $\mathbb N$) such that $x = a_j^{(i)}$.

$f$ is injective and hence $\operatorname{card} \displaystyle \bigcup_{i \in I} A_i \leq \operatorname{card} (\mathbb N^2) = \aleph_0$ since $\mathbb N^2$ is countable.

Conclude that the union of countable many countable sets is countable.