We have just remarked that the set \(\Z\) is countably infinite, and hence it is countable. Let \(Z_* = \Z \sm \{0\}\text{.}\) It follows from Exercise 6.5.8 (1) that \(\Z_*\) is also countable. By Theorem 6.6.10 we know that \(Z \times \Z_*\) is countable, and it follows from Theorem 6.6.8 that there is a surjective function \(g : \N \to \Z \times \Z_*\text{.}\) Let \(f : \Z \times \Z_* \to \Q\) be defined by \(f ((m, n)) = mn\) for all \((m, n)\in Z \times \Z_*\text{.}\) Given that \(\Q\) consists of all fractions, it is evident that \(f\) is surjective. By Lemma 4.4.4 (2) we see that \(f \circ g\) is a surjective function \(\N \to \Q\text{.}\) Hence \(\Q\) is countable by Theorem 6.6.8. Because \(\Q\) is infinite, as previously remarked, it is therefore countably infinite.
Suppose to the contrary that \(\R\) is countable. Because \(\R\) is infinite, as already observed, it must be countably infinite. From Example 6.5.3 (4) we know that \((0, 1) \# \R\text{,}\) and hence \((0, 1)\) must be countably infinite. Let \(f : \N \to (0, 1)\) be a bijective function. For each \(n\in \N\text{,}\) we can write \(f (n)\) as an infinite decimal f (n) = 0.a1 n a2 n a3 n \dots, where the numbers a1 n, a2 n, a3 n, \dots are integers in {0, 1, \dots, 9}, and where the expansion does not eventually become the number 9 repeating.
For each k\in N, let bk = { 1, if a k k \neq 1 2, if ak k = 1. Observe that bk \neq ak k for all k\in N. Let b be the number represented by the decimal expansion b = 0.b1 b2 b3 \dots . Because b k \neq 9 for all k\in N, then this decimal expansion corresponds to a unique number in (0, 1). We claim that b \neq f (n) for all n\in N. The decimal expansion of any real number is unique if it does not become the number 9 repeating, and therefore if two numbers have different such decimal expansions (even if the difference is by only one digit) then the two numbers are not equal. For each n\in N, the n-th digit in the decimal expansion of f (n) is a n n, whereas the n-th digit in the decimal expansion of b is b n. Hence b \neq f (n) for all n\in N. We have therefore reached a contradiction to the surjectivity of f, and we deduce that R is not countable.
Theorem6.41.
The set of irrational numbers has the same cardinality as \(\R\text{.}\)
Prove that \((0, 1) \times (0, 1) \# (0, 1)\text{.}\) Use the fact that every real number can be expressed uniquely as an infinite decimal, if decimal expansions that eventually become the number \(9\) repeating are not allowed.
Let \(A\) and \(B\) be sets. Suppose that \(A \# \R\) and \(B \# \R\text{.}\) Prove that \(A \times B \# \R\text{.}\)
This exercise is for the reader who is familiar with the complex numbers. Prove that the set of complex numbers \(\C\) has the same cardinality as \(\R\text{.}\)
