|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
union of countable sets
|
(Result)
|
|
|
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.
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 \lbrace A_i \mid i \in \mathbb{N} \rbrace$ 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 $\lbrace r\rbrace$ for each $r\in \mathbb{R}$ is uncountable.
|
"union of countable sets" is owned by CWoo.
|
|
(view preamble | get metadata)
Cross-references: uncountable, union, pairing function, similarity, right, obvious, countably infinite, induction, elements, proof, onto, odd, even, function, well-defined, surjections, conversely, subsets, iff, countable, examples of countable sets, property, useful
There are 3 references to this entry.
This is version 8 of union of countable sets, born on 2009-09-29, modified 2009-09-29.
Object id is 11927, canonical name is UnionOfCountableSets.
Accessed 307 times total.
Classification:
| AMS MSC: | 03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
