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