$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.4: Some Theorems on Countable Sets

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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).