9.5: Countable sets

For use in proving theorems, the ideas encountered in the discussion of Hotel Infinity need to be stated more formally. Let us begin with the definitions that form the foundation of the subject.

Definition \(9.6.1\).

Suppose \(A\) and \(B\) are sets.

1. \(A\) and \(B\) have the same cardinality iff there is a bijection from \(A\) to \(B\).
2. \(A\) is countably infinite iff it has the same cardinality as \(\mathbb{N}^{+}\).
3. \(A\) is countable iff either \(A\) is finite or \(A\) is countably infinite.
4. \(A\) is uncountable iff \(A\) is not countable.

Remarks \(9.5.2\).

1. In the terminology of the preceding section, a set is countable if and only if all of its elements can be given rooms in Hotel Infinity (see Exercise \(9.5.6(3)\)).
2. If you are told to show that \(A\) is countably infinite, directly from the definition, then you should find a bijection from \(A\) to \(\mathbb{N}^{+}\). However, because it is so well known that the inverse of a bijection is a bijection, it is acceptable to find a bijection from \(\mathbb{N}^{+}\) to \(A\), instead.

Remarks \(9.5.3\).

One can (and should) think of countable sets as the sets whose elements can be listed in a sequence. The sequence may have only finitely many terms, or may continue forever:

1. A set \(A\) is finite iff its elements can be listed in a sequence \(a_{1}, a_{2}, \ldots, a_{n}), for some \(n\).
2. If the elements of \(A\) can be listed in an infinite sequence \(a_{1}, a_{2}, a_{3}, \ldots), then we may define a bijection \(f: \mathbb{N}^{+} \rightarrow A) by \(f(i)=a_{i}\). Therefore, \(A\) is countably infinite.
3. Conversely, if \(A\) is countably infinite, then there is a bijection \(f: \mathbb{N}^{+} \rightarrow A), so letting \(a_{i}=f(i)\) yields an infinite sequence \(a_{1}, a_{2}, a_{3}, \ldots) that lists the elements of \(A\).

Exercise \(9.5.4\).

Define a binary relation \(\approx\) on the collection of all sets by \[A \approx B \quad \text { iff } \quad A \text { and } B \text { have the same cardinality. }\]

1. Show that \(\approx\) is an equivalence relation.
2. What is the equivalence class of \(\mathbb{N}^{+}\)?

The following fundamental result shows that the smallest infinite sets are the countable ones:

Theorem \(9.5.5\).

1. Every infinite set contains a countably infinite subset.
2. Every subset of a countable set is countable.

Proof

1. Given an infinite set \(A\), it suffices to construct an infinite sequence \(a_{1}, a_{2}, a_{2}, \ldots\) of distinct elements of \(A\), for then \(\left\{a_{1}, a_{2}, a_{3}, \ldots\right\}\) is a countably infinite subset of \(A\).
   1. Since \(A\) is infinite, it is certainly not empty, so it has some elements. Let \(a_{1}\) be any of these elements of \(A\).
   2. Since \(A\) is infinite, we know that a1 is not its only element. Let \(a_{2}\) be any element of \(A\) other than \(a_{1}\). Then \(a_{1}\) and \(a_{2}\) are distinct elements of \(A\).
   3. Since \(A\) is infinite, we know that \(a_{1}\) and \(a_{2}\) are not its only elements. Let \(a_{3}\) be any element of \(A\) other than \(a_{1}\) and \(a_{2}\). Then \(a_{1}\), \(a_{2}\), and \(a_{3}\) are distinct elements of A.
      .
      .
      .
      i. Since \(A\) is infinite, we know that \(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\) are not its only elements. Let \(a_{i}\) be any element of \(A\) other than \(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\). Then the elements \(a_{1}, a_{2}, a_{3}, \ldots, a_{i}\) are distinct.
      .
      .
      .

Continuing this inductive process yields the desired infinite sequence \(a_{1}, a_{2}, a_{3}, \ldots\) of distinct elements of \(A\).

2. Given a subset \(M\) of a countable set \(A\), we wish to show that \(M\) is countable. We may assume \(M\) is infinite, for otherwise it is obviously countable. So we wish to show there is a sequence \(m_{1}, m_{2}, m_{3}, \ldots\) that lists all the elements of \(M\).
   To simplify the notation, let us first consider the case where \(A=\mathbb{N}^{+}\).
   1. Case 1. Assume \(A=\mathbb{N}^{+}\). Let
      1. \(m_{1}\) be the smallest element of \(M\),
      2. \(m_{2}\) be the smallest element of \(M \backslash\left\{m_{1}\right\}\),
      3. \(m_{3}\) be the smallest element of \(M \backslash\left\{m_{1}, m_{2}\right\}\),
      4. \(m_{4}\) be the smallest element of \(M \backslash\left\{m_{1}, m_{2}, m_{3}\right\}\),
         .
         .
         .
         (i) \(m_{i}\) be the smallest element of \(M \backslash\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\). (In other words, \(m_{i}\) is the smallest element of \(M\) that is not in \(\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\).)
         .
         .
         .

For each \(m \in M), notice that if we let \(k\) be the number of elements of \(M\) that are less than \(m\), then \(m_{k+1}=m\). Therefore, every element \(m\) of \(M\) appears in the sequence \(m_{1}, m_{2}, m_{3}, \ldots\).

2. Case 2. The general case. This is left as an exercise.

Exercise \(9.5.6\).

1. Complete Case 2 in the proof of Theorem \(9.5.5\). [Hint: If \(M\) is infinite, then \(A\) must be infinite (why?). List the elements of \(A\) in a sequence \(a_{1}, a_{2}, a_{3}, \ldots\), and apply the argument of Case 1.]
2. Suppose that \(f: A \rightarrow B\), that \(f\) is one-to-one, and that \(B\) is countable. Show that \(A\) is countable.
   [Hint: If \(f\) is not onto, you will want to use the fact that every subset of a countable set is countable.]
3. Show that a set \(A\) is countable iff there exists a one-to-one function \(f: A \rightarrow \mathbb{N}^{+}\).

Remark \(9.5.7\).

Mathematicians think of countable sets as being small — even though they may be infinite, they are almost like finite sets. Consider the following basic properties of finite sets:

1. Any subset of a finite set is finite.
2. The union of two finite sets is finite.
3. More generally, the union of finitely many finite sets is finite.
4. If you have two finite sets, then you can make only finitely many ordered pairs from them. (That is, the Cartesian product of two finite sets is finite.)
5. If you have only finitely many darts to throw, then you can hit only finitely many things with them. That is, if \(f: A \rightarrow B\), and \(A\) is finite, then the image \(f(A)\) is finite

All of the above assertions remain true when the word “finite” is replaced with “countable.” The first assertion was established in Thm. \(9.5.5(2)\); the others are contained in the following important theorem:

Theorem \(9.5.8\).

1. A countable union of countable sets is countable.
2. The cartesian product of two countable sets is countable.
3. The image of a countable set is countable.

Remark \(9.5.9\).

Here are more precise statements of the assertions of Theorem \(9.5.8\):

1. If \(A_{1}, A_{2}, A_{3}, \ldots\) is any sequence of countable sets, then the union \[\bigcup_{i=1}^{\infty} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots\]
   is countable. Also, if \(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\) is any finite sequence of countable sets, then the union \[\bigcup_{i=1}^{n} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots \cup A_{n}\]
   is countable.
2. If \(A\) and \(B\) are any countable sets, then \(A \times B\) is countable.
3. If \(f: A \rightarrow B\), and \(A\) is countable, then \(f(A)\) is countable.

Proof

1. Given either an infinite sequence \(A_{1}, A_{2}, A_{3}, \ldots\) of countable sets, or a finite sequence \(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\), An of countable sets, we wish to show that the the union of the sets is countable. Subsets of a countable set are countable, so there is no harm in assuming:
   • the sequence is infinite (because adding additional terms to the sequence will make the union larger), and
   • each of the sets is infinite (because replacing \(A_{i}\) with an infinite superset will make the union larger).

Now, the numbering method of Eg. \(9.4.3(7)\) shows there is an onto function \(g: \mathbb{N}^{+} \rightarrow \bigcup_{i=1}^{\infty} A_{i}\). So, from 3., we conclude that \(\bigcup_{i=1}^{\infty} A_{i}\) is countable.

2. Given countable sets \(A\) and \(B\), we wish to show that \(A \times B\) is countable. Subsets of a countable set are countable, so there is no harm in assuming that \(A\) and \(B\) are infinite (because replacing A and B with infinite supersets will make the cartesian product larger). Let
   • \(a_{1}, a_{2}, a_{3}, \ldots\) be a list of the elements of \(A\), and
   • \(b_{1}, b_{2}, b_{3}, \ldots\) be a list of the elements of \(B\),

Then the elements of \(A \times B\) are listed in the following table (or matrix): \[\begin{array}{cccccc}
\left(a_{1}, b_{1}\right) & \left(a_{1}, b_{2}\right) & \left(a_{1}, b_{3}\right) & \left(a_{1}, b_{4}\right) & \left(a_{1}, b_{5}\right) & \cdots \\
\left(a_{2}, b_{1}\right) & \left(a_{2}, b_{2}\right) & \left(a_{2}, b_{3}\right) & \left(a_{2}, b_{4}\right) & \left(a_{2}, b_{5}\right) & \cdots \\
\left(a_{3}, b_{1}\right) & \left(a_{3}, b_{2}\right) & \left(a_{3}, b_{3}\right) & \left(a_{3}, b_{4}\right) & \left(a_{3}, b_{5}\right) & \cdots \\
\left(a_{4}, b_{1}\right) & \left(a_{4}, b_{2}\right) & \left(a_{4}, b_{3}\right) & \left(a_{4}, b_{4}\right) & \left(a_{4}, b_{5}\right) & \cdots \\
\left(a_{5}, b_{1}\right) & \left(a_{5}, b_{2}\right) & \left(a_{5}, b_{3}\right) & \left(a_{5}, b_{4}\right) & \left(a_{5}, b_{5}\right) & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}\]

The numbering method of Eg. \(9.4.3(7)\) defines a bijection from \(A \times B \text { to } \mathbb{N}^{+}\). So \(A \times B\) is countable.

3. Suppose \(f: A \rightarrow B\), and \(A\) is countable. By replacing \(B\) with \(f(A)\), we may assume \(f\) is onto; then we wish to show that \(B\) is countable. By Exercise \(9.5.6(2)\), it suffices to define a one-to-one function \(g: B \rightarrow A\). The function \(f\) is onto, so, for each \(b \in B\), there is some \(a \in A\), such that \(f(a)=b\); thus, for each \(b \in B\), we may choose \(g(b)\) to be an element of \(A\) such that \[f(g(b))=b\]
   Then \(g: B \rightarrow A\), and all that remains is to show that g is one-to-one. Given \(b_{1}, b_{2} \in B\), such that \(g\left(b_{1}\right)=g\left(b_{2}\right)\), we have \(f\left(g\left(b_{1}\right)\right)=b_{1}\) and \(f\left(g\left(b_{2}\right)\right)=b_{2}\). Therefore \[b_{1}=f\left(g\left(b_{1}\right)\right)=f\left(g\left(b_{2}\right)\right)=b_{2}\]
   So \(g\) is one-to-one, as desired.

The theorems of this section make it easy to show that many sets are countable. Here are a few important examples:

Exercise \(9.5.10\).

Show that each of the following sets is countable.

1. \(\mathbb{N}^{+}\).
2. \(\mathbb{N}\). [Hint: \(\mathbb{N}=\mathbb{N}^{+} \cup\{0\}\).]
3. \(\mathbb{Z}\). [Hint: Let \(\mathbb{Z}^{-}=\{n \in \mathbb{Z} \mid n<0\}\), so \(\mathbb{Z}=\mathbb{N} \cup \mathbb{Z}^{-}\). The set \(\mathbb{Z}^{−}\) is the image of \(\mathbb{N}^{+}\) under a function.]
4. \(\mathbb{Q}\). [Hint: Let \(\mathbb{Z}^{+}\) be the set of positive integers, so \(\mathbb{Q}\) is the image of \(\mathbb{Z} \times \mathbb{Z}^{\times}\) under the function \(f(a, b)=a / b\).]

It is very important to remember that \(\mathbb{Q}\) is countable. Since \(\mathbb{N}\) and \(\mathbb{Z}\) are subsets of \(\mathbb{Q}\), this implies that \(\mathbb{N}\) and \(\mathbb{Z}\) are also countable.

Exercise \(9.5.11\).

1. Suppose \(A\) is countably infinite, and \(b \notin A\). Show, directly from the definition, that \(A \cup\{b\}\) is countably infinite.
2. Suppose \(A\) is countably infinite, and \(a \in A\). Show, directly from the definition, that \(A \backslash\{a\}\) is countably infinite.
3. Suppose \(A\) and \(B\) are countably infinite and disjoint. Show, directly from the definition, that \(A \cup B\) is countably infinite.
4. Suppose \[A_{1} \text { is disjoint from } B_{1}, \quad A_{1} \text { and } A_{2} \text { have the same cardinality, }\]
   \[A_{2} \text { is disjoint from } B_{2}, \text { and } B_{1} \text { and } B_{2} \text { have the same cardinality. }\]
   Show that (\(A_{1} \cup B_{1}\)) has the same cardinality as (\(A_{2} \cup B_{2}\)).
5. Suppose \(A\) is infinite. Show there is a proper subset \(B\) of \(A\), such that \(B\) has the same cardinality as \(A\). [Hint: Combine Theorem \(9.5.5(1)\) with Exercises (2) and (4).]

OTHER TERMINOLOGY.

Some mathematicians do not consider finite sets to be “countable,” so the terms “countable” and “countably infinite” are synonymous to them. Then, a set that is either finite or countably infinite is said to be “at most countable.” Other mathematicians say that a countably infinite set is “denumerable.