1.4: Some Theorems on Countable Sets

We now derive some corollaries of Definition 4 in § 3.

COROLLARY $\PageIndex{1}$

If a set $A$ is countable or finite, so is any subset $B \subseteq A$.

For if $A \subset D_{u}^{\prime}$ for a sequence $u,$ then certainly $B \subseteq A \subseteq D_{u}^{\prime}$

COROLLARY $\PageIndex{2}$

If $A$ is uncountable (or just infinite), so is any superset $B \supset A$.

For, if $B$ were countable or finite, so would be $A \subseteq B,$ by Corollary 1

Theorem $\PageIndex{1}$

If $A$ and $B$ are countable, so is their cross product $A \times B$

Proof

If $A$ or $B$ is $\emptyset,$ then $A \times B=\emptyset,$ and there is nothing to prove.

Thus let $A$ and $B$ be nonvoid and countable. We may assume that they fill two infinite sequences, $A=\left\{a_{n}\right\}, B=\left\{b_{n}\right\}$ (repeat terms if necessary). Then, by definition, $A \times B$ is the set of all ordered pairs of the form

$$\left(a_{n}, b_{m}\right), \quad n, m \in N$$

Call $n+m$ the $r a n k$ of the pair $\left(a_{n}, b_{m}\right) .$ For each $r \in N,$ there are $r-1$ pairs of rank $r :$

$$\left(a_{1}, b_{r-1}\right),\left(a_{2}, b_{r-2}\right), \ldots,\left(a_{r-1}, b_{1}\right)$$

We now put all pairs $\left(a_{n}, b_{m}\right)$ in one sequence as follows. We start with

$$\left(a_{1}, b_{1}\right)$$

as the first term; then take the two pairs of rank three,

$$\left(a_{1}, b_{2}\right),\left(a_{2}, b_{1}\right)$$

then the three pairs of rank four, and so on. At the $(r-1)$ st step, we take all pairs of rank $r,$ in the order indicated in $(1)$.

Repeating this process for all ranks ad infinitum, we obtain the sequence of pairs

$$\left(a_{1}, b_{1}\right),\left(a_{1}, b_{2}\right),\left(a_{2}, b_{1}\right),\left(a_{1}, b_{3}\right),\left(a_{2}, b_{2}\right),\left(a_{3}, b_{1}\right), \ldots$$

in which $u_{1}=\left(a_{1}, b_{1}\right), u_{2}=\left(a_{1}, b_{2}\right),$ etc.

By construction, this sequence contains all pairs of all ranks $r,$ hence all pairs that form the set $A \times B$ (for every such pair has some rank $r$ and so it must eventually occur in the sequence). Thus $A \times B$ can be put in a sequence. $\square$

COROLLARY $\PageIndex{3}$

The set $R$ of all rational numbers is countable.

Proof

Consider first the set $Q$ of all positive rationals, i.e.,

$$\text{ fractions } \frac{n}{m}, \text{ with } n, m \in N$$

We may formally identify them with ordered pairs $(n, m),$ i.e., with $N \times N$ We call $n+m$ the rank of $(n, m) .$ As in Theorem $1,$ we obtain the sequence

$$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{2}{2}, \frac{3}{1}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \ldots$$

By dropping reducible fractions and inserting also 0 and the negative rationals, we put $R$ into the sequence

$$0,1,-1, \frac{1}{2},-\frac{1}{2}, 2,-2, \frac{1}{3},-\frac{1}{3}, 3,-3, \ldots, \text{ as required. } \square$$

Theorem $\PageIndex{2}$

The union of any sequence $\left\{A_{n}\right\}$ of countable sets is countable.

Proof

As each $A_{n}$ is countable, we may put

$$A_{n}=\left\{a_{n 1}, a_{n 2}, \dots, a_{n m}, \ldots\right\}$$

(The double subscripts are to distinguish the sequences representing different sets $A_{n} .$ ) As before, we may assume that all sequences are infinite. Now, $U_{n} A_{n}$ obviously consists of the elements of all $A_{n}$ combined, i.e., all $a_{n m}(n, m \in N) .$ We call $n+m$ the $r a n k$ of $a_{n m}$ and proceed as in Theorem $1,$ thus obtaining

$$\bigcup_{n} A_{n}=\left\{a_{11}, a_{12}, a_{21}, a_{13}, a_{22}, a_{31}, \ldots\right\}$$

Thus $\cup_{n} A_{n}$ can be put in a sequence. $\square$

Note 1: Theorem 2 is briefly expressed as

"Any countable union of countable sets is a countable set."

(The term "countable union" means "union of a countable family of sets", i.e., a family of sets whose elements can be put in a sequence $\left\{A_{n}\right\} .$ ) In particular, if $A$ and $B$ are countable, so are $A \cup B, A \cap B,$ and $A-B$ (by Corollary 1$)$.

Note 2: From the proof it also follows that the range of any double sequence$\left\{a_{n m}\right\}$ is countable. (A double sequence is a function $u$ whose domain $D_{u}$ is $N \times N ;$ say, $u : N \times N \rightarrow B .$ If $n, m \in N,$ we write $u_{n m}$ for $u(n, m)$ here $u_{n m}=a_{n m} . )$

To prove the existence of uncountable sets, we shall now show that the interval

$$[0,1)=\{x | 0 \leq x<1\}$$

of the real axis is uncountable.

We assume as known the fact that each real number $x \in[0,1)$ has a unique infinite decimal expansion

$$0 . x_{1}, x_{2}, \dots, x_{n}, \dots$$

where the $x_{n}$ are the decimal digits (possibly zeros), and the sequence $\left\{x_{n}\right\}$ does not terminate in nines (this ensures uniqueness)."

Theorem $\PageIndex{3}$

The interval$[0,1)$ of the real axis is uncountable.

Proof

We must show that no sequence can comprise all of $[0,1) .$ Indeed, given any $\left\{u_{n}\right\},$ write each term $u_{n}$ as an infinite fraction; say,

$$u_{n}=0 . a_{n 1}, a_{n 2}, \dots, a_{n m}, \dots$$

Next, construct a new decimal fraction

$$z=0 . x_{1}, x_{2}, \ldots, x_{n}, \dots$$

choosing its digits $x_{n}$ as follows.

If $a_{n n}$ (i.e., the $n$ th digit of $u_{n} )$ is $0,$ put $x_{n}=1 ;$ if, however, $a_{n n} \neq 0,$ put $x_{n}=0 .$ Thus, in all cases, $x_{n} \neq a_{n n},$ i.e., $z$ differs from each $u_{n}$ in at least one decimal digit (namely, the $n$ th digit). It follows that $z$ is different from all $u_{n}$ and hence is not in $\left\{u_{n}\right\},$ even though $z \in[0,1)$.

Thus, no matter what the choice of $\left\{u_{n}\right\}$ was, we found some $z \in[0,1)$ not in the range of that sequence. Hence $n o\left\{u_{n}\right\}$ contains all of $[0,1) . \square$

Note 3: By Corollary $2,$ any superset of $[0,1),$ e.g., the entire real axis, is uncountable.

Note 4: Observe that the numbers $a_{n n}$ used in the proof of Theorem 3 form the diagonal of the infinitely extending square composed of all $a_{n m} .$ Therefore, the method used above is called the diagonal process (due to G. Cantor).