# 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.

Any hints or help is greatly appreciated! Cheers!

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}\mathbb{Z}$$, which consists of all the integers. Is $$\mathbb Z\mathbb Z$$ countable?

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

$$00$$
$$1, -11, -1$$
$$2, -22, -2$$
$$3, -33, -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 $$xx$$ in $$\mathbb Z\mathbb Z$$, we either have that $$1 \mapsto x1 \mapsto x$$ if $$x=0x=0$$, $$2x \mapsto x2x \mapsto x$$ if $$x > 0x > 0$$, or $$2|x|+1 \mapsto x2|x|+1 \mapsto x$$ if $$x < 0x < 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 $$SS$$ is in our set of sets, there's a 1-1 correspondence between elements of $$SS$$ and $$\mathbb N\mathbb N$$.

2. "countably many countable sets" we have a 1-1 correspondence between $$\mathbb N\mathbb N$$ and the sets themselves. In other words, we can write the sets as $$S_1S_1$$, $$S_2S_2$$, $$S_3S_3$$... Let's call the set of sets $$\{S_n\}, n \in \mathbb N\{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\mathbb N$$ and the elements in $$S_1 \cup S_2 \cup S_3 ...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}s_{nm}$$ be the $$mthmth$$ element of $$S_nS_n$$. We can do this because $$S_nS_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_{11}, s_{12}, s_{13} ...$$
$$s_{21}, s_{22}, s_{23} ...s_{21}, s_{22}, s_{23} ...$$
$$s_{31}, s_{32}, s_{33} ...s_{31}, s_{32}, s_{33} ...$$
$$......$$

Now let $$1 \mapsto s_{11}1 \mapsto s_{11}$$, $$2 \mapsto s_{12}2 \mapsto s_{12}$$, $$3 \mapsto s_{21}3 \mapsto s_{21}$$, $$4 \mapsto s_{13}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 $$11$$ we cross out the first diagonal, $$2-32-3$$ we cross out the second diagonal, $$4-64-6$$ the third diagonal, $$7-107-10$$ the fourth diagonal, etc. The $$nthnth$$ diagonal requires us to map $$nn$$ elements to cross it out. Since we never "run out" of elements in $$\mathbb N\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 ...S_1 \cup S_2 \cup S_3 ...$$ is in one of the diagonals, we've created a 1-1 map between $$\mathbb N\mathbb N$$ and the set of sets.

Let's extend this one step further. What if we made $$s_{11} = 1/1s_{11} = 1/1$$, $$s_{12} = 1/2s_{12} = 1/2$$, $$s_{21} = 2/1s_{21} = 2/1$$, etc? Then $$S_1 \cup S_2 \cup S_3 ... = \mathbb Q^+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?