Question

Show that the union of a countable number of countable sets is countable.

Short answer

Union of countable number of countable sets is countable.

Step-by-step solution

Step 1:

DEFINITIONS:

A set is countable if it is finite or countably infinite.

A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).

A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

The function f is one-to-one if and only if $f\left(a\right)=f\left(b\right)$implies that a = b for all a and b in the domain.

X is a subset of Y if every element of X is also an element of Y. Notation: |A| < |B| .

Definition (2): There is a one-to-one function from A to B if and only if .

Difference A - B : All elements in A that are NOT in B (complement of B with respect to A).

Step 2:

Given: $A_i$is countable with $\mathrm{i}\in {\mathrm{Z}}^{+}$.

To proof: $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n$is countable.

PROOF:

FIRST STEP- We start by defining sets that are pairwise disjoint (thus the intersection of each with any other set is always empty).

$\begin{array}{r}{B}_1=A_1\\ B_2=A_2-A_1\\ B_3=A_3-\left(A_1\cup A_2\right)\\ \cdots \\ B_n=A_n-\left(A_1\cup A_2\cup \dots \cup A_{n-1}\right)\end{array}$

Let us consider an element with $x\in \left(B_n\cap B_m\right)$ (note if then interchange the indices n and m), then $\mathrm{x}\in {\mathrm{A}}_n\text{and}\mathrm{x}\notin \left({\mathrm{A}}_1\cup A_2\cup \dots \cup A_{n-1}\right).\mathrm{x}\notin \left({\mathrm{A}}_1\cup A_2\cup \dots \cup A_{n-1}\right)$. implies $x\notin A_i$with i = 1,...n - 1 . Since $m<n,\mathrm{x}\notin A_m$, . Thus the intersection of two different sets is empty and thus the $B_i$are pairwise disjoint.

Step 3:

SECOND STEP- Check that $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n=\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$.

By the above definitions of $B_n$, we note that each is a subset of $A_n:B_n\subseteq A_n$: . Taking the union over all n’s:

$\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n\subseteq \underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$

On the other hand, if $x\in \underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n$, then x is an element of at least one $A_i$. Let $j\in Z^{+}$be the smallest integer such that $x\in A_j$, then $x\in B_j$(by the above definition of ) and thus x is also an element of the union $x\in \underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$. By the definition of subset, we have then shown

$\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\subseteq \underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n$

Since $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\text{and}\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\subseteq \underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n\text{,}$, we have then shown that the two sets are equal $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n=\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$.

Step 4:

THIRD STEP- Determine that $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$is countable.

The subset of a countable set is also countable. Since is countable and since , is countable as well.

A set $B_n\subseteq A_n,B_n$is countable if and only if $\mathrm{y}\text{if}\left|B_n\right|\le {\mathrm{Z}}^{+}$.

By definition (2): There exists a one-to-one function ${\mathrm{f}}_n:{\mathrm{B}}_n\to {\mathrm{Z}}^{+}$.

Let us define f (if , then there exist a unique integer n such that ).

$f:\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\to Z^{+},f\left(b\right)=p_n^{f_n\left(b\right)}\text{when}\mathrm{b}\in \mathrm{B}$

Where represents the nth prime number ( we take the prime number, because the image of the functions might take on the same values and the powers of different prime numbers are always different integer).

It remains to be checked that f is one-to-one. Let $f\left(x\right)=f\left(y\right)\text{. If}x\in B_n\text{and}y\in B_m\text{,}$ , then:

$p_n^{f_n\left(\mathrm{x}\right)}=p_m^{f_m\left(y\right)}$

Since the powers of different prime numbers are always different integers, $p_{n}and{p}_m$then have to be the same prime number and thus n = m .

$p_n^{f_n\left(x\right)}=p_m^{f_n\left(y\right)}$

The two numbers are the same, if their powers are the same.

$f_n\left(x\right)=f_n\left(y\right)$

Since $f_n$is one-to-one:

x = y

Thus f is a one-to-one function.

f is a one-to-one function from $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\text{to}{Z}^{+}$ . By definition (2):

$\left|\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\right|\le \left|Z^{+}\right|$

A set $t\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$is countable if and only if $\left|\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n\right|\le \left|Z^{+}\right|$. Thus we have then shown that $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} B_n$is countable and thus $\underset{n=1}{\overset{\mathrm{\infty }}{\cup }} A_n$is countable as well.