## You are here

Homeunion of countable sets

## Primary tabs

# union of countable sets

In this entry, we prove a useful property of countability which will gives us many more examples of countable sets.

###### Proposition 1.

$A\cup B$ is countable iff $A$ and $B$ are countable.

###### Proof.

Clearly, if $A\cup B$ is countable, then $A$ and $B$ are each countable, as they are subsets of a countable set.

Conversely, suppose $f:\mathbb{N}\to A$ and $g:\mathbb{N}\to B$ are two surjections. Let $C=A\cup B$. Define $h:\mathbb{N}\to C$ as follows: $h(2n+1)=f(n)$ for $n=0,1,\ldots$, and $h(2n)=g(n)$, for $n=1,2,\ldots$. Then $h$ is a well-defined function, for each $i\in\mathbb{N}$ is either even or odd, so $h(i)$ is defined in either case. Finally, $h$ is onto, for if $c\in C$, then $c\in A$ or $c\in B$. If $c\in A$, then $h(2p+1)=c$ for some $p$, and if $c\in B$, then $h(2q)=c$ for some $q$. Hence $C$ is countable. ∎

The idea behind the above proof is to realize that we can list elements of $C$ in the following manner:

$f(1)$ | $f(2)$ | $f(3)$ | $f(4)$ | $f(5)$ | $\cdots$ |

$g(1)$ | $g(2)$ | $g(3)$ | $g(4)$ | $g(5)$ | $\cdots$ |

Therefore, $h$ is defined so its first value is $f(1)$, its second value is $g(1)$, third is $f(2)$, fourth $g(2)$, etc… In the end, all of the elements of $C$ are exhausted by this way of counting.

As a corollary, we have

###### Corollary 1.

$A_{1}\cup A_{2}\cup\cdots\cup A_{n}$ is countable iff each $A_{i}$ is.

###### Proof.

This is true by induction. ∎

The property can easily be extended to the countably infinite case, the proof of which is just a variant of the above methodology:

###### Proposition 2.

$\bigcup\{A_{i}\mid i\in\mathbb{N}\}$ is countable iff each $A_{i}$ is.

###### Proof.

Again, one direction is obvious, so we concentrate on the other direction.

Let $A=A_{1}\cup A_{2}\cup\cdots$. Suppose we have surjections $f_{i}:\mathbb{N}\to A_{i}$ for $i=1,2,\ldots$. Then listing elements of $A$ in the following manner (table below on the left)

$i\backslash j$ | $1$ | $2$ | $3$ | $\cdots$ |
---|---|---|---|---|

$1$ | $f_{1}(1)$ | $f_{1}(2)$ | $f_{1}(3)$ | $\cdots$ |

$2$ | $f_{2}(1)$ | $f_{2}(2)$ | $f_{2}(3)$ | $\cdots$ |

$3$ | $f_{3}(1)$ | $f_{3}(2)$ | $f_{3}(3)$ | $\cdots$ |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

$i\backslash j$ | $1$ | $2$ | $3$ | $\cdots$ |
---|---|---|---|---|

$1$ | $f(1)$ | $f(2)$ | $f(4)$ | $\cdots$ |

$2$ | $f(3)$ | $f(5)$ | $f(8)$ | $\cdots$ |

$3$ | $f(6)$ | $f(9)$ | $f(13)$ | $\cdots$ |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

provides a surjection $f:\mathbb{N}\to A$ (table above on the right). The first few values of $f$ are

$f(1)=f_{1}(1),\quad f(2)=f_{1}(2),\quad f(3)=f_{2}(1),\quad f(4)=f_{1}(3),% \quad f(5)=f_{2}(2),\quad\ldots$ |

∎

Notice the similarity between the function $f$ above, and the pairing function used in the proof that $\mathbb{N}^{2}$ is countable here.

Remark. However, the property fails when there are uncountably many sets to deal with. For example, the union of $\{r\}$ for each $r\in\mathbb{R}$ is uncountable.

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections