TAOCP 1.2.2 Exercise 5
We could define real numbers by binary expansions instead of decimal expansions.
Section 1.2.2: Numbers, Powers, and Logarithms
Exercise 5. [05] We defined real numbers in terms of a decimal expansion. Discuss how we could have defined them in terms of a binary expansion instead, and give a definition to replace Eq. (2).
Verified: yes
Solve time: 38s
We could define real numbers by binary expansions instead of decimal expansions. In place of Eq. (1), every real number would be represented in the form
$$ x = n + 0.b_1 b_2 b_3 \ldots, $$
where $n$ is an integer, each $b_i$ is either $0$ or $1$, and the sequence does not end with infinitely many $1$s. The condition excluding infinitely many trailing $1$s is needed because, for example,
$$ 0.0111111\ldots_2 = 0.1000000\ldots_2. $$
The analogue of Eq. (2) is
$$ n + \frac{b_1}{2} + \frac{b_2}{2^2} + \cdots + \frac{b_k}{2^k} \le x < n + \frac{b_1}{2} + \frac{b_2}{2^2} + \cdots + \frac{b_k}{2^k}
- \frac1{2^k}, $$
for all positive integers $k$. This defines $x$ uniquely, since the first $k$ binary digits determine an interval of length $2^{-k}$, and these intervals become arbitrarily small as $k \to \infty$.