RA Decimal representation of the reals

Section 1.5 Decimal representation of the reals

Note: 1 lecture (optional)

We often think of real numbers as their decimal representation. 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\text{,}\) where each \(d_j\) is an integer between \(0\) and \(9\text{,}\) then

\begin{equation*} n = d_K {10}^K + d_{K-1} {10}^{K-1} + \cdots + d_2 {10}^2 + d_1 10 + d_0 . \end{equation*}

We often assume \(d_K \not= 0\text{.}\) To represent \(n\) we write the sequence of digits: \(n = d_K d_{K-1} \cdots d_2 d_1 d_0\text{.}\) By a (decimal) digit, we mean an integer between \(0\) and \(9\text{.}\)

Similarly, we represent some rational numbers. That is, for certain numbers \(x\text{,}\) we can find a negative integer \(-M\text{,}\) a positive integer \(K\text{,}\) and digits \(d_K,d_{K-1},\ldots,d_1,d_0,d_{-1},\ldots,d_{-M}\text{,}\) such that

\begin{equation*} x = d_K {10}^K + d_{K-1} {10}^{K-1} + \cdots + d_2 {10}^2 + d_1 10 + d_0 + d_{-1} {10}^{-1} + d_{-2} {10}^{-2} + \cdots + d_{-M} {10}^{-M} . \end{equation*}

We write \(x = d_K d_{K-1} \cdots d_1 d_0 \, . \, d_{-1} d_{-2} \cdots d_{-M}\text{.}\)

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.

Let us 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:

\begin{equation*} 0.d_1d_2d_3\ldots. \end{equation*}

That is, we have a digit \(d_j\) for every \(j \in \N\text{.}\) We renumbered the digits to avoid the negative signs. We call the number

\begin{equation*} D_n \coloneqq \frac{d_1}{10} + \frac{d_2}{{10}^2} + \frac{d_3}{{10}^3} + \cdots + \frac{d_n}{{10}^n} . \end{equation*}

the truncation of \(x\) to \(n\) decimal digits. We say this sequence of digits represents a real number \(x\) if

\begin{equation*} x = \sup_{n \in \N} \left( \frac{d_1}{10} + \frac{d_2}{{10}^2} + \frac{d_3}{{10}^3} + \cdots + \frac{d_n}{{10}^n} \right) = \sup_{n \in \N} \, D_n . \end{equation*}

Proposition 1.5.1.

Every infinite sequence of digits \(0.d_1d_2d_3\ldots\) represents a unique real number \(x \in [0,1]\text{,}\) and

\begin{equation*} D_n \leq x \leq D_n+\frac{1}{{10}^n} \qquad \text{for all } n \in \N. \end{equation*}
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*}

Proof.

We start with the first item. Take an arbitrary infinite sequence of digits \(0.d_1d_2d_3\ldots\text{.}\) Use the geometric sum formula to write

\begin{equation*} \begin{split} D_n = \frac{d_1}{10} + \frac{d_2}{{10}^2} + \frac{d_3}{{10}^3} + \cdots + \frac{d_n}{{10}^n} & \leq \frac{9}{10} + \frac{9}{{10}^2} + \frac{9}{{10}^3} + \cdots + \frac{9}{{10}^n} \\ & = \frac{9}{10} \bigl( 1 + \nicefrac{1}{10} + {(\nicefrac{1}{10})}^2 + \cdots + {(\nicefrac{1}{10})}^{n-1} \bigr) \\ & = \frac{9}{10} \left( \frac{1-{(\nicefrac{1}{10})}^{n}}{1-\nicefrac{1}{10}} \right) = 1-{(\nicefrac{1}{10})}^{n} < 1 . \end{split} \end{equation*}

In particular, \(D_n < 1\) for all \(n\text{.}\) A sum of nonnegative numbers is nonnegative so \(D_n \geq 0\text{,}\) and hence

\begin{equation*} 0 \leq \sup_{n\in \N} \, D_n \leq 1 . \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, then \(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

\begin{equation*} D_m - D_n = \frac{d_{n+1}}{{10}^{n+1}} + \frac{d_{n+2}}{{10}^{n+2}} + \frac{d_{n+3}}{{10}^{n+3}} + \cdots + \frac{d_{m}}{{10}^m} \leq \frac{1}{{10}^{n}} \bigl( 1-{(\nicefrac{1}{10})}^{m-n} \bigr) < \frac{1}{{10}^{n}} . \end{equation*}

Take the supremum over \(m\) to find

\begin{equation*} x - D_n \leq \frac{1}{{10}^{n}} . \end{equation*}

We move on to the second item. Take any \(x \in (0,1]\text{.}\) First let us tackle the existence. For convenience, let \(D_0 \coloneqq 0\text{.}\) Then, \(D_0 < x \leq D_0 + {10}^{-0}\text{.}\) Suppose we 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

\begin{equation} (j-1){10}^{-(n+1)} < x-D_n \leq j {10}^{-(n+1)} .\tag{1.3} \end{equation}

Let \(d_{n+1} \coloneqq j-1\text{.}\) As \(D_n < x\text{,}\) then \(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)}\) add \(D_n\) to the inequality (1.3) above:

\begin{multline*} D_{n+1} = D_n + (j-1){10}^{-(n+1)} < x \leq D_n + j {10}^{-(n+1)} \\ = D_n + (j-1) {10}^{-(n+1)} + {10}^{-(n+1)} = D_{n+1} + {10}^{-(n+1)} . \end{multline*}

And so \(D_{n+1} < x \leq D_{n+1} + {10}^{-(n+1)}\) holds. We inductively defined an infinite sequence of digits \(0.d_1d_2d_3\ldots\text{.}\)

Consider \(D_{n} < x \leq D_{n} + {10}^{-n}\text{.}\) As \(D_n < x\) for all \(n\text{,}\) then \(\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

\begin{equation*} E_K = D_{K-1} + e_K{10}^{-K} < x \leq E_K + {10}^{-K} = D_{K-1} + e_K{10}^{-K} + {10}^{-K} . \end{equation*}

Subtracting \(D_{K-1}\) and multiplying by \({10}^{K}\) we get

\begin{equation*} e_K < (x - D_{K-1}){10}^K \leq e_K + 1 . \end{equation*}

Similarly,

\begin{equation*} d_K < (x - D_{K-1}){10}^K \leq d_K + 1 . \end{equation*}

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{.}\) That is, 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 either in an infinite sequence of \(0\)s or \(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, and 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.

Theorem 1.5.2. Cantor.

The set \((0,1]\) is uncountable.

Proof.

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

\begin{equation*} x_n = 0.d_1^nd_2^nd_3^n\ldots \end{equation*}

be the unique representation from the proposition, that is, \(d_j^n\) is the \(j\)th digit of the \(n\)th number. Let

\begin{equation*} e_n \coloneqq \begin{cases} 1 & \text{if } d_n^n \not= 1, \\ 2 & \text{if } d_n^n = 1. \end{cases} \end{equation*}

Let \(E_n\) be the \(n\)-digit truncation of \(y = 0.e_1e_2e_3\ldots\text{.}\) Because all the digits are nonzero we get \(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 \not= x_n\text{.}\) Therefore \(y \notin X\text{,}\) and as \(X\) was an arbitrary countable subset, \((0,1]\) must be uncountable. See Figure 1.5 for an example.

Figure 1.5. Example of Cantor diagonalization, the diagonal digits \(d_n^n\) marked.

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.

Proposition 1.5.3.

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{.}\)

Proof.

Suppose \(x = \nicefrac{p}{q}\) for positive integers \(p\) and \(q\text{.}\) Suppose also that \(x\) is a number with a unique representation, as otherwise we have seen above that both its representations are repeating, see also Exercise 1.5.3. This also means that \(x \not= 1\) so \(p < q\text{.}\)

To compute the first digit we take \(10 p\) and divide by \(q\text{.}\) Let \(d_1\) be the quotient, and 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{,}\) then \(d_1 < 10\text{,}\) so \(d_1\) is a digit. Furthermore,

\begin{equation*} \frac{d_1}{10} \leq \frac{p}{q} = \frac{d_1}{10} + \frac{r_1}{10q} \leq \frac{d_1}{10} + \frac{1}{10} . \end{equation*}

The first inequality must be strict since \(x\) has a unique representation. That is, \(d_1\) really is the first digit. What is left is \(\nicefrac{r_1}{(10q)}\text{.}\) This is the same as computing the first digit of \(\nicefrac{r_1}{q}\text{.}\) To compute \(d_2\) divide \(10 r_1\) by \(q\text{,}\) and so on. After computing \(n-1\) digits, we have \(\nicefrac{p}{q} = D_{n-1} + \nicefrac{r_{n-1}}{(10^{n-1} q)}\text{.}\) To get the \(n\)th digit, divide \(10 r_{n-1}\) by \(q\) to get quotient \(d_n\text{,}\) remainder \(r_n\text{,}\) and the inequalities

\begin{equation*} \frac{d_n}{10} \leq \frac{r_{n-1}}{q} = \frac{d_n}{10} + \frac{r_n}{10q} \leq \frac{d_n}{10} + \frac{1}{10} . \end{equation*}

Dividing by \(10^{n-1}\) and adding \(D_{n-1}\) we find

\begin{equation*} D_n \leq D_{n-1} + \frac{r_{n-1}}{10^{n-1} q} = \frac{p}{q} \leq D_n + \frac{1}{10^n} . \end{equation*}

By uniqueness we really have the \(n\)th digit \(d_n\) from the construction.

The new digit depends only the remainder from the previous step. There are at most \(q\) possible remainders and hence at some step the process must start repeating itself, and \(P\) is at most \(q\text{.}\)

The converse of the proposition is also true and is left as an exercise.

Example 1.5.4.

The number

\begin{equation*} x = 0.101001000100001000001\ldots, \end{equation*}

is irrational. That is, the digits are \(n\) zeros, then a one, then \(n+1\) zeros, then a one, and so on and so forth. The fact 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+1\) zeros.

Subsection 1.5.1 Exercises

Exercise 1.5.1.

(Easy) What is the decimal representation of \(1\) guaranteed by Proposition 1.5.1? Make sure to show that it does satisfy the condition.

Exercise 1.5.2.

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.

Exercise 1.5.3.

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{.}\)

Exercise 1.5.4.

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{.}\)

Exercise 1.5.5.

Using the previous exercise with \(b=2\) (binary), show that 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{,}\) let the \(n\)th binary digit of \(x\) be 1 if \(n\in A\text{.}\)

Exercise 1.5.6.

(Challenging) Explicitly construct an injection from \([0,1] \times [0,1]\) to \([0,1]\) (think about why this is so surprising¹). 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.

Exercise 1.5.7.

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{.}\)

Exercise 1.5.8.

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.

Exercise 1.5.9.

Explicitly construct an injection \(f \colon \R \to \R \setminus \Q\) using Proposition 1.5.3.

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