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

• Why isn't this closed as a duplicate? Dec 12, 2013 at 17:29
• i have read "a countable union of countable sets is countable". are they the same question? frankly, it's difficult for me to understand the meaning of the statement.
– 象嘉道
Sep 23, 2017 at 16:33

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?

• Thank you for your incredibly detailed explanation! I have a good understanding on how to prove what I need to now. Thanks! Dec 12, 2013 at 0:12
• I have to ask something about $S_1\cup S_2\cup S_3\cup\cdots=\mathbb Q^+$, though. Wouldn't that make $1\mapsto s_{ii}$, for all $i$? Except if we define that in $\mathbb Q^+$, $\frac{1}{1}\neq\frac{2}{2}\neq\frac{3}{3}\neq\cdots$. Just saying. May 30, 2015 at 2:37
• what if the sets are not disjoint? This mapping would not be 1-1. Ex. if $S_1=S_2$ Oct 23, 2017 at 4:20
• @Hovercouch: thanks for the proof. I think my textbook uses a similar argument, but I'm confused about the last part of it. Do you mind giving it a look? imgur.com/a/02y4Q Mar 22, 2018 at 13:51
• @qwr Why bother skipping over the elements that have already occured? To show it's countable it's sufficient to show there exists a surjection $\mathbb{N} \to \bigcup_{i=1}^{∞}S_i$ so even if it repeats, it doesn't really matter if it's injective or not, count those bad boys again! Jan 8, 2021 at 14:04

@Hovercouch's answer is correct, but the presentation hides a really rather important point that you ought probably to know about. Here it is:

The argument depends on accepting (a weak version of) the Axiom of Choice!

Why so?

You are only given that each $S_i$ is countable. You aren't given up front a way of counting any particular $S_i$, so you need to choose a surjective function $f_i\colon \mathbb{N} \to S_i$ to do the counting (in @Hovercouch's notation, $f_m(n) = s_{mn}$). And, crucially, you need to choose such an $f_i$ countably many times (a choice for each $i$).

That's an infinite sequence of choices to make: and it's a version of the highly non-trivial Axiom of Choice that says, yep, it's legitimate to pretend we can do that.

• But if $S_i$ is countable it means that there is surjection like this. So if there is such function why do we need additional axiom to pick it? Dec 16, 2013 at 14:22
• But there are lots of such surjections for any $S_i$: you need to select one for each $i$. Check out proofwiki.org/wiki/… where the use of choice or its equivalent is made explicit. Dec 16, 2013 at 14:36
• Can't we get rid of need for this axiom if we prove that $A \cup B$ for any two sets $A$ and $B$ and then by induction that it is true for any countable union? Dec 16, 2013 at 14:50
• @Trismegistos: The induction only proves it for every finite union. Not for infinite unions. Aug 6, 2014 at 21:29
• @Trismegistos: You can prove that for every finite length, $1+1+\ldots+1$ is finite. Does that mean that an infinite sum of $1$'s is finite? :-) Aug 7, 2014 at 14:00

Lema 1. The union of two countable sets is countable.

Proof. Let $A = \{a_n : n \in \mathbf N\}$ and $B = \{b_n : n \in \mathbf N\}$. Then we can define the sequence $(c_n)_{n=0}^\infty$ by $$c_{2k} = a_k \quad\text{and}\quad c_{2k+1} = b_k$$ for every $k \in \mathbf N$. Now $A \cup B = \{c_n : n \in \mathbf N\}$ and since it is a infinite set then it is countable.

By Lemma 1 you can prove your proposition by induction on the number of sets of the family

Corollary. The union of a finite family of countable sets is a countable set.

To prove for a infinite family you need the Axiom of choice.

• you need to consider the possibility that $A\cap B\neq \emptyset$
– Kun
Sep 26, 2017 at 9:09
• Even if the two sets aren't disjoint, we have $A\subseteq A\cup B$ where $A$ is countable. Sep 26, 2017 at 11:03

Let $\{A_n\}$ be a countable collection of collection sets. Denote, $A=\cup_{n\in I} A_n$. Now for each $A_n$ define a injection $f_n:A_n\to \mathbb{N}$. Now define a function $f:A\to \mathbb{N}$ as follows, take $x\in A$. Suppose $i$ be the first such that $x\in A_i$. Now define $f(x)=2^i3^{f_i(x)}$. Clearly this is an injection. Now if $A$ is finite then done, if not then $im(f)$ is an infinite subset of $\mathbb{N}$. And it's again countable, so bijective to $\mathbb{N}$. Also, $A$ is bijective to $im(f)$, so, $A$ is bijective to $\mathbb{N}$, done.

Simply put, a set is countable if you can enumerate the elements without forgetting any. (Enumerating the same element twice doesn't matter.)

As you can enumerate the elements in the given sets, you can enumerate them taking the sets in a round-robin fashion, adding one more set on every round.

$1$ of $1$,

$2$ of $1$, $1$ of $2$,

$3$ of $1$, $2$ of $2$, $1$ of $3$,

$4$ of $1$, $3$ of $2$, $2$ of $3$, $1$ of $4$,

$...$

As you can check, no one is missing.

• You didn't mention the AoC. Is there more to your choice of the word 'enumeration' .Enumeration Theory encyclopediaofmath.org/index.php/Enumeration Aug 18, 2017 at 0:06
• you don't need the AoC if you can name the items you are mapping to. Aug 31, 2018 at 3:29

Well, the assertion is that, if you have a countable collection of sets which are countable themselves, then the union of all elements in the collection is also countable. To demonstrate this, try writing the set of natural numbers as the union of countably many infinite disjoint subsets of $\mathbb{N}$ (and, for that, consider decomposing every natural number in its unique prime factorization)

Your sets are $$A_n$$ for $$n \ge 0$$, all of which are countable (i.e. in bijection with $$\mathbb{N}$$); you have to prove that the set $$A = \bigcup_{n \ge 0} A_n$$ is countable. One way is to construct an injection of A into $$\mathbb{N} \times \mathbb{N}$$, which you can do easily (if $$f_0 : A_0 \rightarrow \mathbb{N}$$ is a bijection, then you can define $$g_0(a) = (f_0(a), 0)$$ for all $$a \in A_0$$, then consider $$B_1 = A \setminus A_0$$ and go on... be careful with the domains of definition!). After that, use the classic fact that there is a bijection between $$\mathbb{N} \times \mathbb{N}$$ and $$\mathbb{N}$$, for instance $$(a,b) \mapsto 2^a(2b+1) - 1$$, and conclude with Cantor-Bernstein theorem and the obvious fact that there exists an injection from $$\mathbb{N}$$ to $$A$$.

Using

The wiki definition for countable sets,
The axiom of countable choice,
The make-it-a-disjoint-union technique found here,
The padding-if-necessary the index out to $$\omega$$ technique,
The prime integers form an infinite set,
The prime factorization theorem.

the problem is (eventually) reduced to observing that

$$\quad U =\;\bigsqcup_{p \text{ is a prime}} \{p^n \mid n \ge 1\}$$

is a subset of $$\Bbb N$$.

Note: When there are duplicates in the original sets you'll need to get the smallest index where the element occurs to define the injective mapping into $$U$$.