We often think of real numbers as their decimal representations. By a (decimal) digit, we mean an integer between \(0\) and \(9\text{.}\) For a positive integer \(n\text{,}\) we find the digits \(d_K,d_{K-1},\ldots,d_2,d_1,d_0\) for some \(K\) (each \(d_j\) an integer between \(0\) and \(9\)) such that
We often assume \(d_K \neq 0\) (avoiding leading zeros). To represent \(n\text{,}\) we write the sequence of digits: \(n = d_K d_{K-1} \cdots d_2 d_1 d_0\text{.}\)
Similarly, we represent some rational numbers. For certain numbers \(x\text{,}\) we can find nonnegative integers \(K\) and \(M\) and digits \(d_K,d_{K-1},\ldots,d_1,d_0,d_{-1},\ldots,d_{-M}\text{,}\) such that
Not every real number has such a representation. Even the simple rational number \(\nicefrac{1}{3}\) does not. The irrational number \(\sqrt{2}\) does not have such a representation either. To get a representation for all real numbers, we must allow infinitely many digits.
Consider only real numbers in the interval \([0,1]\text{.}\) If we find a representation for these, adding integers to them obtains a representation for all real numbers. Take an infinite sequence of decimal digits:
For every \(x \in (0,1]\) there exists an infinite sequence of digits \(0.d_1d_2d_3\ldots\) that represents \(x\text{.}\) There exists a unique representation such that
\begin{equation}
D_n < x \leq D_n+\frac{1}{{10}^n} \qquad \text{for all } n \in \N.
\end{equation}
Therefore, \(0.d_1d_2d_3\ldots\) represents a unique number \(x \coloneqq \sup_{n\in
\N} D_n \in [0,1]\text{.}\) As \(x\) is a supremum, \(D_n \leq x\text{.}\) Take \(m \in \N\text{.}\) If \(m < n\text{,}\) then \(D_m - D_n \leq 0\text{.}\) If \(m > n\text{,}\) then computing as above
We move on to the second item. Take any \(x \in (0,1]\text{.}\) First, we tackle the existence. For convenience, let \(D_0 \coloneqq 0\text{.}\) Then, \(D_0 < x \leq D_0 + {10}^{-0}\text{.}\) Suppose we have defined the digits \(d_1,d_2,\ldots,d_n\text{,}\) and that \(D_k < x \leq D_k + {10}^{-k}\text{,}\) for \(k=0,1,2,\ldots,n\text{.}\) We need to define \(d_{n+1}\text{.}\)
By the Archimedean property of the real numbers, find an integer \(j\) such that \(x-D_n \leq j {10}^{-(n+1)}\text{.}\) Take the least such \(j\) and obtain
Let \(d_{n+1} \coloneqq j-1\text{.}\) As \(D_n < x\text{,}\) we have \(d_{n+1} = j-1 \geq 0\text{.}\) On the other hand, since \(x-D_n \leq {10}^{-n}\text{,}\) we have that \(j\) is at most 10, and therefore \(d_{n+1} \leq 9\text{.}\) So \(d_{n+1}\) is a decimal digit. Since \(D_{n+1} = D_n + d_{n+1} {10}^{-(n+1)}\text{,}\) add \(D_n\) to the inequality (1.3) above:
Consider \(D_{n} < x \leq D_{n} + {10}^{-n}\text{.}\) As \(D_n < x\) for all \(n\text{,}\) we have \(\sup \{ D_n : n \in \N \} \leq x\text{.}\) The second inequality for \(D_n\) implies
\begin{equation}
x - \sup \{ D_m : m \in \N \}
\leq
x - D_n \leq 10^{-n} .
\end{equation}
As the inequality holds for all \(n\) and \({10}^{-n}\) can be made arbitrarily small (see Exercise 1.5.8), we have \(x \leq \sup \{ D_m : m \in \N \}\text{.}\) Therefore, \(\sup \{ D_m : m \in \N \} = x\text{.}\)
What is left to show is the uniqueness. Suppose \(0.e_1e_2e_3\ldots\) is another representation of \(x\text{.}\) Let \(E_n\) be the \(n\)-digit truncation of \(0.e_1e_2e_3\ldots\text{,}\) and suppose \(E_n < x \leq E_n + {10}^{-n}\) for all \(n \in \N\text{.}\) Suppose for some \(K \in \N\text{,}\)\(e_n = d_n\) for all \(n < K\text{,}\) so \(D_{K-1} = E_{K-1}\text{.}\) Then
Hence, both \(e_K\) and \(d_K\) are the largest integer \(j\) such that \(j < (x - D_{K-1}){10}^K\text{,}\) and therefore \(e_K = d_K\text{.}\) In other words, the representation is unique.
The representation is not unique if we do not require \(D_n < x\) for all \(n\text{.}\) For example, for the number \(\nicefrac{1}{2}\text{,}\) the method in the proof obtains the representation
\begin{equation}
0.49999\ldots .
\end{equation}
However, \(\nicefrac{1}{2}\) also has the representation \(0.50000\ldots\text{.}\)
The only numbers that have nonunique representations are ones that end in an infinite sequence of \(0\)s or an infinite sequence of \(9\)s, because the only representation for which \(D_n = x\) is one where all digits past the \(n\)th digit are zero. In this case, there are exactly two representations of \(x\) (see the exercises).
Let us give another proof of the uncountability of the reals using decimal representations. This is Cantor’s second proof, which is probably better known. This proof may seem shorter, but it is because we already did the hard part above and we are left with a slick trick to prove that \(\R\) is uncountable. This trick is called Cantor diagonalization and finds use in other proofs as well.
Let \(X \coloneqq \{ x_1,x_2,x_3,\ldots \}\) be any countable subset of real numbers in \((0,1]\text{.}\) We will construct a real number not in \(X\text{.}\) Let
Let \(E_n\) be the \(n\)-digit truncation of \(y = 0.e_1e_2e_3\ldots\text{.}\) Because all the digits are nonzero, \(E_n < E_{n+1} \leq y\text{.}\) Therefore,
\begin{equation}
E_n < y \leq E_n + {10}^{-n}
\end{equation}
for all \(n\text{,}\) and the representation is the unique one for \(y\) from the proposition. For every \(n\text{,}\) the \(n\)th digit of \(y\) is different from the \(n\)th digit of \(x_n\text{,}\) so \(y \neq x_n\text{.}\) So \(y \notin X\text{,}\) and as \(X\) was an arbitrary countable subset, \((0,1]\) must be uncountable. See Figure 1.5 for an example.
Using decimal digits we can also find lots of numbers that are not rational. The following proposition is true for every rational number, but we give it only for \(x \in (0,1]\) for simplicity.
If \(x \in (0,1]\) is a rational number and \(x = 0.d_1d_2d_3\ldots\text{,}\) then the decimal digits eventually start repeating. That is, there are positive integers \(N\) and \(P\text{,}\) such that for all \(n \geq N\text{,}\)\(d_n = d_{n+P}\text{.}\)
Suppose \(x = \nicefrac{p}{q}\) for positive integers \(p\) and \(q\text{.}\) If \(x\) has a nonunique decimal representation, then both its representations eventually have repeating digits, either all \(0\)s or all \(9\)s, see Exercise 1.5.3. Therefore suppose that \(x\) has a unique representation. We also suppose that \(x \neq 1\) so \(p < q\text{.}\)
To compute the first digit, take \(10 p\) and divide by \(q\text{.}\) Let \(d_1\) be the quotient. The remainder \(r_1\) is some integer between \(0\) and \(q-1\text{.}\) That is, \(d_1\) is the largest integer such that \(d_1 q \leq 10p\) and then \(r_1 = 10p - d_1q\text{.}\) As \(p < q\text{,}\) we have \(d_1 < 10\text{,}\) so \(d_1\) is a digit. Furthermore,
The first inequality is strict since \(x\) has a unique representation. So \(d_1\) really is the first digit. What is left is \(\frac{r_1}{10q}\text{.}\) To compute \(d_2\text{,}\) divide \(10 r_1\) by \(q\) obtaining \(d_2\) and \(r_2\text{,}\) where \(r_2 = 10 r_1 - d_2 q\text{.}\) Solve for \(r_1\) and plug into \(\frac{p}{q} = \frac{d_1}{10} + \frac{r_1}{10 q}\) to arrive at \(\frac{p}{q} = \frac{d_1}{10} + \frac{d_2}{{10}^2} +
\frac{r_2}{{10}^2 q} = D_2 +
\frac{r_2}{{10}^2 q}\text{.}\) As \(r_2 < q\text{,}\) we again get \(d_2 < 10\text{.}\) To compute \(d_3\text{,}\) divide \(10 r_2\) by \(q\) getting \(d_3\) and \(r_3\text{.}\) And so on and so forth. After computing \(n-1\) digits, we have \(\frac{p}{q} = D_{n-1} + \frac{r_{n-1}}{10^{n-1} q}\text{.}\) To get the \(n\)th digit, divide \(10 r_{n-1}\) by \(q\) to get the quotient \(d_n\text{,}\) the remainder \(r_n\text{,}\) and the inequalities
The new digit depends only on the remainder from the previous step. There are at most \(q\) possible remainders. Hence, the process must start repeating itself after at most \(q\) steps, and so \(P\) is at most \(q\text{.}\)
\begin{equation}
x = 0.101001000100001000001\ldots
\end{equation}
is irrational. Specifically, the digits are a one, then a zero, then a one, then two zeros, then a one, then three zeros, and so on and so forth. That \(x\) is irrational follows from the proposition; the digits never start repeating. For every \(P\text{,}\) if we go far enough, we find a 1 followed by at least \(P\) zeros, and there are infinitely many such 1s. That is, there are infinitely many \(n\) (so arbitrarily large \(n\)) such that \(d_n=1\) and \(d_{n+P}=0\text{,}\) in other words, \(d_n \neq d_{n+P}\text{.}\)
Prove the converse of Proposition 1.5.3, that is, if the digits in the decimal representation of \(x\) are eventually repeating, then \(x\) must be rational.
Show that real numbers \(x \in (0,1)\) with nonunique decimal representation are exactly the rational numbers that can be written as \(\frac{m}{10^n}\) for some integers \(m\) and \(n\text{.}\) In this case show that there exist exactly two representations of \(x\text{.}\)
Let \(b \geq 2\) be an integer. Define a representation of a real number in \([0,1]\) in terms of base \(b\) rather than base 10 and prove Proposition 1.5.1 for base \(b\text{.}\)
Using the previous exercise with \(b=2\) (binary), show that the cardinality of \(\R\) is the same as the cardinality of \(\sP(\N)\text{,}\) obtaining yet another (though related) proof that \(\R\) is uncountable. Hint: Construct two injections, one from \([0,1]\) to \(\sP(\N)\) and one from \(\sP(\N)\) to \([0,1]\text{.}\) Hint 2: Given a set \(A \subset \N\text{,}\) the map that makes the \(n\)th binary digit of \(x\) be 1 if \(n\in A\) almost works, but is not one-to-one. Modify it.
(Challenging) Explicitly construct an injection from \([0,1] \times [0,1]\) to \([0,1]\) (think about why this is so surprising 1
With quite a bit more work (or by applying the Cantor–Bernstein–Schröder theorem) one can prove that there is a bijection. When he proved this result, Cantor apparently wrote “I see it but I don’t believe it.”
). Then describe the set of numbers in \([0,1]\) not in the image of your injection (unless, of course, you managed to construct a bijection). Hint: Consider even and odd digits of the decimal expansion.
Prove that if \(x = \nicefrac{p}{q} \in (0,1]\) is a rational number, \(q > 1\text{,}\) then the period \(P\) of repeating digits in the decimal representation of \(x\) is in fact less than or equal to \(q-1\text{.}\)
Prove that if \(b \in \N\) and \(b \geq 2\text{,}\) then for every \(\epsilon > 0\text{,}\) there is an \(n \in \N\) such that \(b^{-n} < \epsilon\text{.}\) Hint: One possibility is to first prove that \(b^n > n\) for all \(n \in \N\) by induction.
For a higher quality printout use the PDF versions: https://www.jirka.org/ra/realanal.pdf,https://www.jirka.org/ra/realanal2.pdf
or https://jirilebl.github.io/ra/realanal.pdf,https://jirilebl.github.io/ra/realanal2.pdf
