elementary set theory - Prove that the union of countably many countable sets is countable.

I am doing some homework exercises and stumbled upon this question. I don't know where to start.

Prove that the union of countably many countable sets is countable.

Just reading it confuses me.

Any hints or help is greatly appreciated! Cheers!

Answer

Let's start with a quick review of "countable". A set is countable if we can set up a 1-1 correspondence between the set and the natural numbers. As an example, let's take $\mathbb{Z}$, which consists of all the integers. Is $\mathbb Z$ countable?

It may seem uncountable if you pick a naive correspondence, say $1 \mapsto 1$, $2 \mapsto 2 ...$, which leaves all of the negative numbers unmapped. But if we organize the integers like this:

$$0$$
$$1, -1$$
$$2, -2$$
$$3, -3$$
$$...$$

We quickly see that there is a map that works. Map 1 to 0, 2 to 1, 3 to -1, 4 to 2, 5 to -2, etc. So given an element $x$ in $\mathbb Z$, we either have that $1 \mapsto x$ if $x=0$, $2x \mapsto x$ if $x > 0$, or $2|x|+1 \mapsto x$ if $x < 0$. So the integers are countable.

We proved this by finding a map between the integers and the natural numbers. So to show that the union of countably many sets is countable, we need to find a similar mapping. First, let's unpack "the union of countably many countable sets is countable":

1. "countable sets" pretty simple. If $S$ is in our set of sets, there's a 1-1 correspondence between elements of $S$ and $\mathbb N$.




2. "countably many countable sets" we have a 1-1 correspondence between $\mathbb N$ and the sets themselves. In other words, we can write the sets as $S_1$, $S_2$, $S_3$... Let's call the set of sets $\{S_n\}, n \in \mathbb N$.




3. "union of countably many countable sets is countable". There is a 1-1 mapping between the elements in $\mathbb N$ and the elements in $S_1 \cup S_2 \cup S_3 ...$

So how do we prove this? We need to find a correspondence, of course. Fortunately, there's a simple way to do this. Let $s_{nm}$ be the $mth$ element of $S_n$. We can do this because $S_n$ is by definition of the problem countable. We can write the elements of ALL the sets like this:

$$s_{11}, s_{12}, s_{13} ...$$
$$s_{21}, s_{22}, s_{23} ...$$
$$s_{31}, s_{32}, s_{33} ...$$
$$...$$

Now let $1 \mapsto s_{11}$, $2 \mapsto s_{12}$, $3 \mapsto s_{21}$, $4 \mapsto s_{13}$, etc. You might notice that if we cross out every element that we've mapped, we're crossing them out in diagonal lines. With $1$ we cross out the first diagonal, $2-3$ we cross out the second diagonal, $4-6$ the third diagonal, $7-10$ the fourth diagonal, etc. The $nth$ diagonal requires us to map $n$ elements to cross it out. Since we never "run out" of elements in $\mathbb N$, eventually given any diagonal we'll create a map to every element in it. Since obviously every element in $S_1 \cup S_2 \cup S_3 ...$ is in one of the diagonals, we've created a 1-1 map between $\mathbb N$ and the set of sets.

Let's extend this one step further. What if we made $s_{11} = 1/1$, $s_{12} = 1/2$, $s_{21} = 2/1$, etc? Then $S_1 \cup S_2 \cup S_3 ... = \mathbb Q^+$! This is how you prove that the rationals are countable. Well, the positive rationals anyway. Can you extend these proofs to show that the rationals are countable?