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

Question

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 1

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?

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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)

Answer 7

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

Answer 8

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

Answer 9

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