Proof about Countability and Induction

Question

Let n be a positive integer. Using the fact that the union of two countable sets is countable, use induction to prove that the union of n countable sets is countable.

I did the following.

**We begin by induction on n. Suppose n = 1.

Then we have 1 set and by above, it is countable.

Suppose the union of k sets is countable, for some integer k.

We must show that the union of k+1 sets is also countable.**

From here I am not sure how to "Prove" this without just flat out saying that these would also be countable by the theorem.

Answer 1

You're right in that it's pretty straightforward. Nevertheless, you have to be careful that you don't make illogical jumps.

You have the base case right. You have 1 countable set and so it is trivially countable.

Now consider the union of $k$ countable sets $S_1, S_2, \ldots S_k$ and assume this union is countable. Let us call this union $A$ i.e.

$$A = \bigcup_{i=1}^{k}{S_i}$$.

Now consider another countable set $S_{k+1}$. We want to prove that $\bigcup_{i=1}^{k+1}S_i$ is also countable. Well we have:

$$ \bigcup_{i=1}^{k+1}S_i = \left(\bigcup_{i=1}^{k}S_i \right) \cup S_{k+1} \\ = A \cup S_{k+1} $$

From the induction hypothesis, we know $A$ is countable and $S_{k+1}$ is countable by assumption, and by our rule, we know the union of two countable sets if countable. Since the union of $S_1, S_2, \dots S_{k+1}$ is equal to the union of the countable set $A$ and the countable set $S_{k+1}$, we can conclude that $\bigcup_{i=1}^{k+1}S_i$ is countable.

Note we had to be careful in that we cant just say, the $k+1$ sets are countable because the union of the first $k$ are. Your rule says only the union of two countable sets is countable so you need to make that step of calling the union of the first $k$ a set $A$ and then taking its union with $S_{K+1}$

Answer 2

By definition, a set, $A$, is countable if there is a function $A\rightarrow\mathbb{N}$ such that every $n\in\mathbb{N}$ has finitely many preimages. (This means that for every $n\in\mathbb{N}$ there are only finitely many $a\in A$ with $f(a)=n$.) This is because $A_n$ can be defined to be $f(a)=n$, and then we have expressed A as a countable union of finite sets.

To prove that the set of all finite subsets of $\mathbb{N}$ is countable, we may consider $f(A)=\max A$. The number of sets with maximal element $n$ is finite ($2^{n-1}$), so we may conclude that $A+a$ is indeed countable, given both $A$ and $a$ have countable maximums.

If we let $k=A$ and $1=a$, then we have proven that $k+1$ is countable, because $A+a$ is countable.

Answer 3

As gowrath points out, once you can show that the union of any two countable sets is countable, then you can easily complete your inductive step. But, how do you show that the union of any two countable sets is countable?

Well, take $A$ and $B$ to be countable sets. That means that I can 'list' the elements like so:

$A = a_1, a_2, a_3, ...$ where every element $a\in A$ occurs somewhere on this list

$B =b_1, b_2, b_3, ...$ (same for $B$)

Ok, now create a new list by 'zipping' the two lists together like so:

$a_1, b_1, a_2, b_2, a_3, b_3, ...$

Obviously, every element in $A\cup B$ will be somewhere on this list. Some may occur twice (if they are in both $A$ and $B$), and if you want you can remove duplicatess from this list to get a new list, but the fact that all elements are on the list shows that there is a mapping from the natural numbers to $A\cup B$, and hence $A\cup B$ is countable.