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!

  • 14
    $\begingroup$ Why isn't this closed as a duplicate? $\endgroup$
    – Asaf Karagila
    Commented Dec 12, 2013 at 17:29
  • $\begingroup$ 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. $\endgroup$
    Commented Sep 23, 2017 at 16:33

9 Answers 9


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?

  • 9
    $\begingroup$ Thank you for your incredibly detailed explanation! I have a good understanding on how to prove what I need to now. Thanks! $\endgroup$
    – wonggr
    Commented Dec 12, 2013 at 0:12
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 30, 2015 at 2:37
  • 5
    $\begingroup$ what if the sets are not disjoint? This mapping would not be 1-1. Ex. if $S_1=S_2$ $\endgroup$ Commented Oct 23, 2017 at 4:20
  • $\begingroup$ @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 $\endgroup$
    – ensbana
    Commented Mar 22, 2018 at 13:51
  • 5
    $\begingroup$ @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! $\endgroup$
    – William
    Commented 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.

  • 3
    $\begingroup$ 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. $\endgroup$ Commented Dec 16, 2013 at 14:36
  • 16
    $\begingroup$ @Trismegistos: The induction only proves it for every finite union. Not for infinite unions. $\endgroup$
    – Asaf Karagila
    Commented Aug 6, 2014 at 21:29
  • 8
    $\begingroup$ @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? :-) $\endgroup$
    – Asaf Karagila
    Commented Aug 7, 2014 at 14:00
  • 2
    $\begingroup$ @AsafKaragila Yes it clicks now. I wondered for many years why infinite sums are not commutative because I expected you can prove by induction that they are commutative. I suspect I somehow mixed potential with actual infinity. $\endgroup$ Commented Aug 7, 2014 at 14:34
  • 2
    $\begingroup$ In fact, there is a model of ZF in which the reals are a countable union of countable sets! $\endgroup$
    – JMM
    Commented Dec 31, 2022 at 2:47

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

Proof. Let $A = \{a_n : n \in \mathbb N\}$ and $B = \{b_n : n \in \mathbb 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 \mathbb N$. Now $A \cup B = \{c_n : n \in \mathbb 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.

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

Let $\{A_n\}$ be a countable collection of countable sets. Denote, $A=\cup_{n\in I} A_n$. Now for each $A_n$ define an 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.

  • $\begingroup$ This is slick ${}$ $\endgroup$
    – FShrike
    Commented Jun 29, 2023 at 19:26

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.

  • $\begingroup$ You didn't mention the AoC. Is there more to your choice of the word 'enumeration' .Enumeration Theory encyclopediaofmath.org/index.php/Enumeration $\endgroup$ Commented Aug 18, 2017 at 0:06
  • 2
    $\begingroup$ you don't need the AoC if you can name the items you are mapping to. $\endgroup$ Commented 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$.



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


This proof is equivalent to showing the set of rational numbers is countable.

Let $A_i=\{a_{i1},a_{i2},a_{i3},...\}$ be the $i$th countable set for $i \in \mathbb{Z}^+$. We can arrange the elements of $\bigcup_{i=1}^\infty A_i$ into an array $M=[m_{ij}]$ where $m_{ij}$ is the $j$th element of the $i$th countable set for $i,j \in \mathbb{Z}^+$. From here we can show $\bigcup_{i=1}^\infty A_i$ is countable by listing the entries of $M$ as follows: first, list every entry $m_{ij}$ such that $i+j=2$; second, list every entry $m_{ij}$ such that $i+j=3$; third, list every entry $m_{ij}$ such that $i+j=4$; and so on and so forth. In general, list all $k-1$ entries such that $i+j=k$ for $k = 2,3,4,...$

Listing entries in this way is analogous to how Cantor listed the rational numbers in his famous proof showing the rational numbers were indeed countable. Simply let $m_{ij} = \frac{i}{j}$ and list the entries as follows

enter image description here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .