University Mathematics — Year 1 · Bachelor Year 1

10Real Numbers

All of analysis rests on one property that distinguishes $\R$ from $\Q$ : every nonempty set bounded from above has a least upper bound. This chapter states it precisely, derives its first consequences — the Archimedean property, the floor function, the density of the rationals and of the irrationals — and sets up the vocabulary (sup, inf, max, min) used constantly from Chapter 11 onward.

10.1 The upper bound property

Definition 10.1 (Bounds, sup and inf)

Let $A \subseteq \R$ be nonempty. A real $M$ is an upper bound of $A$ when $a \leq M$ for all $a \in A$ ; $A$ is bounded above when it has an upper bound (similarly below, with lower bounds; bounded means both). A maximum of $A$ is an upper bound belonging to $A$ .

The supremum $\sup A$ is the least upper bound of $A$ , when it exists; the infimum $\inf A$ is the greatest lower bound.

Theorem 10.2 (Completeness axiom of $\R$ )

$\R$ is an ordered field containing $\Q$ in which every nonempty subset bounded above has a supremum.

Proof. Admitted at this level. ∎

Remark 10.3

We take this as the defining axiom of $\R$ ; constructing a model (by Dedekind cuts or by Cauchy sequences of rationals) and proving its uniqueness is honest but long, and is left for further study. Note that $\Q$ fails the property: $\{x \in \Q : x^2 < 2\}$ is bounded above but has no least upper bound in $\Q$ — its candidate, $\sqrt 2$ , is missing (Example 1.11). By passing to opposites ( $\sup(-A) = -\inf A$ ), every nonempty set bounded below has an infimum.

Proposition 10.4 (The $\varepsilon$ -characterization)

Let $A \neq \emptyset$ be bounded above and $s \in \R$ . Then $s = \sup A$ if and only if

$s$ is an upper bound: $\forall a \in A$ , $a \leq s$ ; and
nothing smaller is: $\forall \varepsilon > 0$ , $\exists a \in A$ , $a > s - \varepsilon$ .

Proof. If $s = \sup A$ : (1) holds by definition, and for (2), $s - \varepsilon < s$ is not an upper bound, which is exactly the existence of $a > s - \varepsilon$ . Conversely, (1) says $s$ is an upper bound; (2) says no $t < s$ is an upper bound (take $\varepsilon = s - t$ ): $s$ is the least one. ∎

Example 10.5

$\sup \intoo{0}{1} = 1$ , not attained (no maximum); $\sup \intcc{0}{1} = 1 = \max$ . For $A = \{1 - \frac 1n : n \in \N^*\}$ : $\sup A = 1$ , not attained; $\inf A = \min A = 0$ . A maximum, when it exists, is the supremum; the whole point of $\sup$ is to have a substitute when the maximum does not exist.

The set A = \1 - 1n : n ∈ ℕ*\ on the number line: its points pile up toward 1 without reaching it. Every number ≥ 1 is an upper bound (the ray), and nothing smaller is, because an element of A enters each interval (1 - , 1): the two clauses of in one picture. The supremum is the left endpoint of the ray of upper bounds — and the completeness axiom is precisely the guarantee that this ray always has a left endpoint. — The set $A = \{1 - \frac1n : n \in \N^*\}$ on the number line: its points pile up toward $1$ without reaching it. Every number $\geq 1$ is an upper bound (the ray), and nothing smaller is, because an element of $A$ enters each interval $\intoo{1 - \varepsilon}{1}$ : the two clauses of Proposition 10.4 in one picture. The supremum is the left endpoint of the ray of upper bounds — and the completeness axiom is precisely the guarantee that this ray always has a left endpoint.

Example 10.6 (Computing suprema in practice)

Two full workouts of Proposition 10.4.

The set $A = \{x + \frac1x : x > 0\}$ . For every $x > 0$ , $x + \frac1x - 2 = \frac{(\,\sqrt x - 1/\sqrt x\,)^2}{1} \geq 0$ , so $2$ is a lower bound; and $2 = 1 + \frac11 \in A$ : therefore $\inf A = \min A = 2$ , attained at $x = 1$ . Above, $A$ is unbounded ( $x + \frac1x > x$ can exceed any $M$ by Theorem 10.10): $\sup A$ does not exist in $\R$ (it is $+\infty$ in $\overline\R$ ).

The set $B = \bigl\{\frac{m}{m + n} : m, n \in \N^*\bigr\}$ . Every element lies in $\intoo{0}{1}$ , so $0$ and $1$ are bounds. Neither is attained: $\frac{m}{m+n} = 1$ would force $n = 0$ . For the supremum, freeze $n = 1$ and let $m$ grow: $\frac{m}{m+1} = 1 - \frac{1}{m+1} > 1 - \varepsilon$ as soon as $m + 1 > \frac1\varepsilon$ (Archimedes): $\sup B = 1$ . Symmetrically ( $m = 1$ , $n$ large), $\inf B = 0$ . The closing insight: to pin a supremum, one well-chosen one-parameter path inside the set suffices — here the path $n = 1$ — and the $\varepsilon$ -characterization asks for nothing more.

Example 10.7 (The infimum mirror)

The infimum has its own $\varepsilon$ -characterization, obtained from Proposition 10.4 through $\inf A = -\sup(-A)$ : $i = \inf A$ iff $i$ bounds $A$ below and, for every $\varepsilon > 0$ , some $a \in A$ has $a < i + \varepsilon$ . A workout with both bounds at once: let

A = \Bigl\{(-1)^n + \frac1n : n \in \N^*\Bigr\} = \Bigl\{0,\ \tfrac32,\ -\tfrac23,\ \tfrac54,\ -\tfrac45,\ \dots\Bigr\} .

Even indices give $1 + \frac1n \leq \frac32$ , with equality at $n = 2$ : since also the odd-index values are $\leq 0 < \frac32$ , we get $\sup A = \max A = \frac32$ . Odd indices give $-1 + \frac1n > -1$ , decreasing toward $-1$ : every element of $A$ is $> -1$ , and $-1 + \varepsilon$ is beaten by $-1 + \frac1n$ for odd $n > \frac1\varepsilon$ : $\inf A = -1$ , not attained. One set, all four behaviors on display: a supremum that is a maximum, an infimum that is not a minimum.

Remark 10.8 (Common pitfalls with sup and inf)

Four errors account for most lost points. (i) Confusing $\sup$ and $\max$ : $\sup A$ need not belong to $A$ ; write $\max$ only after exhibiting an element of $A$ that is an upper bound. (ii) Passing strict inequalities to the supremum: if $a < b$ for all $a \in A$ , one may only conclude $\sup A \leq b$ — witness $A = \intoo{0}{1}$ , $b = 1$ . (iii) Writing $\sup A$ before checking legality: the symbol requires $A$ nonempty and bounded above (Method 10.18); $\sup \emptyset$ and $\sup \N$ are undefined in $\R$ (the conventions of $\overline\R$ are a separate, explicit act). (iv) Set operations: $\sup(A \cup B) = \max(\sup A, \sup B)$ always, but nothing general holds for $A \cap B$ — it may be empty, and even when it is not, $\sup(A \cap B)$ can be far below $\min(\sup A, \sup B)$ : take $A = \{0, 2\}$ and $B = \{0, 3\}$ , where $\sup(A \cap B) = 0$ .

Example 10.9 (Finite sets have maxima — a lemma used silently)

Every finite nonempty $F \subseteq \R$ has a maximum (and a minimum). Induction on the number of elements: a singleton $\{a\}$ has $\max = a$ ; if the claim holds for $n$ -element sets and $F$ has $n + 1$ elements, pick any $a \in F$ : the set $F \setminus \{a\}$ has a maximum $m$ , and $\max F$ is $m$ if $a \leq m$ , else $a$ . No completeness is involved — this is pure order plus induction, valid already in $\Q$ — yet the lemma deserves one honest statement because the coming proofs invoke it silently: the floor construction below (“a set of integers trapped in a finite range has a greatest element”), every $\max(\abs{u_0}, \dots, \abs{u_{N-1}}, \dots)$ bound in Chapter 11, every “take the largest of the finitely many $\delta$ s” in Chapter 13. Infinite sets are where maxima die and suprema take over: this chapter exists for the infinite case.

Theorem 10.10 (Archimedean property)

For every $x \in \R$ there is $n \in \N$ with $n > x$ . Equivalently: for all $\varepsilon > 0$ and $y > 0$ , some multiple $n\varepsilon$ exceeds $y$ .

Proof. Suppose not: some $x$ is an upper bound of $\N$ . Then $s = \sup \N$ exists (Theorem 10.2). By Proposition 10.4 (2) with $\varepsilon = 1$ , there is $n \in \N$ with $n > s - 1$ ; but then $n + 1 \in \N$ and $n + 1 > s$ , contradicting that $s$ is an upper bound. For the second form, let $\varepsilon > 0$ and $y > 0$ : the first form applied to $x = \frac{y}{\varepsilon}$ produces $n \in \N$ with $n > \frac{y}{\varepsilon}$ , and multiplying by $\varepsilon > 0$ (which preserves strict inequalities) gives $n\varepsilon > y$ . Conversely, the second form with $\varepsilon = 1$ and $y = x$ recovers the first for $x > 0$ , and $n = 1$ handles $x \leq 0$ : the two statements are strictly equivalent. ∎

Example 10.11 (Archimedes at work)

Three immediate uses, constantly needed later. (i) No positive real is below every $\frac1n$ : if $0 < \varepsilon$ , pick $n > \frac1\varepsilon$ ; then $\frac1n < \varepsilon$ . In other words, $\R$ contains no infinitesimals — the informal “ $\frac1n$ becomes arbitrarily small” is exactly this theorem. (ii) Explicit thresholds: how large must $n$ be for $\frac{1}{n^2} \leq 10^{-6}$ ? It suffices that $n \geq 10^3$ — Archimedes guarantees such $n$ exist, and the algebra locates them. (iii) Powers beat any bound: $2^n \geq n + 1$ (induction), so for every $M$ some power of $2$ exceeds $M$ : the geometric growth used for the dyadics in Exercise 10.8. The closing insight: the Archimedean property is the licence behind every phrase of the form “take $n$ large enough” — from now on we use that phrase freely, and this example is its one-time justification.

Theorem 10.12 (Floor function)

For every $x \in \R$ there is exactly one integer, the floor $\lfloor x \rfloor$ , with

\lfloor x \rfloor \leq x < \lfloor x \rfloor + 1 .

Proof. Existence. The set $E = \{k \in \Z : k \leq x\}$ is nonempty: by Theorem 10.10 there is $m \in \N$ with $m > -x$ , and then $-m < x$ , so $-m \in E$ . It is bounded above (by any integer $n > x$ , which exists for the same reason), so, being a set of integers trapped in the finite range $\intint{-m}{n}$ , it has a greatest element $k = \max E$ . Then $k \leq x$ , and $k + 1 \notin E$ means $x < k + 1$ .

Uniqueness. If $k$ and $k'$ both satisfy the inequalities, then $k \leq x < k' + 1$ gives $k \leq k'$ , and symmetrically $k' \leq k$ . ∎

Example 10.13 (Floors in practice)

$\lfloor 3.7 \rfloor = 3$ , $\lfloor 5 \rfloor = 5$ , and $\lfloor -3.7 \rfloor = -4$ : the floor goes down, not toward $0$ . Two consequences of uniqueness in Theorem 10.12 that we will use silently. First, for $n \in \Z$ ,

\lfloor x + n \rfloor = \lfloor x \rfloor + n ,

because $\lfloor x \rfloor + n$ is an integer satisfying the two defining inequalities for $x + n$ — and only one integer does. Second, $\lfloor \, \cdot \, \rfloor$ is nondecreasing: if $x \leq y$ then $\lfloor x \rfloor \leq x \leq y < \lfloor y \rfloor + 1$ , and an integer $< \lfloor y \rfloor + 1$ is $\leq \lfloor y \rfloor$ . Beware, however, that $\lfloor 2x \rfloor \neq 2\lfloor x \rfloor$ in general: $x = 0.6$ gives $\lfloor 1.2 \rfloor = 1 \neq 0 = 2\lfloor 0.6 \rfloor$ .

What is true is a worked identity worth keeping (Hermite’s, in its simplest case): for every real $x$ ,

\lfloor x \rfloor + \Bigl\lfloor x + \frac12 \Bigr\rfloor = \lfloor 2x \rfloor .

Write $x = \lfloor x\rfloor + u$ with $u \in \intco{0}{1}$ and separate two cases. If $u < \frac12$ : the left side is $\lfloor x\rfloor + \lfloor x\rfloor = 2\lfloor x\rfloor$ , and $2x = 2\lfloor x\rfloor + 2u$ with $2u \in \intco{0}{1}$ , so the right side is $2\lfloor x\rfloor$ too. If $u \geq \frac12$ : the left side is $\lfloor x\rfloor + (\lfloor x\rfloor + 1)$ , and $2u \in \intco{1}{2}$ makes the right side $2\lfloor x\rfloor + 1$ . The closing insight: $\lfloor x + \frac12\rfloor$ is the rounding of $x$ to the nearest integer, so the identity says that floor plus rounding equals floor of the double — and the case split on the fractional part $u$ is the standard technique behind every floor identity (Exercises 10.2 and 10.3 run on it too).

Theorem 10.14 (Density of $\Q$ and of $\R \setminus \Q$ )

Between any two reals $x < y$ there lie a rational and an irrational.

Proof. A rational. By Theorem 10.10, pick $n \in \N^*$ with $n > \frac{1}{y - x}$ , so $ny - nx > 1$ . Let $m = \lfloor nx \rfloor + 1$ . On one side, $nx < \lfloor nx \rfloor + 1 = m$ (Theorem 10.12); on the other, $m = \lfloor nx \rfloor + 1 \leq nx + 1 < ny$ . Dividing by $n$ : $x < \frac mn < y$ .

An irrational. Apply the previous point to the pair $x - \sqrt 2 < y - \sqrt 2$ : some rational $q$ lies between them, and then $q + \sqrt 2 \in \intoo{x}{y}$ is irrational (if $q + \sqrt 2$ were rational, so would be $\sqrt 2$ ). ∎

Example 10.15 (Running the proof of density)

The proof is an algorithm; let us execute it on $x = 1.414$ and $y = \sqrt 2$ . Since $1.4142^2 = 1.99996164 < 2$ , we have $\sqrt 2 > 1.4142$ , so $y - x > 0.0002$ and $\frac{1}{y - x} < 5000$ : the choice $n = 5000$ is legitimate. Then $nx = 7070$ , so $m = \lfloor 7070 \rfloor + 1 = 7071$ , and the rational produced is

\frac{m}{n} = \frac{7071}{5000} = 1.4142, \qquad 1.414 < 1.4142 < \sqrt 2 .

The closing insight: the proof needs $n$ only slightly larger than $\frac{1}{y-x}$ , and returns the first multiple of $\frac 1n$ beyond $x$ . Density is not an abstract miracle — it is long division in disguise, a theme developed at length in the weekend problem (Problem 10.1).

Remark 10.16 (Where completeness is used next)

Theorem 10.2 is the single non-algebraic axiom of this book, and every existence theorem of analysis is that axiom wearing different clothes: the monotone convergence theorem (Chapter 11), the Bolzano–Weierstrass theorem (Chapter 12), the intermediate value and extreme value theorems (Chapter 13), and the very definition of the integral as a supremum of lower sums (Chapter 15). The Year 3 volume builds measure theory and Hilbert spaces on the same single axiom. When a proof in the coming chapters produces a real number out of thin air, look for the hidden supremum.

Remark 10.17 (Between discreteness and density)

$\Z$ and $\Q$ sit at opposite extremes inside $\R$ : around each integer there is a gap of length $1$ containing no other (discreteness — this is what makes the floor well defined), while between any two reals there are infinitely many rationals (density). Remarkably, for additive subgroups of $\R$ there is nothing in between: Exercise 10.9 proves that such a subgroup is either of the form $\alpha\Z$ (discrete) or dense — a dichotomy that powers the density of $\{\sin n\}$ in Chapter 11 and the constructive monster of Problem 13.1. General sets, of course, mix the behaviors freely: $\Z \cup \Q\cap\intcc{0}{1}$ is discrete far away and dense in the middle.

Method 10.18 (Proving equalities with sup and inf)

To prove $\sup A = s$ : check that $s$ bounds $A$ above, then produce, for each $\varepsilon > 0$ (or for a sequence $\varepsilon = \frac 1n$ ), an element of $A$ above $s - \varepsilon$ . To compare suprema, use: $A \subseteq B \implies \sup A \leq \sup B$ ; and for all $a, b$ : $\sup(A + B) = \sup A + \sup B$ , where $A + B = \{a + b\}$ (Exercise 10.5). Never write $\sup A$ before knowing $A$ is nonempty and bounded above.

10.2 Intervals

Proposition 10.19 (Characterization of intervals)

A subset $I \subseteq \R$ is an interval (one of the familiar types $\intoo{a}{b}$ , $\intcc{a}{b}$ , $\intco{a}{b}$ , $\intoc{a}{b}$ , half-lines, $\R$ , $\emptyset$ , singletons) if and only if it is convex:

\forall x, y \in I,\ \forall z \in \R, \quad x \leq z \leq y \implies z \in I .

Proof. Every listed type is clearly convex. Conversely, let $I$ be convex and nonempty. Set $a = \inf I$ if $I$ is bounded below, else $a = -\infty$ ; likewise $b = \sup I$ or $+\infty$ . We claim $\intoo{a}{b} \subseteq I \subseteq \intcc{a}{b}$ (with obvious conventions at $\pm\infty$ ). The second inclusion is the definition of bounds. For the first, let $z \in \intoo{a}{b}$ : since $z > a$ , $z$ is not a lower bound (or $a = -\infty$ ), so some $x \in I$ has $x < z$ ; similarly some $y \in I$ has $y > z$ ; convexity puts $z \in I$ .

It remains to read off the type from the double inclusion $\intoo{a}{b} \subseteq I \subseteq \intcc{a}{b}$ : the sets squeezed between an open interval and its closure differ from $\intoo{a}{b}$ only by the presence or absence of the (finite) endpoints. Explicitly: if $a, b \in \R$ , the four possibilities for $(a \in I,\ b \in I)$ give $\intoo{a}{b}$ , $\intco{a}{b}$ , $\intoc{a}{b}$ , $\intcc{a}{b}$ (including the degenerate cases $a = b$ : singleton if $a \in I$ ); if $a = -\infty$ and $b \in \R$ , one gets $\intoo{-\infty}{b}$ or $\intoc{-\infty}{b}$ ; symmetrically for $a \in \R$ , $b = +\infty$ ; and $a = -\infty$ , $b = +\infty$ gives $I = \R$ . Every case is on the list: done. ∎

Remark 10.20 (Why convexity is the right test)

The proposition converts a geometric definition (a list of ten shapes) into a one-line logical test, and the test is what one actually uses: to prove that a set is an interval, never chase which of the ten shapes it is — verify convexity and let the proposition sort out the type. The intermediate value theorem of Chapter 13 will be stated exactly this way (“the continuous image of an interval is an interval”), and its proof produces the convexity, not the shape.

Remark 10.21 (Extended real line)

It is convenient to adjoin two symbols and work in $\overline\R = \R \cup \{-\infty, +\infty\}$ , with the conventions $\sup A = +\infty$ when $A$ is not bounded above and $\sup \emptyset = -\infty$ . Then every subset of $\R$ has a supremum in $\overline\R$ — a notational comfort used freely for limits in Chapter 11.

Example 10.22 (Computing in $\overline\R$ )

With the conventions in force: $\sup \Z = +\infty$ , $\inf \Z = -\infty$ ; for $A = \{n + (-1)^n n : n \in \N\} = \{0, 4, 0, 8, \dots\} \cup \{0\}$ , $\sup A = +\infty$ (the even terms $2n$ are unbounded) and $\inf A = \min A = 0$ ; and $\sup\emptyset = -\infty \leq \inf\emptyset = +\infty$ — the one set whose supremum is smaller than its infimum, a reminder that the conventions are chosen to make $\sup$ increasing and $\inf$ decreasing with respect to inclusion:

A \subseteq B \implies \sup A \leq \sup B \quad\text{and}\quad \inf A \geq \inf B ,

now valid with no nonemptiness caveat. What the conventions do not provide is arithmetic: $+\infty + (-\infty)$ and $0 \times (+\infty)$ stay undefined, and every algebraic manipulation of suprema must first check it never forms these. The extended line is bookkeeping, not a number system.

Example 10.23 (The supremum that escaped $\Q$ )

Return to the set of the opening remark, $A = \{x \in \Q : x^2 < 2\}$ , and compute its supremum in $\R$ . It is nonempty ( $1 \in A$ ) and bounded above by $1.5$ (if $x > 1.5$ then $x^2 > 2.25 > 2$ ), so $s = \sup A$ exists. We claim $s = \sqrt 2$ (the real number built in Exercise 10.12). Upper bound: every $a \in A$ satisfies $a < \sqrt2$ — for $a \leq 0$ this is clear, and for $a > 0$ , $a \geq \sqrt2$ would give $a^2 \geq 2$ . Nothing smaller works: given $t < \sqrt2$ , density (Theorem 10.14) provides a rational $q$ with $\max(1, t) < q < \sqrt 2$ , and then $q^2 < 2$ , so $q \in A$ exceeds $t$ . By Proposition 10.4, $s = \sqrt2 \notin \Q$ . The closing insight: the supremum of a set of rationals need not be rational — completeness is precisely the promise that $\R$ , unlike $\Q$ , never lets a supremum escape; this example is the opening remark of the chapter, now proved rather than pointed at.

Remark 10.24 (Perspectives inside this volume)

The chapter’s three tools have distinct careers ahead. The supremum runs the analysis half: monotone limits (Chapter 11), the integral’s very definition (Chapter 15), and, in the geometry of Chapter 23, the distance from a point to a subspace — an infimum that orthogonal projection turns into a minimum. The floor function returns wherever the discrete meets the continuous: digit expansions (this chapter’s weekend problem), Dirichlet’s pigeonhole approximation (Problem 14.1), integral comparisons of sums (Chapter 17). Density arguments upgrade into a method in Chapter 13: an identity of continuous functions needs checking only on $\Q$ — half of Cauchy’s functional equation (Problem 13.1) is exactly that move. When in doubt about where a proof in this volume gets its existence statements, the answer is nearly always: this chapter.

10.3 Exercises

Exercise 10.1 ★

Determine (with proofs) sup, inf, max, min — when they exist — of:

A = \Bigl\{\frac{1}{n} : n \in \N^*\Bigr\}, \qquad B = \Bigl\{\frac{(-1)^n n}{n+1} : n \in \N\Bigr\}, \qquad C = \{x \in \R : x^2 < 3\}.

Solution

Solution of Exercise 10.1.

$A$ : every element is $\leq 1$ and $1 \in A$ : $\sup A = \max A = 1$ . Lower bounds: $0$ bounds below; for $\varepsilon > 0$ , Archimedes provides $n$ with $\frac 1n < \varepsilon$ , so no positive number bounds $A$ below: $\inf A = 0$ , not attained (no min).

$B$ : terms $0, -\frac12, \frac23, -\frac34, \frac45, \dots$ The even terms $\frac{n}{n+1}$ ( $n$ even) increase to $1$ without reaching it; the odd terms $-\frac{n}{n+1}$ decrease to $-1$ . So $\sup B = 1$ and $\inf B = -1$ , neither attained: no max, no min. (Bounds: $\abs{b} < 1$ for all $b \in B$ ; and $\frac{n}{n+1} = 1 - \frac{1}{n+1} > 1 - \varepsilon$ for $n$ large, similarly below.)

$C = \intoo{-\sqrt 3}{\sqrt 3}$ : $\sup C = \sqrt 3$ , $\inf C = -\sqrt 3$ , neither attained.

Exercise 10.2 ★

Prove that for all $x, y \in \R$ : $\lfloor x \rfloor + \lfloor y \rfloor \leq \lfloor x + y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1$ , and that both bounds are attained.

Solution

Solution of Exercise 10.2.

Write $x = \lfloor x \rfloor + u$ , $y = \lfloor y \rfloor + v$ with $u, v \in \intco{0}{1}$ . Then $x + y = \lfloor x \rfloor + \lfloor y \rfloor + (u + v)$ with $u + v \in \intco{0}{2}$ . If $u + v < 1$ , $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y \rfloor$ ; if $1 \leq u + v < 2$ , $\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1$ . Both cases occur: $(x, y) = (0.2,\, 0.3)$ gives the left equality, $(0.7,\, 0.8)$ the right one.

Exercise 10.3 ★

Prove that for every $x \in \R$ and $n \in \N^*$ : $\Bigl\lfloor \frac{\lfloor nx \rfloor}{n} \Bigr\rfloor = \lfloor x \rfloor$ .

Solution

Solution of Exercise 10.3.

Let $k = \lfloor x \rfloor$ , so $k \leq x < k + 1$ . Multiplying by $n$ : $nk \leq nx < nk + n$ , and taking floors (an increasing operation on integers’ side): $nk \leq \lfloor nx \rfloor \leq nk + n - 1$ . Dividing by $n$ : $k \leq \frac{\lfloor nx \rfloor}{n} < k + 1$ , so the outer floor is $k$ .

Exercise 10.4 ★

Let $A \subseteq B$ be nonempty subsets of $\R$ , $B$ bounded. Prove $\inf B \leq \inf A \leq \sup A \leq \sup B$ .

Solution

Solution of Exercise 10.4.

Every element of $A$ is in $B$ , so $\sup B$ bounds $A$ above: therefore $\sup A \leq \sup B$ ( $\sup A$ is the least upper bound). Symmetrically $\inf B \leq \inf A$ . Finally $\inf A \leq \sup A$ because $A$ is nonempty: any $a \in A$ sits between them.

Exercise 10.5 ★★

For nonempty bounded $A, B \subseteq \R$ , define $A + B = \{a + b : a \in A,\ b \in B\}$ and $-A = \{-a : a \in A\}$ . Prove:

\sup(A + B) = \sup A + \sup B, \qquad \sup(-A) = -\inf A .

Solution

Solution of Exercise 10.5.

Let $s = \sup A$ , $t = \sup B$ . Every $a + b \leq s + t$ : upper bound. For $\varepsilon > 0$ , choose $a > s - \frac\varepsilon2$ and $b > t - \frac\varepsilon2$ (Proposition 10.4): then $a + b > s + t - \varepsilon$ . By the $\varepsilon$ -characterization, $\sup(A+B) = s + t$ .

For $-A$ : $m$ bounds $-A$ above $\iff$ $-m$ bounds $A$ below; the least upper bound of $-A$ therefore corresponds to the greatest lower bound of $A$ : $\sup(-A) = -\inf A$ .

Exercise 10.6 ★★

Let $f, g \colon E \to \R$ be bounded functions. Prove

\sup_{x \in E}\, \bigl(f(x) + g(x)\bigr) \leq \sup_{x \in E} f(x) + \sup_{x \in E} g(x),

and give an example where the inequality is strict. Why does this not contradict Exercise 10.5?

Solution

Solution of Exercise 10.6.

For every $x$ : $f(x) + g(x) \leq \sup f + \sup g$ ; taking the sup of the left side gives the inequality. Strict example: $E = \{0, 1\}$ , $f = \mathbf{1}_{\{0\}}$ (value $1$ at $0$ , else $0$ ), $g = \mathbf{1}_{\{1\}}$ : $\sup(f + g) = 1 < 2 = \sup f + \sup g$ .

No contradiction with Exercise 10.5: there, $a \in A$ and $b \in B$ vary independently; here the same $x$ feeds both $f$ and $g$ — the set $\{f(x) + g(x) : x \in E\}$ is smaller than the set $\{f(x) + g(y) : x, y \in E\}$ .

Exercise 10.7 ★★

Prove that $\sqrt 2 + \sqrt 3$ is irrational. (Square it and use the irrationality of $\sqrt 6$ , to be proved via Exercise 6.7.)

Solution

Solution of Exercise 10.7.

$\sqrt 6$ is irrational: $6 = 2 \times 3$ is not a perfect square, and $v_2(6q^2) = 1 + 2v_2(q)$ odd prevents $6q^2 = r^2$ (as in Exercise 6.7). Now suppose $x = \sqrt 2 + \sqrt 3 \in \Q$ . Then $x^2 = 5 + 2\sqrt 6 \in \Q$ , so $\sqrt 6 = \frac{x^2 - 5}{2} \in \Q$ : contradiction. Hence $\sqrt 2 + \sqrt 3 \notin \Q$ .

Exercise 10.8 ★★

Prove that the set $D = \bigl\{\frac{m}{2^n} : m \in \Z,\ n \in \N\bigr\}$ of dyadic rationals is dense in $\R$ : between any two reals lies a dyadic rational.

Solution

Solution of Exercise 10.8.

Let $x < y$ . Pick $n \in \N$ with $2^n > \frac{1}{y - x}$ (Archimedes: $2^n \geq n + 1$ by an easy induction, so some power of $2$ exceeds any real). Then, as in the proof of Theorem 10.14 with $2^n$ in place of $n$ : $m = \lfloor 2^n x \rfloor + 1$ satisfies $x < \frac{m}{2^n} < y$ . So $D$ is dense.

Exercise 10.9 ★★★

Let $G$ be a subgroup of $(\R, +)$ with $G \neq \{0\}$ . Set $\alpha = \inf\,(G \cap \intoo{0}{+\infty})$ . Prove:

if $\alpha > 0$ , then $G = \alpha\Z$ ;
if $\alpha = 0$ , then $G$ is dense in $\R$ .

Deduce that $\Z + \sqrt 2\,\Z$ is dense in $\R$ .

Solution

Solution of Exercise 10.9.

Suppose $\alpha > 0$ . First, $\alpha \in G$ . Suppose not: by the $\varepsilon$ -characterization of the infimum with $\varepsilon = \alpha$ , there is $g \in G$ with $\alpha < g < 2\alpha$ (strict on the left since $\alpha \notin G$ ); then, with $\varepsilon = g - \alpha$ , there is $h \in G$ with $\alpha < h < g$ . Now $g - h \in G$ and $0 < g - h < g - \alpha < \alpha$ : an element of $G \cap \intoo{0}{+\infty}$ below its infimum, absurd. So $\alpha \in G$ , and $\alpha\Z \subseteq G$ ( $G$ is a group). Conversely, for $x \in G$ , let $k = \lfloor x/\alpha \rfloor$ : then $x - k\alpha \in G$ and $0 \leq x - k\alpha < \alpha$ , and the definition of $\alpha$ forces $x - k\alpha = 0$ . Hence $G = \alpha\Z$ .
Suppose $\alpha = 0$ , and let $x < y$ . There is $g \in G$ with $0 < g < y - x$ . The multiple $kg$ with $k = \lfloor x/g \rfloor + 1$ satisfies $x < kg \leq x + g < y$ , and $kg \in G$ : density.

$G = \Z + \sqrt 2\,\Z$ is a subgroup of $(\R, +)$ . It is not of the form $\alpha\Z$ : otherwise $1 = p\alpha$ and $\sqrt 2 = q\alpha$ ( $p, q \in \Z$ ) would give $\sqrt 2 = \frac qp \in \Q$ , contradiction. By the dichotomy, $G$ is dense in $\R$ .

Exercise 10.10 ★★★

For $A, B$ nonempty sets of positive reals, let $AB = \{ab : a \in A, b \in B\}$ . Prove $\sup(AB) = \sup A \cdot \sup B$ (bounded case), and show by example that positivity is essential.

Solution

Solution of Exercise 10.10.

Let $s = \sup A > 0$ , $t = \sup B > 0$ . For $a \in A$ , $b \in B$ : $ab \leq st$ (multiplying inequalities between positive numbers). For $0 < \varepsilon < \min(s, t)$ : choose $a > s - \varepsilon$ and $b > t - \varepsilon$ ; then

ab > (s - \varepsilon)(t - \varepsilon) = st - \varepsilon(s + t) + \varepsilon^2 > st - \varepsilon (s + t),

and $\varepsilon(s+t)$ can be made arbitrarily small: by the $\varepsilon$ -characterization (in the form: no number $< st$ bounds $AB$ above), $\sup AB = st$ .

Positivity is essential: $A = B = \{-1, 0\}$ gives $AB = \{0, 1\}$ , $\sup AB = 1$ , while $\sup A \cdot \sup B = 0 \times 0 = 0$ .

Exercise 10.11 ★★

For a nonempty bounded $A \subseteq \R$ , define the diameter

\operatorname{diam} A = \sup\,\{\abs{a - a'} : a, a' \in A\} .

Prove that $\operatorname{diam} A = \sup A - \inf A$ , and that $\intcc{\inf A}{\sup A}$ is the smallest closed interval containing $A$ .

Solution

Solution of Exercise 10.11.

Write $s = \sup A$ , $i = \inf A$ . For $a, a' \in A$ : $a \leq s$ and $a' \geq i$ give $a - a' \leq s - i$ ; by symmetry $\abs{a - a'} \leq s - i$ , so $s - i$ bounds the set of gaps above. For $\varepsilon > 0$ , choose $a > s - \frac\varepsilon2$ and $a' < i + \frac\varepsilon2$ (Proposition 10.4 and its mirror for the infimum): then $\abs{a - a'} \geq a - a' > s - i - \varepsilon$ . By the $\varepsilon$ -characterization, $\operatorname{diam} A = s - i$ .

Every $a \in A$ satisfies $i \leq a \leq s$ , so $A \subseteq \intcc{i}{s}$ , a closed interval of length $\operatorname{diam} A$ . If a closed interval $\intcc{u}{v}$ contains $A$ , then $v$ is an upper bound and $u$ a lower bound of $A$ , so $u \leq i$ and $v \geq s$ : $\intcc{i}{s} \subseteq \intcc{u}{v}$ . Hence $\intcc{i}{s}$ is the smallest one.

Exercise 10.12 ★★★

Let $y > 0$ and $E = \{x \geq 0 : x^2 \leq y\}$ . Prove that $E$ is nonempty and bounded above, and that $s = \sup E$ satisfies $s^2 = y$ (rule out $s^2 < y$ and $s^2 > y$ by exhibiting, in each case, a small $h > 0$ contradicting the definition of the supremum). Deduce that every $y > 0$ has a unique square root $\sqrt y > 0$ and that $y \mapsto \sqrt y$ is increasing on $\intoo{0}{+\infty}$ .

Solution

Solution of Exercise 10.12.

$0 \in E$ , so $E \neq \emptyset$ . If $x > \max(1, y)$ then $x^2 > x > y$ , so $E$ is bounded above by $\max(1, y)$ : $s = \sup E$ exists (Theorem 10.2), and $s \geq \min(1, y) > 0$ because $\min(1, y) \in E$ : indeed if $y \geq 1$ then $1^2 = 1 \leq y$ , and if $y < 1$ then $y^2 < y$ .

$s^2 < y$ is impossible. Choose $0 < h < 1$ with $h < \frac{y - s^2}{2s + 1}$ . Then

(s + h)^2 = s^2 + 2sh + h^2 \leq s^2 + (2s + 1)h < y ,

so $s + h \in E$ , contradicting that $s$ bounds $E$ above.

$s^2 > y$ is impossible. Choose $0 < h < s$ with $h < \frac{s^2 - y}{2s}$ . Then $(s - h)^2 = s^2 - 2sh + h^2 > s^2 - 2sh > y$ ; every $x \in E$ satisfies $x^2 \leq y < (s - h)^2$ , hence $x < s - h$ (both are $\geq 0$ ): $s - h$ is an upper bound of $E$ smaller than $s$ , contradicting leastness.

Therefore $s^2 = y$ . Uniqueness: if $0 < s < s'$ then $s^2 < s'^2$ , so two distinct positive roots cannot both square to $y$ . Monotonicity: if $0 < y < y'$ , then $\sqrt y \neq \sqrt{y'}$ , and $\sqrt y > \sqrt{y'}$ would give $y > y'$ by squaring: so $\sqrt y < \sqrt{y'}$ .

10.4 Problem: Digit expansions and the rhythm of the rationals

Problem 10.1

Weekend problem — $b$ -adic expansions: existence, uniqueness, and periodicity characterizes $\Q$

Every real in $\intco{0}{1}$ has a digit expansion in every base $b \geq 2$ ; the expansion is unique once trailing strings of the digit $b - 1$ are outlawed; and it is eventually periodic exactly when the number is rational. This problem proves all three facts from the completeness axiom alone — no sequences, no series: only the supremum, the Archimedean property and the floor function — and closes with Cantor’s diagonal argument in digit form. Throughout, $b \geq 2$ is a fixed integer (the base), a digit is an element of $\intint{0}{b-1}$ , and a digit string $(d_n)_{n \geq 1}$ is proper when it is not eventually equal to $b - 1$ (that is: for every $N$ there is $n > N$ with $d_n \leq b - 2$ ).

Part I — Digits by hand. Long division of $p$ by $q$ in base $b$ : multiply the current remainder by $b$ , divide by $q$ , record the quotient as the next digit, keep the remainder.

In base $10$ , run the algorithm on $\frac 18$ and on $\frac 17$ , recording at each step the digit and the remainder. Check that the remainders for $\frac 17$ cycle through $1, 3, 2, 6, 4, 5$ and that the digits $142857$ then repeat forever.
Compute the base- $2$ expansions of $\frac 13$ and of $\frac{5}{16}$ , and the base- $3$ expansion of $\frac 12$ . Observe: one number terminates, the two others repeat — and $\frac 12$ , so tame in base $10$ , repeats forever in base $3$ .
For $x = \frac pq \in \intco{0}{1}$ in lowest terms, show that the digits produced by the algorithm are eventually all $0$ if and only if the remainder $b^N p \bmod q$ vanishes for some $N$ , if and only if $q$ divides some power $b^N$ , if and only if every prime factor of $q$ divides $b$ . Check: $\frac{1}{20}$ terminates in base $10$ , not in base $3$ .
Define the truncation $s_n = \lfloor b^n x \rfloor / b^n$ . For $x = \sqrt 2$ and $b = 10$ , compute $s_0, \dots, s_4$ by verifying at each step that two consecutive squares straddle $2$ (for instance $1.4142^2 = 1.99996164 < 2 < 2.00024449 = 1.4143^2$ ), and check $s_n \leq \sqrt 2 < s_n + 10^{-n}$ each time.

Part II — Existence, from the supremum. Fix $x \in \intco{0}{1}$ and set $A_n = \lfloor b^n x \rfloor$ and $d_n = A_n - b\,A_{n-1}$ for $n \geq 1$ .

Show $A_0 = 0$ and $b\,A_{n-1} \leq A_n \leq b\,A_{n-1} + b - 1$ ; conclude that each $d_n$ is a digit.
Show that $s_n := A_n b^{-n}$ satisfies

$s_n = \sum_{k=1}^{n} d_k\,b^{-k} \qquad\text{and}\qquad s_n \leq x < s_n + b^{-n} .$
Prove $b^n \geq n + 1$ by induction, then show that $(s_n)$ is nondecreasing and that $x = \sup_n s_n$ (use Proposition 10.4 and Theorem 10.10).
Show that the string $(d_n)$ is proper: if $d_k = b - 1$ for all $k > N$ , compute $s_n$ for $n > N$ by a finite geometric sum and contradict question 6.
Conversely, let $(e_n)_{n \geq 1}$ be any proper digit string and $t_n = \sum_{k=1}^n e_k b^{-k}$ . Show that $y = \sup_n t_n$ exists, lies in $\intco{0}{1}$ , and satisfies $t_n \leq y < t_n + b^{-n}$ for every $n$ (for the strict inequality, use a digit $e_m \leq b - 2$ with $m > n$ ). Deduce $\lfloor b^n y \rfloor = b^n t_n$ , then that the digits of $y$ , in the sense of question 5, are exactly the $e_n$ .

Part III — Uniqueness, order, shift.

Assemble questions 5–9 into the $b$ -adic expansion theorem: the maps $x \mapsto (d_n)$ and $(e_n) \mapsto \sup_n t_n$ are mutually inverse bijections between $\intco{0}{1}$ and the set of proper digit strings. In particular no two distinct proper strings have the same value.
Now allow improper strings. Show that a string with $e_n = b - 1$ for all $n > M$ (with $M \geq 0$ minimal) has value $t_M + b^{-M}$ ; conclude that $0.999\dots = 1$ in base $10$ , and that the reals with two digit representations are exactly the $b$ -adic fractions $m/b^N \in \intoo{0}{1}$ — every other real has just one, even among improper strings.
Prove that the bijection of question 10 is order-preserving for the lexicographic order: if the proper strings of $x$ and $y$ first differ at index $m$ , then $x < y$ if and only if $d_m < e_m$ .
(Shift lemma) Let $x \in \intco{0}{1}$ have digits $(d_n)$ . Show that the fractional part of $bx$ has digits $(d_{n+1})_{n \geq 1}$ (compute $\lfloor b^n(bx - A_1)\rfloor$ using $\lfloor u - K \rfloor = \lfloor u \rfloor - K$ for integer $K$ ), and deduce by induction that the fractional part of $b^m x$ has digits $(d_{n+m})_{n \geq 1}$ .

Part IV — Rationality is periodicity. Let $x = \frac pq \in \intco{0}{1}$ be in lowest terms and $r_n = b^n p \bmod q$ the remainder of the Euclidean division of $b^n p$ by $q$ .

Show $A_n = \dfrac{b^n p - r_n}{q}$ and $r_n = (b\,r_{n-1}) \bmod q$ .
Show $d_n = \Bigl\lfloor \dfrac{b\,r_{n-1}}{q} \Bigr\rfloor$ : each digit is a function of the previous remainder alone. This is exactly the long division of Part I.
Apply the pigeonhole principle (Corollary 2.3) to $r_0, \dots, r_q$ and conclude: the expansion of every rational is eventually periodic, with preperiod and period at most $q$ .
Conversely, suppose the digits of $y \in \intco{0}{1}$ are purely periodic: $d_{n+T} = d_n$ for all $n \geq 1$ . Using the shift lemma and the uniqueness of question 10, show that the fractional part of $b^T y$ equals $y$ , and deduce $(b^T - 1)\,y \in \N$ : thus $y$ is rational with denominator dividing $b^T - 1$ . Verify the mechanism on $0.(142857)$ : $142857 \times 7 = 999999$ .
Treat the eventually periodic case by shifting, and state the periodicity criterion: $x \in \intco{0}{1}$ is rational if and only if its proper $b$ -adic expansion is eventually periodic — in one base if and only if in all.
For $x = \frac 1q$ with $\gcd(q, b) = 1$ , show that the expansion is purely periodic and that its least period is the least $T \geq 1$ with $b^T \equiv 1 \pmod q$ (the multiplicative order of $b$ modulo $q$ ). Check that for $q = 7$ , $b = 10$ the powers of $10$ modulo $7$ run through $3, 2, 6, 4, 5, 1$ : order $6$ , matching question 1.

Part V — Dividends and the diagonal.

Let $x^*$ be the real of $\intco{0}{1}$ whose base- $10$ digits are $1$ at the triangular positions $\frac{j(j + 1)}{2}$ ( $j \geq 1$ ) and $0$ elsewhere: $x^* = 0.101001000100001\dots$ Show that its digit string is proper but not eventually periodic (a period $T$ would force ones at gaps at most $T$ , but the gaps grow), and conclude that $x^*$ is irrational: a number proved irrational by pure rhythm.
Show that for every base $b$ the set $\{m/b^n : m \in \Z, n \in \N\}$ is dense in $\R$ (generalizing Exercise 10.8), and that every rational $\frac pq \in \intoo{0}{1}$ has a terminating expansion in base $q$ . Moral: terminating is a property of the pair (number, base); periodicity — rationality — is intrinsic.
(Cantor’s diagonal) Let $k \mapsto x_k$ be any map from $\N^*$ to $\intco{0}{1}$ . Define the digit string $e_k = 1$ if the $k$ -th digit of $x_k$ differs from $1$ , and $e_k = 2$ otherwise. Show that $(e_k)$ is proper, that its value $y$ lies in $\intco{0}{1}$ , and that $y \neq x_k$ for every $k$ . Conclude: no map $\N^* \to \intco{0}{1}$ is surjective. (The vocabulary of countability, and this theorem’s proper home, is Chapter 12.)
Show that if the proper expansions of $x$ and $y$ agree up to index $n$ then $\abs{x - y} < b^{-n}$ , and disprove the converse with $x = 0.1$ , $y = 0.0999$ in base $10$ : closeness of numbers does not force agreement of digits. Which reals are to blame?
Run Part IV on $x = \frac{1}{10}$ in base $b = 2$ : compute remainders and digits until they cycle, and conclude $\frac{1}{10} = (0.0\overline{0011})_2$ , with preperiod $1$ and period $4$ . Explain via question 3 why no finite binary string will ever equal $\frac{1}{10}$ — the reason a computer’s floating-point $0.1 + 0.2$ is not exactly $0.3$ .
Synthesis. In one sentence each: where did the proof use (i) completeness, (ii) the Archimedean property, (iii) the uniqueness clause of the floor, (iv) the pigeonhole principle? And the moral: $\intco{0}{1}$ is faithfully coded by proper digit strings, rationality reads off as periodicity — yet analysis prefers the supremum to the digits. Why? (Think about adding two digit strings.)

Solution

Solution of Problem 10.1.

1. For $\frac 18$ : $10 = 8 \cdot 1 + 2$ , $20 = 8 \cdot 2 + 4$ , $40 = 8 \cdot 5 + 0$ ; digits $1, 2, 5$ , remainder $0$ , then only zeros: $\frac 18 = 0.125$ . For $\frac 17$ : $10 = 7 \cdot 1 + 3$ , $30 = 7 \cdot 4 + 2$ , $20 = 7 \cdot 2 + 6$ , $60 = 7 \cdot 8 + 4$ , $40 = 7 \cdot 5 + 5$ , $50 = 7 \cdot 7 + 1$ : digits $1, 4, 2, 8, 5, 7$ , remainders $3, 2, 6, 4, 5, 1$ . The remainder has returned to $r = 1$ , so the six steps repeat verbatim forever: $\frac 17 = 0.(142857)$ , remainders cycling through $1, 3, 2, 6, 4, 5$ .

2. $\frac 13$ in base $2$ ( $r_0 = 1$ ): $2 = 3 \cdot 0 + 2$ , $4 = 3 \cdot 1 + 1$ , and $r = 1$ recurs: $\frac 13 = (0.\overline{01})_2$ . $\frac{5}{16}$ in base $2$ : $10 = 16 \cdot 0 + 10$ , $20 = 16 \cdot 1 + 4$ , $8 = 16 \cdot 0 + 8$ , $16 = 16 \cdot 1 + 0$ : $\frac{5}{16} = (0.0101)_2$ , terminating. $\frac 12$ in base $3$ : $3 = 2 \cdot 1 + 1$ , and $r = 1$ recurs at once: $\frac 12 = (0.\overline{1})_3$ .

3. The algorithm’s remainder after $N$ steps is $r_N = b^N p \bmod q$ (proved formally in question 14; here it is the observation that each step multiplies the remainder by $b$ and reduces mod $q$ ). All later digits are $0$ if and only if some $r_N = 0$ , i.e. $q \mid b^N p$ ; since $\gcd(p, q) = 1$ , Gauss’s lemma gives $q \mid b^N$ . If $q \mid b^N$ , every prime factor of $q$ divides $b^N$ , hence divides $b$ (primality). Conversely, if every prime of $q = p_1^{a_1} \cdots p_r^{a_r}$ divides $b$ , then with $A = \max_i a_i$ each $p_i^{a_i}$ divides $b^A$ , and the $p_i^{a_i}$ are pairwise coprime, so $q \mid b^A$ . For $q = 20 = 2^2 \cdot 5$ : both primes divide $10$ ( $\frac{1}{20} = 0.05$ ), but $2 \nmid 3$ , so $\frac{1}{20}$ repeats forever in base $3$ .

4. $1^2 = 1 < 2 < 4 = 2^2$ gives $s_0 = 1$ . Then $1.4^2 = 1.96 < 2 < 2.25 = 1.5^2$ : $\lfloor 10\sqrt 2 \rfloor = 14$ , $s_1 = 1.4$ . Next $1.41^2 = 1.9881 < 2 < 2.0164 = 1.42^2$ : $s_2 = 1.41$ ; $1.414^2 = 1.999396 < 2 < 2.002225 = 1.415^2$ : $s_3 = 1.414$ ; $1.4142^2 = 1.99996164 < 2 < 2.00024449 = 1.4143^2$ : $s_4 = 1.4142$ . In each case the displayed inequalities say exactly $s_n \leq \sqrt 2 < s_n + 10^{-n}$ , which is the definition of the floor of $10^n \sqrt 2$ .

5. $A_0 = \lfloor x \rfloor = 0$ since $0 \leq x < 1$ . From $A_{n-1} \leq b^{n-1} x < A_{n-1} + 1$ , multiply by $b$ :

b\,A_{n-1} \leq b^n x < b\,A_{n-1} + b .

The integer $b\,A_{n-1}$ is $\leq b^n x$ , so $b\,A_{n-1} \leq A_n$ ; and $b^n x < b\,A_{n-1} + b$ with $b\,A_{n-1} + b$ an integer forces $A_n \leq b\,A_{n-1} + b - 1$ . Hence $0 \leq d_n = A_n - b\,A_{n-1} \leq b - 1$ : a digit.

6. Telescoping: $d_k b^{-k} = A_k b^{-k} - A_{k-1} b^{-(k-1)}$ , so

\sum_{k=1}^n d_k b^{-k} = A_n b^{-n} - A_0 = s_n .

Dividing $A_n \leq b^n x < A_n + 1$ by $b^n$ gives $s_n \leq x < s_n + b^{-n}$ .

7. Induction: $b^0 = 1 \geq 1$ , and $b^{n+1} = b \cdot b^n \geq 2(n + 1) \geq n + 2$ . Monotonicity: $s_n - s_{n-1} = d_n b^{-n} \geq 0$ . Each $s_n \leq x$ (question 6): $x$ is an upper bound of $\{s_n\}$ . For $\varepsilon > 0$ , the Archimedean property provides $n$ with $n + 1 > \frac1\varepsilon$ , hence $b^{-n} < \varepsilon$ , and then $s_n > x - b^{-n} > x - \varepsilon$ by question 6. By Proposition 10.4, $x = \sup_n s_n$ .

8. Suppose $d_k = b - 1$ for all $k > N$ . For $n > N$ , the finite geometric sum gives

s_n = s_N + (b - 1)\sum_{k=N+1}^{n} b^{-k} = s_N + b^{-N} - b^{-n} .

So $x \geq s_n = s_N + b^{-N} - b^{-n}$ for every $n$ ; letting the last term shrink below any $\varepsilon$ (question 7), $x \geq s_N + b^{-N}$ . But question 6 at rank $N$ says $x < s_N + b^{-N}$ : contradiction. The string $(d_n)$ is proper.

9. Bounded: $t_n \leq (b-1)\sum_{k=1}^n b^{-k} = 1 - b^{-n} < 1$ , and $(t_n)$ is nondecreasing, so $y = \sup t_n$ exists with $0 \leq y \leq 1$ . Fix $n$ . For the two-sided estimate: $t_n \leq y$ is clear. By properness pick $m > n$ with $e_m \leq b - 2$ . For $p \geq m$ :

t_p - t_n = \sum_{k=n+1}^{p} e_k b^{-k} \leq (b^{-n} - b^{-p}) - b^{-m} < b^{-n} - b^{-m},

the middle sum losing at least $b^{-m}$ against the all- $(b-1)$ maximum; for $p \leq m$ , $t_p \leq t_m \leq t_n + b^{-n} - b^{-m}$ as well (monotonicity plus the case $p = m$ ). Hence every $t_p \leq t_n + b^{-n} - b^{-m}$ , so $y \leq t_n + b^{-n} - b^{-m} < t_n + b^{-n}$ . (With $n = 0$ : $y < 1$ , so $y \in \intco{0}{1}$ .) Now $b^n t_n = \sum_{k \leq n} e_k b^{n-k}$ is an integer, and $b^n t_n \leq b^n y < b^n t_n + 1$ : so $\lfloor b^n y \rfloor = b^n t_n$ . Finally the digits of $y$ : $d_n(y) = b^n t_n - b \cdot b^{n-1} t_{n-1} = b^n(t_n - t_{n-1}) = e_n$ .

10. Question 9 says: (value of string) has digits (the string); questions 5–8 say: (digits of $x$ ) form a proper string whose truncations have supremum $x$ (question 7). So the two maps compose to the identity in both orders: they are mutually inverse bijections between $\intco{0}{1}$ and the proper strings. If two proper strings had equal value, applying the digit map would make them equal: uniqueness. This is the $b$ -adic expansion theorem.

11. Let $e_n = b - 1$ for $n > M$ , $M \geq 0$ minimal. As in question 8, $t_n = t_M + b^{-M} - b^{-n}$ for $n \geq M$ , so the value is $\sup t_n = t_M + b^{-M}$ . If $M = 0$ the value is $0 + 1 = 1$ : in base $10$ , $0.999\dots = 1$ exactly — not approximately. If $M \geq 1$ , minimality gives $e_M \leq b - 2$ , and the value is

t_M + b^{-M} = \frac{b^M t_M + 1}{b^M} \in \intoo{0}{1},

a $b$ -adic fraction, whose proper expansion is $e_1 \dots e_{M-1}\,(e_M + 1)\,000\dots$ (a terminating string is proper, and its value is the same number). Conversely a real with two representations must have one improper (properness pins down the representation, question 10), hence be of this form. And each $m/b^N \in \intoo{0}{1}$ , written with last nonzero digit $d_N$ , does have the improper twin $d_1 \dots d_{N-1}(d_N - 1)(b-1)(b-1)\dots$ : exactly the $b$ -adic fractions carry two names, all other reals one.

12. Say the strings agree up to $m - 1$ , with common truncation $P = s_{m-1}$ , and $d_m < e_m$ . By question 9 (strict upper estimate at rank $m$ ), $x < P + d_m b^{-m} + b^{-m} = P + (d_m + 1)b^{-m} \leq P + e_m b^{-m} \leq y$ , the last step because $P + e_m b^{-m}$ is $y$ ’s truncation $t_m \leq y$ . So $d_m < e_m \implies x < y$ ; exchanging roles, $e_m < d_m \implies y < x$ ; and since the strings differ at $m$ , one of the two holds. Both directions follow.

13. Let $z = bx - A_1 \in \intco{0}{1}$ (indeed $A_1 \leq bx < A_1 + 1$ ). For $n \geq 0$ : $b^n z = b^{n+1} x - b^n A_1$ with $b^n A_1 \in \Z$ , so by $\lfloor u - K \rfloor = \lfloor u \rfloor - K$ ( $K$ integer),

A_n(z) = A_{n+1}(x) - b^n A_1(x) .

Hence $d_n(z) = A_n(z) - b\,A_{n-1}(z) = A_{n+1} - b^n A_1 - b\,A_n + b^n A_1 = d_{n+1}(x)$ . So the fractional part of $bx$ carries the shifted digits; iterating $m$ times, the fractional part of $b^m x$ has digits $(d_{n+m})_{n \geq 1}$ .

14. Euclidean division: $b^n p = q\,Q_n + r_n$ with $0 \leq r_n < q$ . Divide by $q$ : $b^n x = Q_n + \frac{r_n}{q}$ with $0 \leq \frac{r_n}{q} < 1$ , so $Q_n = \lfloor b^n x \rfloor = A_n$ , giving $A_n = \frac{b^n p - r_n}{q}$ . For the recurrence: $b^n p = b(q\,A_{n-1} + r_{n-1}) = q\,(b\,A_{n-1}) + b\,r_{n-1}$ , so $b^n p$ and $b\,r_{n-1}$ differ by a multiple of $q$ : $r_n = (b\,r_{n-1}) \bmod q$ .

15. Divide $b\,r_{n-1}$ by $q$ : $b\,r_{n-1} = q\,c + r_n$ with $c = \lfloor b\,r_{n-1}/q \rfloor$ . Substituting into the display of question 14: $b^n p = q(b\,A_{n-1} + c) + r_n$ , and uniqueness of Euclidean division identifies $A_n = b\,A_{n-1} + c$ , that is $d_n = c = \lfloor b\,r_{n-1}/q \rfloor$ . Digit $n$ depends only on $r_{n-1}$ — the long division loop of Part I, now certified.

16. The $q + 1$ remainders $r_0, \dots, r_q$ take values in the $q$ -element set $\intint{0}{q-1}$ : by the pigeonhole principle (Corollary 2.3) two coincide, say $r_N = r_{N+T}$ with $0 \leq N < N + T \leq q$ . Since $r_n$ determines $r_{n+1}$ (question 14), induction gives $r_{n+T} = r_n$ for all $n \geq N$ ; since $r_{n-1}$ determines $d_n$ (question 15), $d_{n+T} = d_n$ for all $n \geq N + 1$ . Every rational’s expansion is eventually periodic, with preperiod $\leq q$ and period $\leq q$ .

17. The digits of the fractional part of $b^T y$ are $(d_{n+T}) = (d_n)$ (shift lemma, then pure periodicity): the same proper string as $y$ . By question 10 the values are equal: $b^T y - \lfloor b^T y \rfloor = y$ , so $(b^T - 1)\,y = \lfloor b^T y \rfloor = A_T \in \N$ and

y = \frac{A_T}{b^T - 1} ,

rational with denominator dividing $b^T - 1$ ; the numerator $A_T$ is the integer whose base- $b$ digits are $d_1 \dots d_T$ . Check: $0.(142857) = \frac{142857}{999999}$ , and $142857 \times 7 = 999999$ , so this is $\frac 17$ .

18. If $d_{n+T} = d_n$ for $n > N$ , the fractional part $z$ of $b^N x$ has digits $(d_{N+n})_{n\geq1}$ (shift lemma), which are purely periodic; by question 17, $z \in \Q$ . Then $b^N x = A_N + z$ gives $x = (A_N + z)/b^N \in \Q$ . With question 16: $x$ rational $\iff$ expansion eventually periodic. The right side mentions the base, the left does not: periodicity in one base is equivalent to rationality, hence to periodicity in every base.

19. For $x = \frac 1q$ , $r_n = b^n \bmod q$ . If $\gcd(b, q) = 1$ , then $r_T = r_0 = 1$ if and only if $b^T \equiv 1 \pmod q$ ; such $T$ exists (pigeonhole gives $b^i \equiv b^j$ , $i < j$ , and $b$ is invertible modulo $q$ , so $b^{j-i} \equiv 1$ ), and the least one — the multiplicative order — makes the remainders, hence the digits, purely periodic of period $T$ . No smaller period is possible: a period $T'$ would give $(b^{T'} - 1)\frac1q \in \N$ (question 17), i.e. $q \mid b^{T'} - 1$ . For $q = 7$ , $b = 10$ : $10 \equiv 3$ , $10^2 \equiv 2$ , $10^3 \equiv 6$ , $10^4 \equiv 4$ , $10^5 \equiv 5$ , $10^6 \equiv 1 \pmod 7$ : order $6$ , and indeed $\frac 17$ has period six.

20. The string has infinitely many $0$ s ( $x^*$ ’s digits are mostly zero), so it is proper, and $x^*$ is well defined (question 9). Suppose the digits eventually periodic with period $T$ beyond $N$ . Infinitely many digits equal $1$ (one per triangular number), so some $1$ sits at a position $j > N$ ; then periodicity puts a $1$ at every position $j + kT$ : from $j$ onward, gaps between consecutive $1$ s are at most $T$ . But the $1$ s sit exactly at the triangular numbers, whose consecutive gaps $\frac{(j+1)(j+2)}{2} - \frac{j(j+1)}{2} = j + 1$ exceed $T$ eventually: contradiction. Not eventually periodic, so by question 18, $x^* \notin \Q$ — irrationality read off the rhythm of the digits alone.

21. Given $x < y$ , question 7 provides $n$ with $b^{-n} < y - x$ ; set $m = \lfloor b^n x \rfloor + 1$ . Then $b^n x < m \leq b^n x + 1 < b^n y$ , so $x < \frac{m}{b^n} < y$ : density, for every base at once ( $b = 2$ recovers Exercise 10.8). For $\frac pq \in \intoo{0}{1}$ in base $b = q$ : the first digit is $\lfloor q \cdot \frac pq \rfloor = p$ and the fractional part of $q \cdot \frac pq = p$ is $0$ : all later digits vanish, a terminating expansion $\frac pq = (0.p)_q$ . Terminating depends on the base; periodicity — rationality — does not (question 18).

22. Each $e_k \in \{1, 2\}$ is a digit of base $10$ , and the string never ends in all $9$ s: proper. Its value $y$ lies in $\intco{0}{1}$ and has digits exactly $(e_k)$ (question 9). Fix $k$ : the $k$ -th digit of $y$ is $e_k$ , chosen $\neq$ the $k$ -th digit of $x_k$ , so the proper strings of $y$ and $x_k$ differ, so $y \neq x_k$ (question 10: the coding is injective). Thus $y$ is in no list: no map $\N^* \to \intco{0}{1}$ is surjective. The reals, unlike the rationals, cannot be enumerated — uncountability, whose theory Chapter 12 develops.

23. If the expansions agree up to $n$ , then $x$ and $y$ have the same truncation $s_n$ , and question 6 puts both in $\intco{s_n}{s_n + b^{-n}}$ , an interval of length $b^{-n}$ : $\abs{x - y} < b^{-n}$ . Converse: $x = 0.1$ and $y = 0.0999$ (terminating, hence proper) satisfy $\abs{x - y} = 10^{-4} < 10^{-3}$ , yet their expansions differ at the very first digit. The culprits are the $b$ -adic fractions of question 11: near them, a tiny move flips every displayed digit ( $0.0999 \to 0.1000$ ), because they are precisely the reals where the improper twin lurks.

24. $p = 1$ , $q = 10$ , $b = 2$ , $r_0 = 1$ : $2 = 10 \cdot 0 + 2$ , $4 = 10 \cdot 0 + 4$ , $8 = 10 \cdot 0 + 8$ , $16 = 10 \cdot 1 + 6$ , $12 = 10 \cdot 1 + 2$ — and $r_5 = 2 = r_1$ : the remainders cycle $(2, 4, 8, 6)$ from index $1$ . Digits: $d_1 = 0$ , then the repeating block $d_2 d_3 d_4 d_5 = 0, 0, 1, 1$ :

\tfrac{1}{10} = (0.0\overline{0011})_2 ,

preperiod $1$ , period $4$ . By question 3, a terminating base- $2$ expansion would need every prime of $10$ to divide $2$ ; the prime $5$ refuses. So $0.1$ is not representable by any finite binary string — a computer storing finitely many bits keeps only a truncation, and the accumulated truncation errors are why floating-point $0.1 + 0.2$ differs from $0.3$ in the last bits.

25. (i) Completeness produced the values: $x = \sup s_n$ and $y = \sup t_n$ (questions 7 and 9) — over $\Q$ alone, the proper string of $\sqrt 2$ would name nothing. (ii) The Archimedean property made $b^{-n}$ eventually smaller than any $\varepsilon$ , forcing the truncations to close in on their supremum (questions 7, 21). (iii) The uniqueness clause of the floor identified $Q_n = A_n$ in question 14 and legitimized every digit extraction $\lfloor u - K \rfloor = \lfloor u \rfloor - K$ (question 13). (iv) The pigeonhole principle, applied to finitely many remainders, is the sole engine of periodicity (question 16). Moral: proper strings code $\intco{0}{1}$ faithfully and turn rationality into a visible rhythm; but addition of digit strings requires carries propagating from infinitely far right, so no finite-stage rule computes even the first digit of a sum — whereas the supremum interface of Theorem 10.2 handles all of analysis with one axiom. Digits are a magnificent picture of $\R$ ; the supremum is its engine.

Terms defined in this chapter

Bounds, sup and inf

See all 395 terms in the glossary