39
$\begingroup$

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!

$\endgroup$
  • 11
    $\begingroup$ Why isn't this closed as a duplicate? $\endgroup$ – Asaf Karagila Dec 12 '13 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$ – 象嘉道 Sep 23 '17 at 16:33
46
$\begingroup$

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?

$\endgroup$
  • 2
    $\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 Dec 12 '13 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$ – Julius D. Selle May 30 '15 at 2:37
  • 1
    $\begingroup$ what if the sets are not disjoint? This mapping would not be 1-1. Ex. if $S_1=S_2$ $\endgroup$ – IntegrateThis Oct 23 '17 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 Mar 22 '18 at 13:51
  • $\begingroup$ Here are the relevant definitions: imgur.com/a/0FTvg $\endgroup$ – ensbana Mar 22 '18 at 13:53
36
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Trismegistos Dec 16 '13 at 14:22
  • $\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$ – Peter Smith Dec 16 '13 at 14:36
  • $\begingroup$ 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? $\endgroup$ – Trismegistos Dec 16 '13 at 14:50
  • 5
    $\begingroup$ @Trismegistos: The induction only proves it for every finite union. Not for infinite unions. $\endgroup$ – Asaf Karagila Aug 6 '14 at 21:29
  • 1
    $\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 Aug 7 '14 at 14:00
15
$\begingroup$

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.

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

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – CopyPasteIt Aug 18 '17 at 0:06
  • 1
    $\begingroup$ you don't need the AoC if you can name the items you are mapping to. $\endgroup$ – Q the Platypus Aug 31 '18 at 3:29
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.