The real numbers

The rationals and the reals obey the same rules of arithmetic and the same rules for inequalities, yet the rationals can be listed and the reals cannot, so something separates them that no rule of algebra mentions.

The previous lesson found that split by comparing infinite sets through bijections, and left open what the reals have that the rationals lack. This lesson names it, the completeness axiom, and uses it to pay debts that earlier lessons deferred to "a later lesson": that $ℕ$ has no upper bound in $ℝ$ , used without proof in the lessons on quantifiers, on sets and on order; that the rationals with square less than $2$ have no least upper bound among the rationals, stated in the lesson on order; that some real number has square $2$ , claimed in the lesson on quantifiers; and that a decimal expansion names a real number, which the diagonal argument took for granted. It assumes upper bounds and the supremum from the lesson on order: $u = \sup A$ when $u$ is an upper bound of $A$ lying below every other upper bound. As throughout the course, $ℕ = {1, 2, 3, \dots}$ .

The plan is the one a first analysis course follows. First, write down exactly what is assumed about $ℝ$ : the arithmetic and order rules it shares with $ℚ$ , and the one axiom it does not share. Then derive everything else from that list, including facts so familiar that they seem not to need proof, because several of them turn out to be false in number systems that obey every rule of school algebra.

The gap where $\sqrt{2}$ should be

Work inside $ℚ$ and let $T = {q \in ℚ : q^{2} < 2}$ . It is nonempty, since $1 \in T$ , and any positive $u$ with $u^{2} > 2$ is an upper bound, because an element $q > u$ would have $q^{2} > u^{2} > 2$ . The lesson on order watched the decimals $1.4$ , $1.41$ , $1.414$ climb inside $T$ while $1.5$ , $1.42$ , $1.415$ came down from above, and claimed that no rational is the least upper bound. The proof rests on two pieces of algebra that push a candidate up or down.

The first says a number whose square is below $2$ is never the top of $T$ . Let $u \geq 1$ with $u^{2} < 2$ , and set $h = \frac{2 - u^{2}}{2 u + 1}$ . Then $h > 0$ , and $h < 1$ because $2 - u^{2} \leq 1 < 3 \leq 2 u + 1$ . Since $0 < h < 1$ gives $h^{2} < h$ ,

(u + h)^{2} = u^{2} + 2 u h + h^{2} < u^{2} + h (2 u + 1) = 2

So $u + h$ is larger than $u$ with square still below $2$ . From $u = 1.4$ it gives $h = \frac{0.04}{3.8} = \frac{1}{95}$ , and $(1.4 + \frac{1}{95})^{2} \approx 1.9896$ .

The second says a number whose square is above $2$ is never the least upper bound. Let $u > 0$ with $u^{2} > 2$ , and set $k = \frac{u^{2} - 2}{2 u} > 0$ . Then $u - k = \frac{u^{2} + 2}{2 u}$ is positive, and

(u - k)^{2} = u^{2} - 2 u k + k^{2} > u^{2} - 2 u k = 2

So $u - k$ is a smaller upper bound. From $u = \frac{3}{2}$ it gives $\frac{17}{12}$ , with square $\frac{289}{144}$ , just above $2$ . Both $h$ and $k$ are built from $u$ by the four operations, so if $u$ is rational, so are they.

Example. Prove that $T = {q \in ℚ : q^{2} < 2}$ has no least upper bound in $ℚ$ .

Suppose, for contradiction, that $u \in ℚ$ is the least upper bound of $T$ . Since $1 \in T$ , $u \geq 1$ . Since $\sqrt{2}$ is irrational, as the lesson on contradiction proved, no rational has square $2$ , so $u^{2} \neq 2$ , and either $u^{2} < 2$ or $u^{2} > 2$ . If $u^{2} < 2$ , the rational $u + h$ above lies in $T$ and exceeds $u$ , contradicting that $u$ is an upper bound. If $u^{2} > 2$ , the rational $u - k$ is an upper bound of $T$ smaller than $u$ , contradicting that $u$ is the least. Both cases are impossible, so $T$ has no least upper bound in $ℚ$ .

The structure is worth seeing. Trichotomy splits the candidate into three cases; algebra kills two of them; irrationality kills the third. Nothing is left, so no candidate exists.

Now you. Prove that ${q \in ℚ : q^{2} < 3}$ has no least upper bound in $ℚ$ , using the irrationality of $\sqrt{3}$ .

Answer

Suppose $u \in ℚ$ is the least upper bound. Since $1$ is in the set, $u \geq 1$ , and since $\sqrt{3}$ is irrational, $u^{2} \neq 3$ . If $u^{2} < 3$ , let $h = \frac{3 - u^{2}}{2 u + 1}$ . It is rational and positive, and less than $1$ because $3 - u^{2} \leq 2 < 3 \leq 2 u + 1$ . Then $h^{2} < h$ , so $(u + h)^{2} < u^{2} + h (2 u + 1) = 3$ , and $u + h$ is in the set and exceeds $u$ , a contradiction. If $u^{2} > 3$ , let $k = \frac{u^{2} - 3}{2 u} > 0$ . Then $u - k = \frac{u^{2} + 3}{2 u} > 0$ and $(u - k)^{2} > u^{2} - 2 u k = 3$ . Any element $q$ of the set with $q \geq u - k$ would have $q^{2} \geq (u - k)^{2} > 3$ , so $u - k$ is an upper bound smaller than $u$ , a contradiction.

The ordered field axioms

That proof used only arithmetic, order and the irrationality of $\sqrt{2}$ . To say what the reals have in addition, their familiar properties must be written down as a list, so that it is clear which ones the rationals share.

A field is a set $F$ with two operations, $+$ and $\cdot$ , and two distinguished elements $0$ and $1$ , such that for all $x$ , $y$ , $z$ in $F$ :

(A1) $x + (y + z) = (x + y) + z$ and (A2) $x + y = y + x$ ;
(A3) $x + 0 = x$ , and (A4) there is an element $- x$ with $x + (- x) = 0$ ;
(M1) $x (y z) = (x y) z$ and (M2) $x y = y x$ ;
(M3) $x \cdot 1 = x$ , where $1 \neq 0$ , and (M4) if $x \neq 0$ , there is an element $x^{- 1}$ with $x x^{- 1} = 1$ ;
(D) $x (y + z) = x y + x z$ .

Subtraction and division are abbreviations: $x - y$ means $x + (- y)$ , and $\frac{x}{y}$ means $x y^{- 1}$ for $y \neq 0$ . An ordered field is a field with a total order $\leq$ (reflexive, antisymmetric, transitive, and any two elements comparable, as in the lesson on order) that respects the arithmetic:

(O1) if $x \leq y$ , then $x + z \leq y + z$ ;
(O2) if $0 \leq x$ and $0 \leq y$ , then $0 \leq x y$ .

As usual $x < y$ means $x \leq y$ and $x \neq y$ , and $x$ is positive when $0 < x$ . Totality gives trichotomy: for any $x$ and $y$ , exactly one of $x < y$ , $x = y$ , $y < x$ holds.

Eleven axioms look like very little, but every rule of school algebra and every rule for manipulating inequalities follows from them. Here are the ones used constantly, with proofs, to show how the derivations go; parts (i) to (iii) repeat, for every ordered field, what the first lesson proved for the integers.

Lemma. In any ordered field, for all $x$ , $y$ , $z$ :

(i) negatives are unique: if $x + y = 0$ and $x + y' = 0$ , then $y = y'$ ;

(ii) $0 \cdot x = 0$ ;

(iii) $(- 1) x = - x$ , and $(- x) (- y) = x y$ ;

(iv) if $x y = 0$ , then $x = 0$ or $y = 0$ ;

(v) $x \leq y$ if and only if $0 \leq y - x$ ; in particular $x \leq 0$ if and only if $0 \leq - x$ ;

(vi) if $x < y$ and $0 < z$ , then $x z < y z$ ; if $x < y$ and $z < 0$ , then $y z < x z$ .

Proof. (i) $y = y + 0 = y + (x + y') = (y + x) + y' = 0 + y' = y'$ , using (A3), (A1) and (A2).

(ii) $0 \cdot x = (0 + 0) x = 0 \cdot x + 0 \cdot x$ by (A3) and (D). Adding $- (0 \cdot x)$ to both sides and using (A1), (A4), (A3) leaves $0 = 0 \cdot x$ .

(iii) $x + (- 1) x = 1 \cdot x + (- 1) x = (1 + (- 1)) x = 0 \cdot x = 0$ , so $(- 1) x$ is a negative of $x$ , and by (i) it is $- x$ . Then $(- x) (- y) = (- 1) (- 1) x y$ , and $(- 1) (- 1) = - (- 1) = 1$ , because $- 1 + 1 = 0$ makes $1$ the negative of $- 1$ .

(iv) Suppose $x y = 0$ and $x \neq 0$ . Then $y = (x^{- 1} x) y = x^{- 1} (x y) = x^{- 1} \cdot 0 = 0$ .

(v) If $x \leq y$ , add $- x$ to both sides by (O1): $0 \leq y - x$ . If $0 \leq y - x$ , add $x$ : $x \leq y$ . Taking $y = 0$ gives the second statement.

(vi) Suppose $x < y$ and $0 < z$ . By (v), $0 \leq y - x$ , and $y - x \neq 0$ . By (O2), $0 \leq (y - x) z = y z - x z$ , and by (iv) the product is not $0$ , since neither factor is. So $0 < y z - x z$ , and by (v), $x z < y z$ . If $z < 0$ , then $0 < - z$ by (v), and the first part gives $x (- z) < y (- z)$ , that is, $- x z < - y z$ ; adding $x z + y z$ to both sides gives $y z < x z$ . $□$

Part (vi) is the rule "multiplying by a negative number reverses an inequality", and it is a theorem, not a convention. The same style of argument shows that inequalities can be added: if $a \leq b$ and $c \leq d$ then $a + c \leq b + c \leq b + d$ .

Example. Prove that in any ordered field, $x^{2} \geq 0$ for every $x$ , and deduce that $0 < 1$ .

Let $x$ be an element of the field. By totality, $0 \leq x$ or $x \leq 0$ . If $0 \leq x$ , then (O2) with both factors equal to $x$ gives $0 \leq x \cdot x = x^{2}$ . If $x \leq 0$ , then $0 \leq - x$ by part (v) of the lemma, and (O2) gives $0 \leq (- x) (- x)$ , which equals $x^{2}$ by part (iii). So $x^{2} \geq 0$ in both cases.

Now $1 = 1 \cdot 1 = 1^{2} \geq 0$ , and $1 \neq 0$ by (M3), so $0 < 1$ .

The fact looks too obvious to prove, and yet it has content: nothing in the order axioms says directly that $1$ is on the positive side. It then follows that $1 + 1 > 1 > 0$ , and by induction that $1 + 1 + \dots + 1$ ( $n$ terms) is positive for every $n \in ℕ$ . So in an ordered field the elements $1$ , $1 + 1$ , $1 + 1 + 1$ , and so on are all different and all positive, and they form a copy of $ℕ$ inside the field. Negatives and quotients of these give copies of $ℤ$ and $ℚ$ . When this lesson writes $ℕ \subseteq ℝ$ , that copy is what is meant.

Now you. Prove that in any ordered field, if $0 < a$ , then $0 < a^{- 1}$ , and if $0 < a < b$ , then $0 < b^{- 1} < a^{- 1}$ .

Answer

Let $0 < a$ . Then $a \neq 0$ , so $a^{- 1}$ exists, and $a^{- 1} \neq 0$ because $a a^{- 1} = 1 \neq 0$ (by part (ii) of the lemma, $a \cdot 0 = 0$ ). Suppose, for contradiction, that $a^{- 1} < 0$ . Multiplying the inequality $0 < a$ by the negative element $a^{- 1}$ reverses it, by part (vi): $a \cdot a^{- 1} < 0 \cdot a^{- 1}$ , that is, $1 < 0$ . That contradicts the Example, so by trichotomy $0 < a^{- 1}$ .

Now let $0 < a < b$ . Then $b > 0$ , so $a^{- 1} > 0$ and $b^{- 1} > 0$ by the first part, and their product $a^{- 1} b^{- 1}$ is positive by (O2) and part (iv) of the lemma. Multiplying $a < b$ by this positive element keeps the direction, by part (vi): $a \cdot a^{- 1} b^{- 1} < b \cdot a^{- 1} b^{- 1}$ , which simplifies to $b^{- 1} < a^{- 1}$ .

Why can the complex numbers not be put in order?

They can be put in some total order, just not one that respects the arithmetic. The Example says that in every ordered field, every square is non-negative and $1$ is positive, so $- 1$ is negative (by part (v) of the lemma, since $0 < 1$ gives $- 1 < 0$ ). In $ℂ$ , $- 1 = i^{2}$ is a square. So an order on $ℂ$ satisfying (O1) and (O2) would make $- 1$ both non-negative and negative, which trichotomy forbids. No ordered field contains a square root of $- 1$ .

The comment after the Example rules out another family. In the field $ℤ / 5 ℤ$ of remainders modulo $5$ , from the lesson on equivalence relations, $1 + 1 + 1 + 1 + 1 = 0$ . In an ordered field, a sum of $n$ copies of $1$ is positive, never $0$ . So no finite field can be ordered, and every ordered field is infinite and contains a copy of $ℚ$ , as the Example showed. In that sense $ℚ$ is the smallest ordered field, sitting inside all of them.

Neither argument uses completeness. They show how much the eleven axioms already decide: the sign of $1$ , the sign of every square, which fields can be ordered at all. What they cannot decide is whether a given element, such as a square root of $2$ , exists, and that is the next section's point.

What the rationals lack

The trouble is that $ℚ$ satisfies every one of these axioms. So no argument from the ordered field axioms alone can produce a number whose square is $2$ , since the same argument would work in $ℚ$ , where there is none. This is a common pattern for proving that something does not follow from a list of axioms: exhibit one structure satisfying all of them in which the conclusion fails. Here $ℚ$ is that structure.

The gap at $\sqrt{2}$ is not a single blemish. The same algebra, with $3$ , $5$ or any non-square in place of $2$ , shows that the rationals below $\sqrt{3}$ , $\sqrt{5}$ and so on have no rational least upper bound either, and the previous lesson showed that the rationals are countable while the reals are not, so all but a countable part of the real line is missing from $ℚ$ . The rationals are full of holes, and a single additional axiom fills all of them.

The completeness axiom

The missing property concerns least upper bounds, exactly where the rationals failed.

Completeness axiom. Every nonempty set of real numbers that is bounded above has a least upper bound in $ℝ$ .

The reals are an ordered field satisfying this axiom, a complete ordered field, and that is all this course assumes about them. Every other property of $ℝ$ used from here on is proved from the eleven ordered field axioms and this one. The rationals are an ordered field that is not complete: $T$ is nonempty and bounded above, and has no rational least upper bound.

Both conditions in the axiom are needed. The empty set has every real as an upper bound, and so no least one. The set $ℕ$ , as the section on the Archimedean property proves, has no upper bound at all. And the supremum, when it exists, is unique: if $u$ and $u'$ are both least upper bounds of $A$ , each is an upper bound lying below every upper bound, so $u \leq u'$ and $u' \leq u$ , and antisymmetry gives $u = u'$ . That is why the notation $\sup A$ is allowed.

A supremum need not belong to the set. When it does, it is the maximum $\max A$ , the greatest element; $\sup [0, 1] = \max [0, 1] = 1$ , while $\sup [0, 1) = 1$ and $[0, 1)$ has no maximum. The axiom is exactly what guarantees a supremum when there is no maximum to fall back on. Every nonempty finite set has a maximum, so completeness says nothing new about finite sets; it is a statement about infinite ones.

The idea took its modern form in 1872, in two independent constructions. Richard Dedekind, in Braunschweig, published Stetigkeit und irrationale Zahlen ("Continuity and irrational numbers"), defining a real number as a cut of the rationals into a lower and an upper class; he dated the idea to November 1858, when, teaching calculus in Zurich, he could find no rigorous proof that a bounded increasing quantity approaches a limit. The same year Georg Cantor, in Halle, built the reals from sequences of rationals whose terms eventually cluster together. In both constructions completeness is a theorem.

Where do the real numbers come from, if they are only described by axioms?

An axiom list describes what is wanted; it does not show that anything fits the description. Dedekind's construction does, using nothing but $ℚ$ and sets.

A cut is a subset $α$ of $ℚ$ that is nonempty, is not all of $ℚ$ , is closed downwards (if $q \in α$ and $p < q$ then $p \in α$ ), and has no greatest element. The rationals below $\frac{1}{2}$ form a cut, and so does $T$ together with all negative rationals, that is, ${q \in ℚ : q < 0 or q^{2} < 2}$ . The first cut is "the number $\frac{1}{2}$ "; the second has no rational at its top and is "the number $\sqrt{2}$ ". Dedekind defines the reals to be the cuts. Order is inclusion: $α \leq β$ means $α \subseteq β$ . Addition is $α + β = {p + q : p \in α, q \in β}$ , and multiplication is defined first for positive cuts, then extended by signs.

The hard work is checking the eleven ordered field axioms, which is long and unilluminating. Completeness, the axiom $ℚ$ lacked, is the easy one. If $A$ is a nonempty set of cuts bounded above by a cut $β$ , its union $⋃ A$ is again a cut (nonempty, contained in $β$ so not all of $ℚ$ , closed downwards, and with no greatest element since no member of $A$ has one), it contains every member of $A$ , and it is contained in every upper bound. So $\sup A = ⋃ A$ . Taking suprema, which is what fails in $ℚ$ , becomes taking unions, which always works.

Cantor's construction goes through equivalence classes, in the manner of the lesson on equivalence relations, where $ℚ$ was built from pairs of integers. A real number is a class of sequences of rationals whose terms eventually stay as close together as you like, two sequences being equivalent when their difference tends to $0$ .

The two constructions give the same answer. Any two complete ordered fields are isomorphic: there is a bijection between them that preserves addition, multiplication and order, and it is unique. So the axioms describe exactly one structure, up to renaming the elements, and it no longer matters whether a real number "is" a cut, a class of sequences, or an infinite decimal. This is why a course may start from the axioms, as this one does, and never look at a construction again.

Working with the supremum

The definition of $\sup A$ quantifies over every upper bound, which is awkward to check directly. Proofs usually want a form that tests only numbers just below the candidate. The lesson on order stated this form for $ℝ$ ; here it is with a proof.

Example. Prove that $s = \sup A$ if and only if $s$ is an upper bound of $A$ and, for every $ε > 0$ , some $a \in A$ satisfies $a > s - ε$ .

( $\Rightarrow$ ) Suppose $s = \sup A$ . Then $s$ is an upper bound by definition. Let $ε > 0$ . Since $s - ε < s$ and $s$ lies below every upper bound, $s - ε$ is not an upper bound, so some $a \in A$ has $a > s - ε$ .

( $\Leftarrow$ ) Suppose $s$ is an upper bound with the $ε$ property, and let $v$ be any upper bound of $A$ . Suppose, for contradiction, that $v < s$ , and take $ε = s - v > 0$ . Some $a \in A$ has $a > s - ε = v$ , contradicting that $v$ is an upper bound. So $s \leq v$ for every upper bound $v$ , and $s = \sup A$ .

The second half chose $ε$ to fit the contradiction. Picking $ε$ after the thing to be defeated is known is the move the next lesson, on limits, makes over and over. The characterisation also has a sequential flavour: taking $ε = 1, \frac{1}{2}, \frac{1}{3}, \dots$ produces elements $a_{1}, a_{2}, a_{3}, \dots$ of $A$ with $s - \frac{1}{n} < a_{n} \leq s$ , a sequence in $A$ that closes in on its supremum.

A classic pitfall sits here. Strict inequalities do not survive taking suprema. Every element of $[0, 1)$ is less than $1$ , and yet $\sup [0, 1) = 1$ , not something less than $1$ . What does survive is the weak version: if every $a \in A$ satisfies $a \leq c$ , then $c$ is an upper bound, so $\sup A \leq c$ . A proof that concludes " $\sup A < c$ " from " $a < c$ for all $a$ " has made this mistake, and the decimal $0.999 \dots$ at the end of the lesson is its most famous victim.

Lower bounds need no second axiom.

Proposition. Every nonempty set of real numbers that is bounded below has a greatest lower bound, $\inf A = - \sup (- A)$ , where $- A = {- a : a \in A}$ .

Proof. Let $A$ be nonempty with a lower bound $m$ . Then $- A$ is nonempty, and $- m$ is an upper bound of it: every element is $- a$ with $a \geq m$ , so $- a \leq - m$ by part (v) of the lemma. By completeness, $- A$ has a supremum $s$ . Put $t = - s$ . For every $a \in A$ , $- a \leq s$ , so $a \geq - s = t$ , and $t$ is a lower bound of $A$ . If $m'$ is any lower bound of $A$ , then $- m'$ is an upper bound of $- A$ by the same reasoning, so $s \leq - m'$ , that is, $m' \leq t$ . So $t$ is the greatest lower bound. $□$

The infimum $\inf A$ is the greatest lower bound, and the minimum $\min A$ is a least element when one exists. Negation turns upper bounds into lower bounds and back, so every fact about suprema has a mirror image about infima, proved by applying the fact to $- A$ .

Now you. Prove that $t = \inf A$ if and only if $t$ is a lower bound of $A$ and, for every $ε > 0$ , some $a \in A$ satisfies $a < t + ε$ .

Answer

( $\Rightarrow$ ) Suppose $t = \inf A$ . It is a lower bound by definition. Let $ε > 0$ . Since $t + ε > t$ and $t$ lies above every lower bound, $t + ε$ is not a lower bound, so some $a \in A$ has $a < t + ε$ .

( $\Leftarrow$ ) Suppose $t$ is a lower bound with this property, and let $m$ be any lower bound. If $m > t$ , take $ε = m - t > 0$ : some $a \in A$ has $a < t + ε = m$ , contradicting that $m$ is a lower bound. So $m \leq t$ for every lower bound $m$ , and $t = \inf A$ .

The Archimedean property

The lessons on quantifiers, on sets and on order used, without proof, that $ℕ$ has no upper bound in $ℝ$ . It sounds like something no proof could make clearer. It is not a consequence of the ordered field axioms, though: the deeper explanation below describes an ordered field containing an element larger than every natural number. In $ℝ$ it follows from completeness.

Theorem (the Archimedean property). For every real number $x$ there is a natural number $n$ with $n > x$ .

Proof. Suppose, for contradiction, that some real $x$ has $n \leq x$ for every $n \in ℕ$ . Then $ℕ$ is nonempty and bounded above, so by completeness it has a supremum $s$ . By the characterisation of the supremum with $ε = 1$ , some $n \in ℕ$ has $n > s - 1$ . Then $n + 1 > s$ , and $n + 1 \in ℕ$ , contradicting that $s$ is an upper bound of $ℕ$ . $□$

The proof is short because completeness did the work. It also shows the pattern of many completeness arguments: assume the bad thing, take a supremum that the bad thing makes available, and use the characterisation to push past it.

Three consequences are used constantly, and each is one line.

Corollary. (i) For every $ε > 0$ there is $n \in ℕ$ with $\frac{1}{n} < ε$ . (ii) For every $x > 0$ and every real $y$ there is $n \in ℕ$ with $n x > y$ . (iii) For every real $x$ there are integers $m$ and $m'$ with $m < x < m'$ .

Proof. (i) Take $n > \frac{1}{ε}$ and multiply both sides by the positive number $\frac{ε}{n}$ , which gives $ε > \frac{1}{n}$ . (ii) Take $n > \frac{y}{x}$ and multiply by the positive number $x$ . (iii) Take $m' \in ℕ$ with $m' > x$ , and $k \in ℕ$ with $k > - x$ ; then $m = - k$ satisfies $m < x$ . $□$

Part (i) is the form earlier lessons used: for $ε = 0.03$ , the condition $n > \frac{1}{0.03} = 33.3 \dots$ is first met at $n = 34$ , and $\frac{1}{34} \approx 0.0294$ . Part (ii) is the form Archimedes and Euclid had in mind: however small a length $x$ and however large a length $y$ , enough copies of $x$ laid end to end exceed $y$ . The fourth definition of Book V of Euclid's Elements says that two magnitudes have a ratio when each, multiplied, can exceed the other, and Archimedes used the property as an explicit assumption in the third century BC.

Part (iii) leads to the integer part of a real number.

Proposition (the floor). For every real number $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ . It is written $⌊ x ⌋$ .

Proof. Existence. By part (iii) of the corollary there are integers $k$ and $m'$ with $k < x < m'$ . Let $S$ be the set of integers greater than $x$ . It contains $m'$ , so it is nonempty, and every element exceeds $k$ . Subtracting $k$ from each element of $S$ gives a nonempty set of natural numbers, which by the well-ordering principle has a least element; adding $k$ back, $S$ has a least element $j$ . Then $j > x$ , and $j - 1 \notin S$ , so $j - 1 \leq x$ . Put $m = j - 1$ : then $m \leq x < m + 1$ .

Uniqueness. If $m \leq x < m + 1$ and $m' \leq x < m' + 1$ for integers $m$ and $m'$ , then $m < m' + 1$ and $m' < m + 1$ , so $- 1 < m - m' < 1$ . The only integer strictly between $- 1$ and $1$ is $0$ , so $m = m'$ . $□$

So $⌊ 3.7 ⌋ = 3$ , $⌊ 5 ⌋ = 5$ and $⌊ - 2.5 ⌋ = - 3$ , not $- 2$ , since $- 3 \leq - 2.5 < - 2$ . The floor is the real-number version of the quotient in the division algorithm of the lesson on direct proof, whose deeper explanation noted that dividing reals with remainder needs "the fact that the integers are not bounded above inside $ℝ$ ". This is that fact at work.

Example. Prove that $\inf {\frac{1}{n} : n \in ℕ} = 0$ , and that the infimum is not a minimum.

Every $\frac{1}{n}$ is positive (the reciprocal of a positive element is positive), so $0$ is a lower bound. Let $ε > 0$ . By part (i) of the corollary some $n \in ℕ$ has $\frac{1}{n} < ε = 0 + ε$ . By the characterisation of the infimum, $\inf {\frac{1}{n} : n \in ℕ} = 0$ . It is not a minimum because $0$ is not in the set: $\frac{1}{n} = 0$ would give $1 = n \cdot 0 = 0$ .

This is the whole content of the statement $\frac{1}{n} \to 0$ , which the next lesson turns into its first proved limit. Without the Archimedean property, the set ${\frac{1}{n}}$ could have a positive lower bound.

Now you. Prove that for every $x > 0$ there is $n \in ℕ$ with $\frac{1}{2^{n}} < x$ , and deduce that $\inf {\frac{1}{2^{n}} : n \in ℕ} = 0$ .

Answer

First, $2^{n} > n$ for every $n \in ℕ$ , by induction: $2^{1} = 2 > 1$ , and if $2^{n} > n$ then $2^{n + 1} = 2 \cdot 2^{n} > 2 n \geq n + 1$ . Now let $x > 0$ . By the Archimedean property there is $n \in ℕ$ with $n > \frac{1}{x}$ , so $2^{n} > n > \frac{1}{x}$ , and taking reciprocals of positive numbers reverses the inequality: $\frac{1}{2^{n}} < x$ .

Every $\frac{1}{2^{n}}$ is positive, so $0$ is a lower bound of the set. For $ε > 0$ , the first part with $x = ε$ gives an element $\frac{1}{2^{n}} < 0 + ε$ . By the characterisation, the infimum is $0$ . Repeated halving shrinks below every positive number, which is what makes bisection work.

Are there ordered fields in which

ℕ

is bounded?

Yes, and the simplest is built from polynomials. Let $F$ be the set of quotients $\frac{p (t)}{q (t)}$ of polynomials in a letter $t$ with real coefficients, $q$ not the zero polynomial, added and multiplied as algebraic fractions. It is a field, for the same reasons that $ℚ$ is a field built from $ℤ$ . Order it by declaring a nonzero element $\frac{p (t)}{q (t)}$ positive when the leading coefficients of $p$ and $q$ (the coefficients of their highest powers of $t$ ) have the same sign, and write $f < g$ when $g - f$ is positive. One can check that this is a total order satisfying (O1) and (O2). Informally, $f$ is positive when $f (t)$ is positive for all sufficiently large real $t$ .

In this field, $t - n$ has leading coefficient $1$ for every natural number $n$ , so $t - n$ is positive and $t > n$ . The element $t$ is an upper bound for $ℕ$ , and $F$ is an ordered field in which the Archimedean property fails. Its reciprocal $\frac{1}{t}$ is positive and smaller than every $\frac{1}{n}$ , since $\frac{1}{n} - \frac{1}{t} = \frac{t - n}{n t}$ has leading coefficients $1$ and $n$ . Such an element is an infinitesimal: positive, yet smaller than every positive rational. By the theorem above, $F$ cannot be complete, and indeed $ℕ$ is bounded in $F$ with no least upper bound (if $s$ were one, the proof of the theorem would find $n \in ℕ$ with $n > s - 1$ , and then $n + 1 > s$ ).

This matters for two reasons. It shows that the Archimedean property genuinely depends on completeness, so the proof above is not proving something that was already assumed. And it answers the old worry about infinitesimals. Leibniz built calculus on quantities infinitely small yet not zero, and his critics, most sharply George Berkeley in The Analyst (1734), asked how such things could exist. The $ε$ definitions of the next lesson were the nineteenth century's answer: in $ℝ$ there are no infinitesimals, and none are needed. In the 1960s Abraham Robinson showed that Leibniz's approach can also be made rigorous, by working in a larger ordered field with infinitesimals, which he called non-standard analysis. Fields like $F$ are the simplest glimpse of such worlds.

Computing suprema and infima

The working method has two stages. First, guess: list some elements, and see where they pile up. Then verify, using the characterisations: show the guess is a bound, and show that nothing closer is. If the guess belongs to the set, the second stage is automatic, because a bound that belongs to the set is a maximum or minimum, and any upper bound must be at least as large as an element of the set.

Example. Find the supremum and infimum of $A = {(- 1)^{n} + \frac{1}{n} : n \in ℕ}$ , and decide whether each is a maximum or minimum.

The first elements, at $n = 1, 2, 3, 4, 5, 6$ , are $0$ , $\frac{3}{2}$ , $- \frac{2}{3}$ , $\frac{5}{4}$ , $- \frac{4}{5}$ , $\frac{7}{6}$ . The even terms come down towards $1$ from $\frac{3}{2}$ ; the odd terms come down towards $- 1$ . The guess is $\sup A = \frac{3}{2}$ and $\inf A = - 1$ .

The supremum. If $n$ is even, then $n \geq 2$ , so $\frac{1}{n} \leq \frac{1}{2}$ and the element is $1 + \frac{1}{n} \leq \frac{3}{2}$ . If $n$ is odd, the element is $- 1 + \frac{1}{n} \leq - 1 + 1 = 0 < \frac{3}{2}$ . So $\frac{3}{2}$ is an upper bound. It is the element at $n = 2$ , so any upper bound is at least $\frac{3}{2}$ . Hence $\sup A = \max A = \frac{3}{2}$ .

The infimum. Every element exceeds $- 1$ : for even $n$ it is $1 + \frac{1}{n} > 1$ , and for odd $n$ it is $- 1 + \frac{1}{n} > - 1$ . So $- 1$ is a lower bound. Let $ε > 0$ . By the Archimedean property there is $n \in ℕ$ with $n > \frac{1}{ε}$ ; if $n$ is even, replace it by $n + 1$ , which is odd and still exceeds $\frac{1}{ε}$ . For this odd $n$ , the element $- 1 + \frac{1}{n}$ lies in $A$ and is less than $- 1 + ε$ . By the characterisation of the infimum, $\inf A = - 1$ . It is not a minimum, since every element is strictly greater than $- 1$ .

Notice where the Archimedean property entered: only in the part that was not attained. That is typical. Suprema and infima that belong to the set need only algebra; those that do not need a way to get arbitrarily close, and in $ℝ$ that way almost always runs through $\frac{1}{n} \to 0$ .

Now you. Find the supremum and infimum of $B = {\frac{1}{n} - \frac{1}{m} : n, m \in ℕ}$ , and decide whether each is attained.

Answer

Guess $\sup B = 1$ and $\inf B = - 1$ .

The supremum. For all $n, m \in ℕ$ , $\frac{1}{n} - \frac{1}{m} < \frac{1}{n} \leq 1$ , since $\frac{1}{m} > 0$ and $n \geq 1$ . So $1$ is an upper bound, and it is never attained, since every element is strictly less than $1$ . Let $ε > 0$ , and choose $m \in ℕ$ with $\frac{1}{m} < ε$ , by the Archimedean property. With $n = 1$ , the element $1 - \frac{1}{m}$ lies in $B$ and exceeds $1 - ε$ . By the characterisation, $\sup B = 1$ .

The infimum. Exchanging $n$ and $m$ turns the element $\frac{1}{n} - \frac{1}{m}$ into its negative, so $- B = B$ . By the proposition on infima, $\inf B = - \sup (- B) = - \sup B = - 1$ , and it is not attained, because $- 1 = \frac{1}{n} - \frac{1}{m}$ would mean $\frac{1}{m} - \frac{1}{n} = 1$ , which the first part ruled out.

Two general facts save work in such computations, and both follow from the definitions in a line or two. If $A \subseteq B$ , both nonempty and $B$ bounded above, then $\sup A \leq \sup B$ , since $\sup B$ is an upper bound of $B$ and hence of $A$ . And if $A$ and $B$ are nonempty and every element of $A$ is at most every element of $B$ , then $\sup A \leq \inf B$ , since each $b \in B$ is an upper bound of $A$ , so $\sup A \leq b$ , and then $\sup A$ is a lower bound of $B$ . The sheet at the end proves more, such as $\sup (A + B) = \sup A + \sup B$ .

Square roots exist

The lesson on quantifiers said that "some $x$ has $x^{2} = 2$ " is false over the rationals and true over the reals. The rational half was the irrationality of $\sqrt{2}$ . The real half needs completeness, and the proof is the argument of the first section run again, with a supremum now available to run it on. It costs nothing extra to do every positive number at once.

Theorem. For every real $a > 0$ there is exactly one real $s > 0$ with $s^{2} = a$ .

Proof. Let $S = {x \in ℝ : x \geq 0 and x^{2} < a}$ . It is nonempty, since $0 \in S$ . It is bounded above by $1 + a$ : if $x > 1 + a$ , then $x > 1$ , so $x^{2} = x \cdot x > x > 1 + a > a$ , and $x \notin S$ . By completeness, $S$ has a supremum $s$ , and $s \geq 0$ because $0 \in S$ . By trichotomy, $s^{2} < a$ , $s^{2} = a$ or $s^{2} > a$ . We rule out the first and the last.

Suppose $s^{2} < a$ . Let $h$ be the smaller of $\frac{1}{2}$ and $\frac{a - s^{2}}{2 s + 1}$ . Then $0 < h < 1$ , so $h^{2} < h$ , and $h (2 s + 1) \leq a - s^{2}$ . Hence

(s + h)^{2} = s^{2} + 2 s h + h^{2} < s^{2} + h (2 s + 1) \leq a

so $s + h \in S$ . But $s + h > s$ , contradicting that $s$ is an upper bound of $S$ .

Suppose $s^{2} > a$ . Then $s > 0$ (as $s = 0$ would give $s^{2} = 0 < a$ ). Let $k = \frac{s^{2} - a}{2 s} > 0$ . Then $s - k = \frac{s^{2} + a}{2 s} > 0$ , and

(s - k)^{2} = s^{2} - 2 s k + k^{2} > s^{2} - 2 s k = a

If some $x \in S$ had $x \geq s - k$ , then, both being non-negative, $x^{2} \geq (s - k)^{2} > a$ , contradicting $x \in S$ . So $s - k$ is an upper bound of $S$ , smaller than $s$ , contradicting that $s$ is the least.

Hence $s^{2} = a$ , and $s > 0$ since $a > 0$ . For uniqueness, suppose $t > 0$ and $t^{2} = a$ . Then $(s - t) (s + t) = s^{2} - t^{2} = 0$ , and $s + t > 0$ , so by part (iv) of the lemma, $s - t = 0$ . $□$

The positive square root of $a$ is written $\sqrt{a}$ . For $a = 2$ , the proof is the first section's argument with one change. Over $ℚ$ , algebra ruled out both inequalities, irrationality ruled out equality, and no candidate was left. Over $ℝ$ , completeness supplies the candidate, the same algebra rules out both inequalities, and equality is what remains. The gap in the rationals is exactly where the reals have a number.

The same method gives $n$ th roots: for every $a > 0$ and $n \in ℕ$ there is a unique $s > 0$ with $s^{n} = a$ . Only the algebra for pushing a candidate up or down changes, and the problem sheet does the case $n = 3$ . In particular $ℝ$ contains irrational numbers, which the ordered field axioms alone could never have produced.

The rationals and irrationals are dense

For all their gaps, the rationals are everywhere: no interval of the real line, however short, avoids them. A set $D \subseteq ℝ$ is dense in $ℝ$ when every open interval $(a, b)$ with $a < b$ contains an element of $D$ .

Theorem (density of the rationals). For all real $a < b$ there is a rational $q$ with $a < q < b$ .

Proof. Since $b - a > 0$ , the Archimedean property gives $n \in ℕ$ with $\frac{1}{n} < b - a$ , that is, $n b - n a > 1$ . Let $m = ⌊ n a ⌋ + 1$ . By the definition of the floor, $m - 1 \leq n a < m$ , so

n a < m \leq n a + 1 < n b

Dividing by the positive number $n$ gives $a < \frac{m}{n} < b$ , and $\frac{m}{n}$ is rational. $□$

The idea is a ruler. Marks spaced $\frac{1}{n}$ apart, with $\frac{1}{n}$ smaller than the gap $b - a$ , cannot all jump over the interval, and the floor finds the first mark past $a$ . Between $0.3$ and $0.31$ the gap is $0.01$ , so the proof takes $n = 101$ ; then $n a = 30.3$ , $m = 31$ , and $\frac{31}{101} \approx 0.3069$ lies between them.

Applying the theorem again to $(a, q)$ and to $(q, b)$ , and so on, gives as many rationals in $(a, b)$ as you like, so every interval contains infinitely many. The irrationals, which the previous lesson showed are far more numerous than the rationals, are dense too.

Example. Prove that for all real $a < b$ there is an irrational $x$ with $a < x < b$ .

Let $a < b$ . Then $a - \sqrt{2} < b - \sqrt{2}$ , so by the density of the rationals there is a rational $q$ with $a - \sqrt{2} < q < b - \sqrt{2}$ . Put $x = q + \sqrt{2}$ ; adding $\sqrt{2}$ throughout gives $a < x < b$ . Suppose $x$ were rational. Then $\sqrt{2} = x - q$ would be a difference of rationals, hence rational, which it is not. So $x$ is irrational.

The proof shifts the whole problem by one known irrational, solves it with a rational, and shifts back. It needed the existence of $\sqrt{2}$ as a real number, from the previous section, and its irrationality, from the lesson on contradiction. Between $0.3$ and $0.31$ it finds $q$ between $0.3 - 1.41421 \dots$ and $0.31 - 1.41421 \dots$ , for instance $q = - 1.11$ , and the irrational $\sqrt{2} - 1.11 = 0.30421 \dots$ .

Now you. Prove that every real number $x$ is the supremum of the rationals below it: $x = \sup {q \in ℚ : q < x}$ .

Answer

Let $x$ be real and $Q_{x} = {q \in ℚ : q < x}$ . By the density of the rationals there is a rational between $x - 1$ and $x$ , so $Q_{x}$ is nonempty, and it is bounded above by $x$ by its definition. So its supremum exists, and $x$ is an upper bound. Let $ε > 0$ . By density there is a rational $q$ with $x - ε < q < x$ ; then $q \in Q_{x}$ and $q > x - ε$ . By the characterisation of the supremum, $\sup Q_{x} = x$ .

This says every real number is pinned down by the rationals below it, which is exactly the idea behind Dedekind's construction: the set $Q_{x}$ is the cut that represents $x$ .

Density settles the last claim of the lesson on order, that $T = {q \in ℚ : q^{2} < 2}$ has supremum $\sqrt{2}$ in $ℝ$ . Every $q \in T$ has $q < \sqrt{2}$ , since a rational $q \geq \sqrt{2}$ would be positive, and squaring preserves order on positive numbers, so it would have $q^{2} \geq 2$ . And for any $b < \sqrt{2}$ , density gives a rational $q$ strictly between the larger of $b$ and $0$ and $\sqrt{2}$ , which lies in $T$ and exceeds $b$ . So the set that had no supremum in $ℚ$ has one in $ℝ$ , and it is the number the rationals were missing.

Density is a strange property to hold alongside countability. The rationals are dense, so every interval contains infinitely many, and yet they can be listed, so they are, in the sense of the previous lesson, a vanishingly small part of the line. Both facts are true at once, and neither contradicts the other.

Nested intervals

Completeness has several equivalent forms, and one of them is geometric. Picture a sequence of closed intervals, each inside the one before, shrinking down. In $ℝ$ something is always left.

Theorem (nested intervals). Let $[a_{1}, b_{1}] \supseteq [a_{2}, b_{2}] \supseteq [a_{3}, b_{3}] \supseteq \dots$ be closed bounded intervals, with $a_{n} \leq b_{n}$ for every $n$ . Then there is a real number $c$ lying in every one of them. If, in addition, for every $ε > 0$ some $n$ has $b_{n} - a_{n} < ε$ , then there is exactly one such $c$ .

Proof. Nesting means $a_{1} \leq a_{2} \leq a_{3} \leq \dots$ and $b_{1} \geq b_{2} \geq b_{3} \geq \dots$ . First, $a_{m} \leq b_{n}$ for all $m$ and $n$ . If $m \leq n$ , then $a_{m} \leq a_{n} \leq b_{n}$ . If $m > n$ , then $a_{m} \leq b_{m} \leq b_{n}$ .

So the set $A = {a_{m} : m \in ℕ}$ is nonempty and every $b_{n}$ is an upper bound of it. By completeness it has a supremum $c$ . Since $c$ is an upper bound of $A$ , $a_{n} \leq c$ for every $n$ ; since $c$ is the least upper bound and $b_{n}$ is an upper bound, $c \leq b_{n}$ for every $n$ . Hence $c \in [a_{n}, b_{n}]$ for every $n$ .

For uniqueness, suppose $c$ and $d$ both lie in every interval, and suppose $c \neq d$ . Let $ε = | c - d | > 0$ , and choose $n$ with $b_{n} - a_{n} < ε$ . Both $c$ and $d$ lie in $[a_{n}, b_{n}]$ , so $| c - d | \leq b_{n} - a_{n} < ε = | c - d |$ , which is impossible. So $c = d$ . $□$

Each hypothesis is needed, and the counterexamples are worth knowing.

Closed. The open intervals $(0, \frac{1}{n})$ are nested, but their intersection is empty, as the lesson on sets showed: a positive $x$ in all of them would satisfy $x < \frac{1}{n}$ for every $n$ , against the Archimedean property.
Bounded. The closed intervals $[n, \infty)$ are nested with empty intersection, since a real in all of them would be at least every natural number.
In $ℝ$ . In $ℚ$ , take $a_{n}$ to be $\sqrt{2}$ truncated after $n$ decimal places and $b_{n} = a_{n} + 10^{- n}$ : the intervals $[1.4, 1.5] \supseteq [1.41, 1.42] \supseteq [1.414, 1.415] \supseteq \dots$ have rational endpoints, and in $ℝ$ their only common point is $\sqrt{2}$ . So the rational intervals ${q \in ℚ : a_{n} \leq q \leq b_{n}}$ are nested, nonempty and shrinking, and share no rational at all.

The theorem is the rigorous form of bisection. To locate a number with some property, start with an interval that contains it, halve the interval, keep the half where the property still holds, and repeat. The lengths $\frac{b_{1} - a_{1}}{2^{n - 1}}$ shrink below any $ε$ , since $2^{n - 1} \geq n$ , so the theorem pins down exactly one point. The intermediate value theorem, that a continuous function negative at one end of an interval and positive at the other has a zero between, is proved this way, and the Calculus lesson on continuity uses the same halving to find roots numerically.

Is there a proof that

ℝ

is uncountable that avoids decimals?

Yes, and it is older than the diagonal argument. Let $x_{1}, x_{2}, x_{3}, \dots$ be any sequence of real numbers. We find a real number that is not in the list.

Start with $I_{0} = [0, 1]$ . Suppose a closed interval $I_{n - 1} = [a, b]$ with $a < b$ has been chosen. Cut it into three closed thirds, $[a, a + \frac{L}{3}]$ , $[a + \frac{L}{3}, a + \frac{2 L}{3}]$ and $[a + \frac{2 L}{3}, b]$ , where $L = b - a$ . The first and third thirds do not meet, so the number $x_{n}$ lies in at most two of the three. Let $I_{n}$ be a third that does not contain $x_{n}$ (the leftmost such, to make the choice definite). This defines closed intervals $I_{1} \supseteq I_{2} \supseteq I_{3} \supseteq \dots$ , each of positive length, with $x_{n} \notin I_{n}$ .

By the nested intervals theorem some $c$ lies in every $I_{n}$ . If $c = x_{n}$ for some $n$ , then $x_{n} = c \in I_{n}$ , contradicting the choice of $I_{n}$ . So $c$ differs from every $x_{n}$ , and no sequence lists every real number in $[0, 1]$ . Hence $[0, 1]$ , and with it $ℝ$ , is uncountable.

Cantor's first proof that the reals are uncountable, published in 1874, seventeen years before the diagonal argument, was built on nested intervals in this spirit. The argument shows where uncountability comes from. Run it in $ℚ$ , with a list of all the rationals (which exists, by the previous lesson), and every step works except the last: the nested intervals close in on a point, but the point is irrational, so the rational intervals have nothing in common. Countability of $ℚ$ and uncountability of $ℝ$ are two faces of the same fact, completeness.

Decimal expansions, and $0.999 \dots = 1$

The lesson on countability treated real numbers as infinite decimals and used, without proof, that every number in $(0, 1)$ has a decimal expansion and that $0.4999 \dots = 0.5$ . Both claims need a definition before they can be proved, because an infinite decimal is an infinite sum, and "add infinitely many numbers" has so far been given no meaning. Completeness gives it one.

Definition. For digits $d_{1}, d_{2}, d_{3}, \dots$ in ${0, 1, \dots, 9}$ , the decimal $0. d_{1} d_{2} d_{3} \dots$ denotes the real number

\sup {t_{n} : n \in ℕ}, where t_{n} = \frac{d_{1}}{10} + \frac{d_{2}}{10^{2}} + \dots + \frac{d_{n}}{10^{n}}

The finite decimal $t_{n}$ is the truncation after $n$ places. The supremum exists: the set is nonempty, and every $t_{n} \leq \frac{9}{10} + \dots + \frac{9}{10^{n}} = 1 - \frac{1}{10^{n}} < 1$ , the finite geometric sum being checked by induction. So every infinite decimal names a real number in $[0, 1]$ .

Theorem. $0.999 \dots = 1$ .

Proof. Here $t_{n} = 1 - \frac{1}{10^{n}}$ . Every $t_{n} < 1$ , so $1$ is an upper bound. Let $ε > 0$ . By the Archimedean property there is $n$ with $\frac{1}{n} < ε$ , and $10^{n} \geq n$ (by induction), so $\frac{1}{10^{n}} \leq \frac{1}{n} < ε$ and $t_{n} > 1 - ε$ . By the characterisation of the supremum, $\sup {t_{n}} = 1$ . $□$

The same computation gives $0.4999 \dots = 0.5$ : the truncations $0.4$ , $0.49$ , $0.499$ , and so on, are $t_{n} = \frac{1}{2} - \frac{1}{10^{n}}$ , all below $\frac{1}{2}$ and eventually above $\frac{1}{2} - ε$ for every $ε > 0$ .

Existence runs the other way: every number is the value of some decimal, and the floor function produces the digits.

Theorem. Every real $x$ with $0 \leq x < 1$ is the value of a decimal $0. d_{1} d_{2} d_{3} \dots$ , whose digits are given by $d_{n} = ⌊ 10^{n} x ⌋ - 10 ⌊ 10^{n - 1} x ⌋$ .

Proof. Write $N_{n} = ⌊ 10^{n} x ⌋$ for $n \geq 0$ , so $N_{0} = 0$ because $0 \leq x < 1$ . From $N_{n - 1} \leq 10^{n - 1} x < N_{n - 1} + 1$ , multiplying by $10$ ,

10 N_{n - 1} \leq 10^{n} x < 10 N_{n - 1} + 10

Since $10 N_{n - 1}$ is an integer at most $10^{n} x$ , and $N_{n}$ is the greatest such integer, $N_{n} \geq 10 N_{n - 1}$ ; and $N_{n} \leq 10^{n} x < 10 N_{n - 1} + 10$ gives $N_{n} \leq 10 N_{n - 1} + 9$ . So $d_{n} = N_{n} - 10 N_{n - 1}$ is one of $0, 1, \dots, 9$ . Dividing $d_{k} = N_{k} - 10 N_{k - 1}$ by $10^{k}$ and adding from $k = 1$ to $n$ , the sum telescopes:

t_{n} = \sum_{k = 1}^{n} \frac{d_{k}}{10^{k}} = \sum_{k = 1}^{n} (\frac{N_{k}}{10^{k}} - \frac{N_{k - 1}}{10^{k - 1}}) = \frac{N_{n}}{10^{n}} - N_{0} = \frac{N_{n}}{10^{n}}

By the definition of the floor, $N_{n} \leq 10^{n} x < N_{n} + 1$ , so $t_{n} \leq x < t_{n} + \frac{1}{10^{n}}$ . The first inequality makes $x$ an upper bound of the truncations. For $ε > 0$ , choose $n$ with $\frac{1}{10^{n}} < ε$ , as in the previous proof; then $t_{n} > x - \frac{1}{10^{n}} > x - ε$ . By the characterisation, $x = \sup {t_{n}} = 0. d_{1} d_{2} d_{3} \dots$ . $□$

For $x = \frac{3}{7}$ : $N_{1} = ⌊ \frac{30}{7} ⌋ = 4$ , $N_{2} = ⌊ \frac{300}{7} ⌋ = 42$ , $N_{3} = ⌊ \frac{3000}{7} ⌋ = 428$ , so the digits begin $4, 2, 8$ , and $\frac{3}{7} = 0.428 \dots$ , as long division says. The floor formula never produces a tail of $9$ s: its truncations satisfy $x < t_{n} + \frac{1}{10^{n}}$ strictly, which fails for the expansion $0.4999 \dots$ of $0.5$ at every $n$ , since there $t_{n} + \frac{1}{10^{n}} = \frac{1}{2}$ exactly. So the expansion it gives is the one that the diagonal argument chose, the one not ending in $9$ s.

0.999 \dots

not always just short of

1

The feeling comes from picturing $0.999 \dots$ as a process: nines being written one after another, the number creeping towards $1$ and never arriving. Every truncation is indeed short of $1$ , by exactly $\frac{1}{10^{n}}$ . But the decimal does not name any truncation, or a process. By definition it names one number, the least number that is at least every truncation, and the proof shows that number is $1$ .

Suppose someone insists that $0.999 \dots$ is a number $y$ strictly less than $1$ . Then $1 - y$ is positive, and the Archimedean property gives an $n$ with $\frac{1}{10^{n}} < 1 - y$ , so the truncation $t_{n} = 1 - \frac{1}{10^{n}}$ exceeds $y$ . Then $y$ is not even an upper bound of the truncations. The only way for a number to sit strictly between every truncation and $1$ is to be less than $1$ by an infinitesimal amount, and in $ℝ$ there are no infinitesimals. In a non-Archimedean field such as the one described earlier, the argument breaks down, which is the precise sense in which the intuition "just short of $1$ " is about a different number system.

Two popular arguments deserve a word. " $\frac{1}{3} = 0.333 \dots$ , and three times that is $0.999 \dots$ , so $0.999 \dots = 1$ " is correct in its conclusion, but as a proof it assumes that infinite decimals can be multiplied digit by digit, which needs its own justification from the definition. "Let $y = 0.999 \dots$ ; then $10 y = 9.999 \dots$ , and subtracting, $9 y = 9$ " assumes that multiplying by $10$ shifts digits and that infinite decimals can be subtracted term by term. Both steps are true, and both follow from the supremum definition (the problem sheet proves the first kind of fact), but they are theorems, not rules of notation. The supremum proof above needs only the definition and the Archimedean property.

Two expansions for one number is not a defect peculiar to base ten. In every base $b \geq 2$ , a number with a terminating expansion also has one ending in an endless run of the digit $b - 1$ ; in binary, $0.0111 \dots = 0.1$ . It is the price of describing a complete line with a countable string of digits.

Where completeness is needed next

The Archimedean property, the floor, density, square roots, nested intervals and decimal expansions are facts calculus uses without comment, and each came from one axiom. The rest of analysis leans on it too. The next lesson writes convergence of a sequence with $ε$ and $N$ and proves the monotone convergence theorem: in $ℝ$ , every bounded increasing sequence converges, to the supremum of its terms. That is the theorem Dedekind could not prove in 1858, and the decimal truncations of $\sqrt{2}$ , rational, increasing, bounded by $2$ and with no rational limit, show that in $ℚ$ it is false.

In any ordered field, three properties are equivalent: the least upper bound property; the monotone convergence theorem; and the nested intervals theorem together with the Archimedean property. So a course may take any of them as its axiom; this one took the least upper bound, because it is the easiest to state and the one the rationals most visibly lack. The problem sheet proves one of the equivalences.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution. Throughout, "the characterisation" means the $ε$ form of the supremum or infimum proved in the lesson.

Warm-up

1. Find the supremum and infimum of each set, and say whether each is a maximum or minimum: (a) $[- 2, 3)$ ; (b) ${x \in ℝ : x^{2} \leq 5}$ ; (c) ${\frac{n}{n + 1} : n \in ℕ}$ .

Solution

(a) Every $x$ in the set satisfies $- 2 \leq x$ , and $- 2$ is in the set, so $\inf = \min = - 2$ . Every $x$ satisfies $x < 3$ , so $3$ is an upper bound. Let $ε > 0$ , and let $x$ be the larger of $0$ and $3 - \frac{ε}{2}$ . Then $0 \leq x < 3$ , so $x$ is in the set, and $x \geq 3 - \frac{ε}{2} > 3 - ε$ . By the characterisation, $\sup = 3$ . It is not a maximum, since $3$ is not in the set.

(b) For $x \geq 0$ , squaring preserves order on non-negative numbers, so $x^{2} \leq 5$ exactly when $x \leq \sqrt{5}$ . For $x < 0$ , $x^{2} = (- x)^{2}$ , so $x^{2} \leq 5$ exactly when $- x \leq \sqrt{5}$ , that is, $x \geq - \sqrt{5}$ . So the set is $[- \sqrt{5}, \sqrt{5}]$ , with $\sup = \max = \sqrt{5}$ and $\inf = \min = - \sqrt{5}$ . (Both exist as real numbers by the theorem on square roots.)

(c) Write $\frac{n}{n + 1} = 1 - \frac{1}{n + 1}$ . For $n \geq 1$ , $\frac{1}{n + 1} \leq \frac{1}{2}$ , so every element is at least $\frac{1}{2}$ , the element at $n = 1$ . So $\inf = \min = \frac{1}{2}$ . Every element is less than $1$ , so $1$ is an upper bound, and it is not attained. Let $ε > 0$ and choose $n \in ℕ$ with $\frac{1}{n} < ε$ . Then $\frac{1}{n + 1} < \frac{1}{n} < ε$ , so the element $1 - \frac{1}{n + 1}$ exceeds $1 - ε$ . By the characterisation, $\sup = 1$ , not a maximum.

2. Using the ordered field axioms and the lemma in the lesson, prove that for all $x$ and $y$ in an ordered field: (a) if $x < y$ then $x + z < y + z$ for every $z$ ; (b) if $x < y$ then $- y < - x$ ; (c) if $x < y$ then $x < \frac{x + y}{2} < y$ .

Solution

(a) Let $x < y$ and let $z$ be any element. By (O1), $x + z \leq y + z$ . If $x + z = y + z$ , adding $- z$ to both sides gives $x = y$ , which is false. So $x + z < y + z$ .

(b) By (a), adding $- x - y$ to both sides of $x < y$ gives $- y < - x$ .

(c) By (a), adding $x$ to both sides of $x < y$ gives $2 x < x + y$ , and adding $y$ gives $x + y < 2 y$ , where $2 = 1 + 1$ . Now $2 > 0$ , since $1 > 0$ (the Example) and $1 + 1 > 0 + 1 = 1 > 0$ by (a). So $\frac{1}{2} > 0$ by the Now you after the Example. Multiplying $2 x < x + y < 2 y$ by the positive element $\frac{1}{2}$ keeps both inequalities, by part (vi) of the lemma, and gives $x < \frac{x + y}{2} < y$ .

Part (c) shows that between two elements of an ordered field there is always a third, so no ordered field has "next" elements. Density of $ℚ$ in $ℝ$ says more: the element in between can be chosen rational.

3. Let $A$ be a nonempty bounded set of real numbers. Prove that $\inf A \leq \sup A$ , with equality if and only if $A$ has exactly one element.

Solution

Since $A$ is nonempty, choose $a \in A$ . Then $\inf A \leq a$ , because the infimum is a lower bound, and $a \leq \sup A$ , because the supremum is an upper bound. So $\inf A \leq \sup A$ .

If $A = {a}$ , then $a$ is both the maximum and the minimum, so $\inf A = a = \sup A$ . Conversely, suppose $\inf A = \sup A = c$ . Every $a \in A$ satisfies $c \leq a \leq c$ , so $a = c$ by antisymmetry. So every element of $A$ equals $c$ , and since $A$ is nonempty, $A = {c}$ .

4. (a) Find $⌊ - 3.5 ⌋$ , $⌊ - 3 ⌋$ and $⌊ \frac{22}{7} ⌋$ . (b) Use the formula $d_{n} = ⌊ 10^{n} x ⌋ - 10 ⌊ 10^{n - 1} x ⌋$ to find the first four decimal digits of $\frac{5}{7}$ .

Solution

(a) $⌊ - 3.5 ⌋ = - 4$ , since $- 4 \leq - 3.5 < - 3$ . $⌊ - 3 ⌋ = - 3$ , since $- 3 \leq - 3 < - 2$ . $⌊ \frac{22}{7} ⌋ = 3$ , since $21 \leq 22 < 28$ gives $3 \leq \frac{22}{7} < 4$ .

(b) Write $N_{n} = ⌊ 10^{n} \cdot \frac{5}{7} ⌋$ . Since $7 \times 7 = 49 \leq 50 < 56$ , $N_{1} = 7$ . Since $7 \times 71 = 497 \leq 500 < 504$ , $N_{2} = 71$ . Since $7 \times 714 = 4998 \leq 5000 < 5005$ , $N_{3} = 714$ . Since $7 \times 7142 = 49 994 \leq 50 000 < 50 001$ , $N_{4} = 7142$ . With $N_{0} = 0$ , the digits are $d_{1} = 7$ , $d_{2} = 71 - 70 = 1$ , $d_{3} = 714 - 710 = 4$ , $d_{4} = 7142 - 7140 = 2$ . So $\frac{5}{7} = 0.7142 \dots$

Core

5. Let $A$ and $B$ be nonempty sets of reals, both bounded above, and let $A + B = {a + b : a \in A, b \in B}$ . Prove that $\sup (A + B) = \sup A + \sup B$ .

Hint

Use the characterisation, and split the tolerance: find $a$ within $\frac{ε}{2}$ of $\sup A$ and $b$ within $\frac{ε}{2}$ of $\sup B$ .

Solution

Let $s = \sup A$ and $t = \sup B$ . The set $A + B$ is nonempty, since $A$ and $B$ are.

Upper bound. Every element of $A + B$ is $a + b$ with $a \in A$ and $b \in B$ . Then $a \leq s$ and $b \leq t$ , and adding these inequalities gives $a + b \leq s + t$ . So $s + t$ is an upper bound of $A + B$ .

Nothing smaller. Let $ε > 0$ . By the characterisation applied to $A$ with tolerance $\frac{ε}{2}$ , some $a \in A$ has $a > s - \frac{ε}{2}$ , and likewise some $b \in B$ has $b > t - \frac{ε}{2}$ . Then $a + b \in A + B$ and $a + b > s + t - ε$ .

By the characterisation, $\sup (A + B) = s + t$ . Taking $B = {c}$ gives the special case $\sup (A + c) = \sup A + c$ , where $A + c = {a + c : a \in A}$ .

6. Let $A$ be a nonempty bounded set of reals, $c$ a real number, and $c A = {c a : a \in A}$ . Prove that if $c > 0$ then $\sup (c A) = c \sup A$ , and that if $c < 0$ then $\sup (c A) = c \inf A$ .

Hint

Multiplying by a positive number keeps inequalities and multiplying by a negative one reverses them. For $c < 0$ , a lower bound of $A$ turns into an upper bound of $c A$ .

Solution

Case $c > 0$ . Let $s = \sup A$ . For every $a \in A$ , $a \leq s$ , so $c a \leq c s$ ; thus $c s$ is an upper bound of $c A$ , which is nonempty. Let $ε > 0$ . Then $\frac{ε}{c} > 0$ , so some $a \in A$ has $a > s - \frac{ε}{c}$ , and multiplying by $c > 0$ gives $c a > c s - ε$ . By the characterisation, $\sup (c A) = c s$ .

Case $c < 0$ . Let $t = \inf A$ , which exists because $A$ is nonempty and bounded below. For every $a \in A$ , $a \geq t$ , and multiplying by the negative number $c$ reverses this: $c a \leq c t$ . So $c t$ is an upper bound of $c A$ . Let $ε > 0$ . Then $- c > 0$ , so $\frac{ε}{- c} > 0$ , and by the characterisation of the infimum some $a \in A$ has $a < t + \frac{ε}{- c}$ . Multiplying by $c < 0$ reverses the inequality: $c a > c t + c \cdot \frac{ε}{- c} = c t - ε$ . By the characterisation, $\sup (c A) = c t$ .

With $c = - 1$ the second case says $\sup (- A) = - \inf A$ , the proposition on infima read backwards.

7. Find the flaw in this proof, show that the claim is false, and state and prove the correct version.

Claim. Let $A$ and $B$ be nonempty sets of reals such that $a < b$ for every $a \in A$ and every $b \in B$ . Then $\sup A < \inf B$ .

Proof. Both exist, since $A$ is bounded above by any element of $B$ and $B$ is bounded below by any element of $A$ . Since $a < b$ for all $a$ and $b$ , taking the supremum over $a \in A$ and then the infimum over $b \in B$ gives $\sup A < \inf B$ .

Hint

The first sentence is fine. Look at $A = (0, 1)$ and $B = (1, 2)$ .

Solution

The flaw is in the last step: strict inequalities are not preserved by taking suprema or infima. From " $a < b$ for every $a \in A$ " it follows only that $b$ is an upper bound of $A$ , so $\sup A \leq b$ , with $\leq$ and not $<$ . The set $[0, 1)$ has every element below $1$ and supremum equal to $1$ .

The claim is false. Take $A = (0, 1)$ and $B = (1, 2)$ . Every element of $A$ is less than $1$ , and every element of $B$ is greater than $1$ , so $a < b$ for all $a \in A$ and $b \in B$ . But $\sup A = 1$ and $\inf B = 1$ (the first as in the lesson on order; the second by the mirror argument: $1$ is a lower bound, and for $ε > 0$ the smaller of $1 + \frac{ε}{2}$ and $\frac{3}{2}$ lies in $B$ and is less than $1 + ε$ ). So $\sup A = \inf B$ , and $\sup A < \inf B$ fails.

Correct claim. If $A$ and $B$ are nonempty and $a \leq b$ for every $a \in A$ and $b \in B$ (in particular if $a < b$ ), then $\sup A \leq \inf B$ .

Proof. Let $b \in B$ . Every $a \in A$ satisfies $a \leq b$ , so $b$ is an upper bound of $A$ , and $A$ has a supremum with $\sup A \leq b$ . This holds for every $b \in B$ , so $\sup A$ is a lower bound of $B$ , and $B$ has an infimum with $\sup A \leq \inf B$ , because the infimum is the greatest lower bound. $□$

8. Prove or disprove each claim. (a) If $x$ is rational and $y$ is irrational, then $x + y$ is irrational. (b) If $x$ and $y$ are irrational, then $x + y$ is irrational. (c) If $x$ is a nonzero rational and $y$ is irrational, then $x y$ is irrational. (d) If $x$ and $y$ are irrational, then $x y$ is irrational. (e) If $x^{2}$ is irrational, then $x$ is irrational.

Hint

Two are false, with counterexamples built from $\sqrt{2}$ . The true ones go by contradiction or contrapositive, using that $ℚ$ is closed under the four operations.

Solution

(a) True; this and (c) were proved in the lesson on contradiction. Suppose $x$ is rational, $y$ irrational, and $x + y = r$ is rational. Then $y = r - x$ is a difference of rationals, hence rational, a contradiction.

(b) False. $\sqrt{2}$ is irrational, and so is $- \sqrt{2}$ by (c) with $x = - 1$ . Their sum is $0$ , which is rational.

(c) True. Suppose $x \neq 0$ is rational, $y$ irrational, and $x y = r$ is rational. Then $y = \frac{r}{x}$ is a quotient of rationals with nonzero denominator, hence rational, a contradiction.

(d) False. $\sqrt{2} \cdot \sqrt{2} = 2$ , which is rational.

(e) True, by the contrapositive: if $x$ is rational, $x = \frac{p}{q}$ , then $x^{2} = \frac{p^{2}}{q^{2}}$ is rational. The converse fails: $\sqrt{2}$ is irrational and its square is rational.

9. Prove that there is exactly one positive real number $s$ with $s^{3} = 2$ .

Hint

Follow the proof for square roots with $S = {x \geq 0 : x^{3} < 2}$ . To push up: for $0 < h < 1$ , $(s + h)^{3} < s^{3} + h (3 s^{2} + 3 s + 1)$ . To push down: try $k = \frac{s^{3} - 2}{3 s^{2}}$ .

Solution

First a fact used twice: for $0 \leq x < y$ , $x^{3} < y^{3}$ . Indeed $y^{3} - x^{3} = (y - x) (y^{2} + x y + x^{2})$ , with $y - x > 0$ and $y^{2} + x y + x^{2} \geq y^{2} > 0$ .

Let $S = {x \in ℝ : x \geq 0 and x^{3} < 2}$ . It contains $1$ , so it is nonempty. It is bounded above by $2$ : if $x \geq 2$ then $x^{3} \geq 8 > 2$ by the fact. By completeness it has a supremum $s$ , and $s \geq 1$ .

Suppose $s^{3} < 2$ . Let $h$ be the smaller of $\frac{1}{2}$ and $\frac{2 - s^{3}}{3 s^{2} + 3 s + 1}$ . Then $0 < h < 1$ , so $h^{2} < h$ and $h^{3} < h$ , and since $s > 0$ ,

(s + h)^{3} = s^{3} + 3 s^{2} h + 3 s h^{2} + h^{3} < s^{3} + 3 s^{2} h + 3 s h + h = s^{3} + h (3 s^{2} + 3 s + 1) \leq 2

So $s + h \in S$ and $s + h > s$ , contradicting that $s$ is an upper bound.

Suppose $s^{3} > 2$ . Let $k = \frac{s^{3} - 2}{3 s^{2}} > 0$ . Then $s - k = \frac{2 s^{3} + 2}{3 s^{2}} > 0$ , so $0 < k < s$ . Now

(s - k)^{3} = s^{3} - 3 s^{2} k + 3 s k^{2} - k^{3} = s^{3} - 3 s^{2} k + k^{2} (3 s - k) > s^{3} - 3 s^{2} k = 2

because $k^{2} > 0$ and $3 s - k > 2 s > 0$ . If some $x \in S$ had $x \geq s - k$ , the fact would give $x^{3} \geq (s - k)^{3} > 2$ , contradicting $x \in S$ . So $s - k$ is an upper bound smaller than $s$ , contradicting that $s$ is the least.

By trichotomy $s^{3} = 2$ , and $s > 0$ . For uniqueness, if $t > 0$ and $t \neq s$ , then either $t < s$ or $s < t$ , and the fact gives $t^{3} < 2$ or $t^{3} > 2$ . So $s$ is the only positive cube root of $2$ .

10. (a) Prove that if $a$ and $b$ are real numbers with $a \leq b + ε$ for every $ε > 0$ , then $a \leq b$ . (b) Prove that if $x \geq 0$ and $x \leq \frac{1}{n}$ for every $n \in ℕ$ , then $x = 0$ . (c) Deduce that if $| x - y | < \frac{1}{n}$ for every $n \in ℕ$ , then $x = y$ .

Hint

For (a), argue by contradiction and choose $ε$ to fit. For (b), which property of $ℝ$ is being used?

Solution

(a) Suppose $a > b$ . Take $ε = \frac{a - b}{2} > 0$ . By hypothesis $a \leq b + \frac{a - b}{2} = \frac{a + b}{2}$ , which gives $2 a \leq a + b$ , so $a \leq b$ , a contradiction. Hence $a \leq b$ .

(b) Let $x \geq 0$ with $x \leq \frac{1}{n}$ for all $n$ . Suppose $x > 0$ . By the Archimedean property there is $n \in ℕ$ with $\frac{1}{n} < x$ , contradicting the hypothesis. So $x = 0$ . This is exactly where the Archimedean property is used; in an ordered field with infinitesimals, a positive infinitesimal would satisfy the hypothesis.

(c) Let $x$ and $y$ satisfy the hypothesis. Then $| x - y | \geq 0$ and $| x - y | < \frac{1}{n}$ for every $n$ , so by (b), $| x - y | = 0$ , and $x = y$ .

Part (a) is the standard way analysts prove an inequality: show that it holds up to an arbitrary positive error. Part (c) is the same idea for equality, and the next lesson's proof that a limit is unique runs on it.

Challenge

11. Let $F$ be an ordered field with the Archimedean property (for every $x \in F$ some $n \in ℕ$ has $n > x$ ), in which the nested intervals theorem holds. Prove that $F$ is complete: every nonempty subset of $F$ that is bounded above has a least upper bound.

Hint

Bisect. Start with an element $a_{1}$ that is not an upper bound and an element $b_{1}$ that is. At each step look at the midpoint, and keep the half whose left end is not an upper bound and whose right end is. The common point of the intervals is the candidate.

Solution

Let $A \subseteq F$ be nonempty and bounded above. Choose $a \in A$ and put $a_{1} = a - 1$ , which is not an upper bound of $A$ since $a > a_{1}$ , and let $b_{1}$ be any upper bound. Then $a_{1} < b_{1}$ .

Given $a_{n} < b_{n}$ with $a_{n}$ not an upper bound and $b_{n}$ an upper bound, let $m = \frac{a_{n} + b_{n}}{2}$ , so $a_{n} < m < b_{n}$ (Problem 2). If $m$ is an upper bound of $A$ , put $a_{n + 1} = a_{n}$ and $b_{n + 1} = m$ ; otherwise put $a_{n + 1} = m$ and $b_{n + 1} = b_{n}$ . Either way $[a_{n + 1}, b_{n + 1}] \subseteq [a_{n}, b_{n}]$ , $a_{n + 1}$ is not an upper bound, $b_{n + 1}$ is one, and $b_{n + 1} - a_{n + 1} = \frac{b_{n} - a_{n}}{2}$ . By induction, $b_{n} - a_{n} = \frac{L}{2^{n - 1}}$ with $L = b_{1} - a_{1} > 0$ .

The lengths become small: given $ε > 0$ , the Archimedean property gives $n$ with $n > \frac{L}{ε}$ , and $2^{n - 1} \geq n$ (by induction), so $b_{n} - a_{n} = \frac{L}{2^{n - 1}} \leq \frac{L}{n} < ε$ . By the nested intervals theorem, there is $c$ with $a_{n} \leq c \leq b_{n}$ for every $n$ .

$c$ is an upper bound of $A$ . Suppose some $x \in A$ has $x > c$ . Choose $n$ with $b_{n} - a_{n} < x - c$ . Then $b_{n} < a_{n} + (x - c) \leq c + (x - c) = x$ , so $b_{n}$ is not an upper bound of $A$ , a contradiction.

No upper bound is smaller than $c$ . Suppose $v$ is an upper bound with $v < c$ . Choose $n$ with $b_{n} - a_{n} < c - v$ . Then $a_{n} > b_{n} - (c - v) \geq c - (c - v) = v$ . Any element above an upper bound is an upper bound, so $a_{n}$ is an upper bound of $A$ , a contradiction.

Hence $c = \sup A$ , and $F$ is complete. The Archimedean hypothesis cannot be dropped: there are non-Archimedean ordered fields in which every nested sequence of closed intervals has a common point, and they are not complete, since by the lesson every complete ordered field is Archimedean. (The larger fields of Robinson's non-standard analysis are examples.)

12. Prove that the set ${m + n \sqrt{2} : m, n \in ℤ}$ is dense in $ℝ$ : every interval $(a, b)$ with $a < b$ contains an element of it.

Hint

First find an element $z$ of the set with $0 < z < b - a$ . For that, look at the fractional parts $k \sqrt{2} - ⌊ k \sqrt{2} ⌋$ for $k = 0, 1, \dots, N$ , and use the pigeonhole principle on $N$ subintervals of $[0, 1)$ . Then use the multiples of $z$ as a ruler, as in the density of the rationals.

Solution

Write $G = {m + n \sqrt{2} : m, n \in ℤ}$ . It is closed under addition, subtraction and multiplication by integers.

Step 1: small positive elements. Let $N \in ℕ$ . For $k = 0, 1, \dots, N$ , let $f_{k} = k \sqrt{2} - ⌊ k \sqrt{2} ⌋$ , the fractional part, so $0 \leq f_{k} < 1$ and $f_{k} \in G$ . Split $[0, 1)$ into the $N$ intervals $[\frac{j}{N}, \frac{j + 1}{N})$ for $j = 0, \dots, N - 1$ . There are $N + 1$ numbers $f_{k}$ and $N$ intervals, so by the pigeonhole principle two of them, $f_{k}$ and $f_{l}$ with $k < l$ , lie in the same interval, and $| f_{l} - f_{k} | < \frac{1}{N}$ . Now $f_{l} - f_{k} = (l - k) \sqrt{2} - (⌊ l \sqrt{2} ⌋ - ⌊ k \sqrt{2} ⌋)$ is in $G$ , and it is not $0$ : otherwise $\sqrt{2} = \frac{⌊ l \sqrt{2} ⌋ - ⌊ k \sqrt{2} ⌋}{l - k}$ would be rational. So $z = | f_{l} - f_{k} |$ (which is $f_{l} - f_{k}$ or its negative, both in $G$ ) is an element of $G$ with $0 < z < \frac{1}{N}$ .

Step 2: the ruler. Let $a < b$ . Choose $N$ with $\frac{1}{N} < b - a$ , and $z \in G$ with $0 < z < \frac{1}{N}$ by Step 1. Let $j = ⌊ \frac{a}{z} ⌋ + 1$ , an integer. Then $j - 1 \leq \frac{a}{z} < j$ , and multiplying by $z > 0$ gives $j z - z \leq a < j z$ . Hence $a < j z \leq a + z < a + (b - a) = b$ . And $j z \in G$ , being an integer multiple of an element of $G$ . So $(a, b)$ contains the element $j z$ of $G$ .

The same argument works with any irrational in place of $\sqrt{2}$ . For a rational $\frac{p}{q}$ it fails, since then every $m + n \frac{p}{q}$ is a multiple of $\frac{1}{q}$ and the set has gaps of length $\frac{1}{q}$ . Step 1 is a form of Dirichlet's approximation theorem: for every irrational $α$ and every $N$ there are integers $l > 0$ and $m$ with $| l α - m | < \frac{1}{N}$ and $l \leq N$ .

13. Call a decimal $0. d_{1} d_{2} d_{3} \dots$ eventually periodic if there are $k \geq 0$ and $p \geq 1$ with $d_{n + p} = d_{n}$ for every $n > k$ . Prove that a real number $x \in [0, 1)$ is rational if and only if the decimal expansion given by the floor formula is eventually periodic.

Hint

( $\Leftarrow$ ) First prove that $10^{m} \cdot 0. d_{1} d_{2} \dots = D + 0. d_{m + 1} d_{m + 2} \dots$ where $D$ is the integer with digits $d_{1} \dots d_{m}$ , using Problems 5 and 6. Then compare $10^{k + p} x$ and $10^{k} x$ . ( $\Rightarrow$ ) For $x = \frac{a}{b}$ , the remainders $r_{n} = 10^{n} a - b N_{n}$ , with $N_{n} = ⌊ 10^{n} x ⌋$ , lie in ${0, \dots, b - 1}$ , and each determines the next digit and the next remainder.

Solution

( $\Leftarrow$ ) A shifting lemma. Let $y = 0. d_{1} d_{2} d_{3} \dots$ with truncations $t_{n}$ , let $m \geq 0$ , let $D = \sum_{j = 1}^{m} d_{j} 10^{m - j}$ (an integer), and let $y' = 0. d_{m + 1} d_{m + 2} \dots$ with truncations $t_{n}'$ . We claim $10^{m} y = D + y'$ . The truncations increase, $t_{1} \leq t_{2} \leq \dots$ , so every $t_{n}$ with $n \leq m$ is at most $t_{m + 1}$ , and $y = \sup {t_{n} : n > m}$ . For $n > m$ , multiplying out gives $10^{m} t_{n} = D + t_{n - m}'$ . By Problem 6 with $c = 10^{m}$ , and Problem 5 with $B = {D}$ ,

10^{m} y = \sup {10^{m} t_{n} : n > m} = \sup {D + t_{j}' : j \in ℕ} = D + \sup {t_{j}'} = D + y'

Periodic implies rational. Suppose $x = 0. d_{1} d_{2} \dots$ with $d_{n + p} = d_{n}$ for all $n > k$ . The tails $0. d_{k + 1} d_{k + 2} \dots$ and $0. d_{k + p + 1} d_{k + p + 2} \dots$ have the same digits in every place, so they are the same number $y'$ . By the lemma, $10^{k} x = D_{1} + y'$ and $10^{k + p} x = D_{2} + y'$ for integers $D_{1}$ and $D_{2}$ . Subtracting, $(10^{k + p} - 10^{k}) x = D_{2} - D_{1}$ , and $10^{k + p} - 10^{k} > 0$ , so $x = \frac{D_{2} - D_{1}}{10^{k} (10^{p} - 1)}$ is rational.

( $\Rightarrow$ ) Let $x = \frac{a}{b}$ with integers $0 \leq a < b$ . Let $N_{n} = ⌊ 10^{n} x ⌋$ and $r_{n} = 10^{n} a - b N_{n}$ , an integer. From $N_{n} \leq \frac{10^{n} a}{b} < N_{n} + 1$ , multiplying by $b > 0$ gives $0 \leq r_{n} < b$ . The digits are $d_{n} = N_{n} - 10 N_{n - 1}$ , and

10 r_{n - 1} = 10^{n} a - 10 b N_{n - 1} = b (N_{n} - 10 N_{n - 1}) + (10^{n} a - b N_{n}) = b d_{n} + r_{n}

with $0 \leq r_{n} < b$ . By the uniqueness in the division algorithm, $d_{n}$ and $r_{n}$ are the quotient and remainder of $10 r_{n - 1}$ on division by $b$ , so both are determined by $r_{n - 1}$ alone.

The $b + 1$ remainders $r_{0}, r_{1}, \dots, r_{b}$ take at most $b$ values, so by the pigeonhole principle $r_{k} = r_{k + p}$ for some $k \geq 0$ and $p \geq 1$ . Then $d_{k + 1} = d_{k + p + 1}$ and $r_{k + 1} = r_{k + p + 1}$ , and by induction $d_{n} = d_{n + p}$ and $r_{n} = r_{n + p}$ for every $n > k$ . So the expansion is eventually periodic.

For $\frac{3}{7}$ , the remainders are $r_{0} = 3$ , then $30 = 7 \times 4 + 2$ , $20 = 7 \times 2 + 6$ , $60 = 7 \times 8 + 4$ , $40 = 7 \times 5 + 5$ , $50 = 7 \times 7 + 1$ , $10 = 7 \times 1 + 3$ , back to $3$ . So $\frac{3}{7} = 0.428571428571 \dots$ , with period $6$ . The proof also shows the period is at most $b$ , and in fact at most $b - 1$ when no remainder is $0$ .