The function \(f(x)=x^2-2\) is negative at \(x=1\) and positive at \(x=2\) . Its graph is an unbroken curve, so it must cross the axis somewhere between. That sentence is the Intermediate Value Theorem in miniature, and it is false for the rational numbers. If \(x\) is only allowed to be rational, then \(f\) is still negative at \(1\) , still positive at \(2\) , still given by the same formula, and it never takes the value \(0\) , because no rational number has square \(2\) .
So whatever makes the theorems of calculus true is not arithmetic and is not the ordering of numbers, since the rationals have both. It is a further property that the real numbers have and the rationals lack. This chapter isolates that property, the existence of least upper bounds, and draws its first consequences. Every later chapter leans on it: the convergence of bounded monotone sequences, the existence of maxima, the Mean Value Theorem, and the existence of the integral are all least upper bounds in disguise.
1.1 What the rationals already have
Definition 1.1 (ordered field). A field is a set \(F\) with two operations, addition and multiplication, that are commutative and associative, have identity elements \(0\ne 1\) , admit negatives \(-x\) and reciprocals \(1/x\) for \(x\ne 0\) , and are linked by the distributive law \(x(y+z)=xy+xz\) . An ordered field is a field with a relation \(<\) such that: (O1) for all \(x,y\in F\) exactly one of \(x<y\) , \(x=y\) , \(y<x\) holds; (O2) if \(x<y\) and \(y<z\) , then \(x<z\) ; (O3) if \(x<y\) , then \(x+z<y+z\) for every \(z\) ; (O4) if \(x<y\) and \(0<z\) , then \(xz<yz\) . We write \(x\le y\) to mean \(x<y\) or \(x=y\) .
Both \(\mathbb Q\) and \(\mathbb R\) are ordered fields. All the familiar rules for manipulating inequalities follow from (O1) to (O4): a square is never negative, \(0<1\) , multiplying an inequality by a negative number reverses it, \(0<x<y\) implies \(0<1/y<1/x\) , and \(0<x<y\) implies \(x^2<y^2\) . We use these rules freely; Exercise 2 asks you to derive the last of them.
The rationals are not enough, and the Greeks knew it.
Theorem 1.2 (no rational square root of two). There is no rational number \(r\) with \(r^2=2\) .
Proof. Suppose there were. Write \(r=p/q\) with \(p,q\) integers, \(q\ne 0\) , and with the fraction in lowest terms, so that \(p\) and \(q\) have no common factor larger than \(1\) . Then \(p^2=2q^2\) , so \(p^2\) is even. The square of an odd integer is odd, so \(p\) itself is even; write \(p=2k\) . Then \(4k^2=2q^2\) , so \(q^2=2k^2\) is even and \(q\) is even as well. Now \(2\) divides both \(p\) and \(q\) , which contradicts the choice of lowest terms.
The proof uses nothing about size. It is pure divisibility, and it leaves open the question of whether any number has square \(2\) . To discuss that we need to measure distance.
Definition 1.3 (absolute value). For \(x\in\mathbb R\) , the absolute value \(\lvert x\rvert\) equals \(x\) if \(x\ge 0\) and \(-x\) if \(x<0\) . The distance between \(x\) and \(y\) is \(\lvert x-y\rvert\) .
Directly from the definition, \(\lvert x\rvert\ge 0\) , \(\lvert xy\rvert=\lvert x\rvert\lvert y\rvert\) , \(-\lvert x\rvert\le x\le\lvert x\rvert\) , and for \(c\ge 0\) the inequality \(\lvert x\rvert\le c\) holds exactly when \(-c\le x\le c\) .
Proposition 1.4 (triangle inequality). For all real \(x\) and \(y\) ,
Proof. Add the inequalities \(-\lvert x\rvert\le x\le\lvert x\rvert\) and \(-\lvert y\rvert\le y\le\lvert y\rvert\) to get \(-(\lvert x\rvert+\lvert y\rvert)\le x+y\le\lvert x\rvert+\lvert y\rvert\) , which is the first claim. For the second, apply the first to \(x=(x-y)+y\) : \(\lvert x\rvert\le\lvert x-y\rvert+\lvert y\rvert\) , so \(\lvert x\rvert-\lvert y\rvert\le\lvert x-y\rvert\) . Exchanging the roles of \(x\) and \(y\) gives \(\lvert y\rvert-\lvert x\rvert\le\lvert x-y\rvert\) . The two together say that \(\lvert x\rvert-\lvert y\rvert\) lies between \(-\lvert x-y\rvert\) and \(\lvert x-y\rvert\) .
The triangle inequality is the most used tool in the book. Its typical application inserts an intermediate point: to show that \(a\) is close to \(c\) , show that \(a\) is close to \(b\) and \(b\) is close to \(c\) , and write \(\lvert a-c\rvert\le\lvert a-b\rvert+\lvert b-c\rvert\) .
1.2 Upper bounds and the least of them
Definition 1.5 (bounds, maximum, supremum). Let \(S\subseteq\mathbb R\) . A number \(u\) is an upper bound of \(S\) if \(x\le u\) for every \(x\in S\) ; if such a \(u\) exists, \(S\) is bounded above. A maximum of \(S\) is an upper bound of \(S\) that belongs to \(S\) . A number \(s\) is the supremum of \(S\) , written \(s=\sup S\) , if (i) \(s\) is an upper bound of \(S\) , and (ii) \(s\le u\) for every upper bound \(u\) of \(S\) . Lower bound, bounded below, minimum, and infimum (\(\inf S\) , the greatest lower bound) are defined by reversing the inequalities. A set is bounded if it is bounded above and below.
A set has at most one supremum: if \(s\) and \(s'\) both satisfy (i) and (ii), then \(s\le s'\) because \(s'\) is an upper bound, and \(s'\le s\) for the same reason. A maximum, when it exists, is the supremum, since any upper bound is at least as large as an element of the set. The converse is the important point: a supremum need not be a maximum. The interval \((0,1)\) has supremum \(1\) and no maximum at all.
Condition (ii) is awkward to verify directly because it speaks about all upper bounds. The following restatement speaks about elements of the set, and it is the form used in almost every proof.
Lemma 1.6 (approximation property of the supremum). Let \(S\) be a nonempty set of real numbers and let \(s\) be an upper bound of \(S\) . Then \(s=\sup S\) if and only if for every \(\varepsilon>0\) there is an element \(x\in S\) with \(x>s-\varepsilon\) .
Proof. Suppose \(s=\sup S\) and let \(\varepsilon>0\) . Since \(s-\varepsilon<s\) , the number \(s-\varepsilon\) is not an upper bound of \(S\) , by (ii). So some \(x\in S\) exceeds it. Conversely, suppose the approximation condition holds and let \(u\) be any upper bound of \(S\) . If \(u<s\) , put \(\varepsilon=s-u>0\) ; the condition gives \(x\in S\) with \(x>s-\varepsilon=u\) , contradicting that \(u\) is an upper bound. Hence \(s\le u\) , which is (ii).
In words: the supremum is an upper bound that elements of the set come arbitrarily close to. The matching statement for the infimum is that \(t=\inf S\) exactly when \(t\) is a lower bound and every \(t+\varepsilon\) exceeds some element of \(S\) .
Example 1.1: A supremum that is not attained
Let \(S=\{n/(n+1):n\in\mathbb N\}=\{1/2,\,2/3,\,3/4,\dots\}\) . We claim \(\sup S=1\) and \(\inf S=1/2\) .
Every element satisfies \(n/(n+1)<1\) , so \(1\) is an upper bound. To apply Lemma 1.6, let \(\varepsilon>0\) . We need an \(n\) with \(n/(n+1)>1-\varepsilon\) . Since \(n/(n+1)=1-1/(n+1)\) , this is the requirement \(1/(n+1)<\varepsilon\) , that is, \(n>1/\varepsilon-1\) . Such a natural number exists (this innocent remark is the Archimedean property, proved in Theorem 1.9). For instance, with \(\varepsilon=0.01\) the requirement is \(n>99\) , and \(n=100\) gives \(100/101\approx 0.990099>0.99\) . So \(\sup S=1\) . Because no element equals \(1\) , the set has no maximum.
For the infimum, \(n/(n+1)=1-1/(n+1)\ge 1-1/2=1/2\) for every \(n\ge 1\) , and the value \(1/2\) is taken at \(n=1\) . So \(1/2\) is a lower bound that belongs to the set: it is the minimum, hence the infimum.
Common mistake. Treating \(\sup S\) as an element of \(S\) . An argument that begins “let \(s=\sup S\) ; since \(s\in S\) …” has assumed that \(S\) has a maximum. What is always available is weaker and usually sufficient: elements of \(S\) within any prescribed \(\varepsilon\) of \(s\) . Check membership separately; it is a different question from the order property.
1.3 The completeness axiom
Definition 1.7 (completeness). An ordered field \(F\) is complete if every nonempty subset of \(F\) that is bounded above has a supremum in \(F\) . The real numbers \(\mathbb R\) are a complete ordered field containing \(\mathbb Q\) .
This is the property we were looking for. Two things should be said about its status. First, in this book it is an axiom about \(\mathbb R\) : we do not construct the real numbers. They can be constructed from the rationals, by Dedekind cuts or by equivalence classes of Cauchy sequences, and one can prove that any two complete ordered fields are the same up to relabelling; either construction takes a chapter of careful bookkeeping and changes nothing that follows. Second, both hypotheses in the definition are needed for trivial reasons: the empty set has every number as an upper bound and so has no least one, and a set that is not bounded above has no upper bound at all.
Completeness is stated for suprema, and infima come for free.
Proposition 1.8 (existence of infima). Every nonempty set \(S\subseteq\mathbb R\) that is bounded below has an infimum, and \(\inf S=-\sup(-S)\) , where \(-S=\{-x:x\in S\}\) .
Proof. If \(\ell\) is a lower bound of \(S\) , then \(-x\le-\ell\) for every \(x\in S\) , so \(-S\) is nonempty and bounded above. Let \(s=\sup(-S)\) . For every \(x\in S\) we have \(-x\le s\) , so \(-s\le x\) , and \(-s\) is a lower bound of \(S\) . If \(\ell\) is any lower bound of \(S\) , then \(-\ell\) is an upper bound of \(-S\) , so \(s\le-\ell\) and therefore \(\ell\le-s\) . Thus \(-s\) is the greatest lower bound.
1.4 First consequences: no infinitely large or infinitely small numbers
It seems too obvious to prove that the natural numbers are not bounded above. Yet it does not follow from the ordered field axioms alone; there are ordered fields containing elements larger than every natural number. In \(\mathbb R\) they are excluded by completeness.
Theorem 1.9 (Archimedean property). (a) For every real number \(x\) there is a natural number \(n\) with \(n>x\) . (b) For every real number \(\varepsilon>0\) there is a natural number \(n\) with \(1/n<\varepsilon\) .
Proof. (a) Suppose not. Then some real \(x\) is an upper bound of \(\mathbb N\) , so \(\mathbb N\) is nonempty and bounded above and has a supremum \(\alpha\) . By Lemma 1.6 with \(\varepsilon=1\) there is \(n\in\mathbb N\) with \(n>\alpha-1\) . Then \(n+1>\alpha\) , and \(n+1\in\mathbb N\) , contradicting that \(\alpha\) is an upper bound.
(b) Apply (a) to \(x=1/\varepsilon\) to get \(n>1/\varepsilon\) ; then \(1/n<\varepsilon\) .
Part (b) says that there is no positive number smaller than all the reciprocals \(1/n\) . It is the reason \(1/n\) tends to \(0\) , and it is used, usually silently, whenever one says “choose \(n\) so large that…”.
Theorem 1.10 (density of the rationals). If \(a<b\) are real numbers, there is a rational number \(q\) with \(a<q<b\) .
Proof. The idea is to choose a denominator so large that steps of size \(1/n\) cannot jump over the interval. By Theorem 1.9(b) choose \(n\in\mathbb N\) with \(1/n<b-a\) , so that \(nb-na>1\) . By Theorem 1.9(a) there are natural numbers \(k_1>na\) and \(k_2>-na\) , so \(-k_2<na<k_1\) . Among the finitely many integers from \(-k_2\) to \(k_1\) , let \(m\) be the smallest one with \(m>na\) . Then \(m-1\le na\) , and therefore
Dividing by \(n>0\) gives \(a<m/n<b\) .
Example 1.2: A rational number in a prescribed gap
The proof of Theorem 1.10 is a recipe. Take \(a=\sqrt2\) (whose existence is the next theorem) and \(b=1.415\) . Here \(b-a\approx 0.000786\) , so we need \(1/n<b-a\) , and the smallest natural number that achieves this is \(n=1272\) . Then \(na\approx 1798.88\) , and the smallest integer exceeding it is \(m=1799\) . The recipe returns
The conclusion can be checked without decimals for \(\sqrt2\) : \(q^2=3236401/1617984\approx 2.000268>2\) , so \(q>\sqrt2\) , and \(q<1.415\) because \(1799<1.415\times 1272=1799.88\) . Simpler rationals lie in the same gap, for example \(1.4145\) ; the point of the recipe is that it works for every gap, however narrow.
Now we can settle the question that Theorem 1.2 left open.
Theorem 1.11 (existence of the square root of two). There is exactly one positive real number \(\alpha\) with \(\alpha^2=2\) .
Proof. Let \(S=\{x\in\mathbb R:x\ge 0\ \text{and}\ x^2<2\}\) . It is nonempty, since \(1\in S\) . It is bounded above by \(2\) : if \(x>2\) then \(x^2>4>2\) , so \(x\notin S\) . Let \(\alpha=\sup S\) ; then \(\alpha\ge 1\) . We show that \(\alpha^2<2\) and \(\alpha^2>2\) are both impossible.
Suppose \(\alpha^2<2\) . Choose a number \(h\) with \(0<h<1\) and \(h<(2-\alpha^2)/(2\alpha+1)\) . Then, using \(h^2<h\) ,
So \(\alpha+h\in S\) , although \(\alpha+h>\alpha\) . This contradicts that \(\alpha\) is an upper bound of \(S\) .
Suppose \(\alpha^2>2\) . Put \(h=(\alpha^2-2)/(2\alpha)>0\) . Then \(\alpha-h=(\alpha^2+2)/(2\alpha)>0\) and
If \(x\in S\) , then \(x^2<2<(\alpha-h)^2\) , and since both \(x\) and \(\alpha-h\) are nonnegative this forces \(x<\alpha-h\) . So \(\alpha-h\) is an upper bound of \(S\) smaller than \(\alpha\) , contradicting that \(\alpha\) is the least one.
By (O1) the only remaining possibility is \(\alpha^2=2\) . For uniqueness, if \(0<\beta<\gamma\) then \(\beta^2<\gamma^2\) , so two different positive numbers cannot have the same square.
Look at how the proof is organised, because the pattern returns many times. Completeness hands us a candidate, the supremum of a set built to stop just short of the target. Then two estimates show the candidate can be neither too small (we could push further inside the set) nor too large (we could pull the bound down). The same argument produces \(n\) th roots of every positive real (Exercise 9 does a cube root) and, in Chapter 5, the Intermediate Value Theorem in general. We write \(\sqrt2\) for the number \(\alpha\) .
Corollary 1.12 (density of the irrationals). If \(a<b\) are real numbers, there is an irrational number \(t\) with \(a<t<b\) .
Proof. By Theorem 1.10 there is a rational \(q\) with \(a/\sqrt2<q<b/\sqrt2\) , and we may take \(q\ne 0\) (if \(q=0\) , apply the theorem again to the interval from \(0\) to \(b/\sqrt2\) ). Then \(a<q\sqrt2<b\) . If \(q\sqrt2\) were rational, then \(\sqrt2=(q\sqrt2)/q\) would be rational, contradicting Theorem 1.2.
Example 1.3: Watching the gap in the rationals
The set \(T=\{q\in\mathbb Q:q>0\ \text{and}\ q^2<2\}\) is nonempty and bounded above by \(2\) . In \(\mathbb R\) its supremum is \(\sqrt2\) . In \(\mathbb Q\) it has no supremum, and one formula shows why. For a positive rational \(s\) put
Then \(s'\) is a positive rational, and a short computation gives
If \(s^2<2\) , both formulas say that \(s'\) is larger than \(s\) and still has square less than \(2\) . So no element of \(T\) is an upper bound of \(T\) : the set has no maximum. If \(s^2>2\) , they say that \(s'\) is smaller than \(s\) and still has square greater than \(2\) ; such an \(s'\) is again an upper bound of \(T\) , because \(q^2<2<s'^2\) forces \(q<s'\) for positive \(q\) . So no rational upper bound of \(T\) is the least one.
Suppose now that a rational \(s\) were the supremum of \(T\) within \(\mathbb Q\) . Then \(s>0\) , and \(s^2\ne 2\) by Theorem 1.2. If \(s^2<2\) then \(s\in T\) and \(s'\in T\) is larger, so \(s\) is not an upper bound. If \(s^2>2\) then \(s'\) is a smaller rational upper bound, so \(s\) is not the least. Either way we have a contradiction, and \(\mathbb Q\) is not complete.
Starting from \(s=1\) the formula produces \(4/3\) , \(7/5\) , \(24/17\) , \(41/29\) , with squares approximately \(1.7778\) , \(1.96\) , \(1.99308\) , \(1.99881\) . Starting from \(s=2\) it produces \(3/2\) , \(10/7\) , \(17/12\) , \(58/41\) , with squares \(2.25\) , approximately \(2.04082\) , \(2.00694\) , \(2.00119\) . The two lists close in on each other, and there is no rational number at the place where they would meet.
1.5 Nested intervals and the size of the continuum
Completeness can be recast as a statement about shrinking intervals, which is often the more convenient form for constructions.
Theorem 1.13 (nested intervals). Let \(I_n=[a_n,b_n]\) , \(n\in\mathbb N\) , be closed bounded intervals with \(a_n\le b_n\) and \(I_{n+1}\subseteq I_n\) for every \(n\) . Then \(\bigcap_{n}I_n\) is not empty. If in addition \(\inf\{b_n-a_n:n\in\mathbb N\}=0\) , the intersection consists of exactly one point.
Proof. Nestedness means \(a_n\le a_{n+1}\) and \(b_{n+1}\le b_n\) . For any indices \(n\) and \(m\) , let \(k\) be the larger of the two; then \(a_n\le a_k\le b_k\le b_m\) . So every \(b_m\) is an upper bound of the set \(A=\{a_n:n\in\mathbb N\}\) . Let \(x=\sup A\) . Then \(a_n\le x\) for every \(n\) because \(x\) is an upper bound of \(A\) , and \(x\le b_m\) for every \(m\) because \(x\) is the least upper bound. Hence \(x\in I_n\) for every \(n\) .
If \(x<y\) were two points of the intersection, then \(a_n\le x<y\le b_n\) would give \(b_n-a_n\ge y-x>0\) for all \(n\) , so the infimum of the lengths would be at least \(y-x\) , not \(0\) .
Both adjectives in “closed bounded” matter. The open intervals \((0,1/n)\) are nested and their intersection is empty: a point \(x>0\) in all of them would satisfy \(x<1/n\) for every \(n\) , contradicting Theorem 1.9(b). The closed but unbounded intervals \([n,\infty)\) are nested with empty intersection by Theorem 1.9(a).
The nested interval theorem gives a quick proof of a fact that surprised Cantor’s contemporaries. Call a set countable if it is finite or its elements can be listed as a sequence \(x_1,x_2,x_3,\dots\) in which every element appears. The integers are countable (\(0,1,-1,2,-2,\dots\) ), and so are the rationals: list the fractions \(p/q\) in lowest terms with \(q>0\) in order of increasing \(\lvert p\rvert+q\) , there being finitely many for each value of that sum.
Theorem 1.14 (uncountability of the reals). The interval \([0,1]\) is not countable. Consequently \(\mathbb R\) is not countable.
Proof. Let \(x_1,x_2,x_3,\dots\) be any sequence of points of \([0,1]\) . We find a point of \([0,1]\) that is not in the sequence. Cut \([0,1]\) into three closed intervals of equal length. The left and right thirds are disjoint, so \(x_1\) fails to lie in at least one of them; call that one \(I_1\) . Cut \(I_1\) into three equal closed intervals and let \(I_2\) be the left or the right third, chosen so that \(x_2\notin I_2\) . Continuing, we obtain nested closed bounded intervals \(I_1\supseteq I_2\supseteq\cdots\) with \(x_n\notin I_n\) for every \(n\) . By Theorem 1.13 there is a point \(x\) belonging to every \(I_n\) . For each \(n\) we have \(x\in I_n\) and \(x_n\notin I_n\) , so \(x\ne x_n\) . Thus no sequence exhausts \([0,1]\) . A listing of \(\mathbb R\) would give a listing of \([0,1]\) by deleting the terms outside it, so \(\mathbb R\) is not countable either.
Since the rationals are countable and the reals are not, the irrational numbers are not countable (the union of two countable sets is countable: interleave the two lists). In this precise sense almost every real number is irrational, although the rationals are dense. Density and size are different notions, and a good deal of analysis lives in the space between them.
1.6 Calculating with suprema
Later chapters compare suprema of related sets constantly: the supremum of a sum, of a function over a smaller interval, of the upper sums of an integral. Three rules cover nearly every case. For sets \(A,B\subseteq\mathbb R\) and a real number \(c\) write \(A+B=\{a+b:a\in A,\ b\in B\}\) and \(cA=\{ca:a\in A\}\) .
Proposition 1.15 (rules for suprema). Let \(A\) and \(B\) be nonempty sets of real numbers that are bounded above. (a) If \(A\subseteq B\) , then \(\sup A\le\sup B\) . (b) \(\sup(A+B)=\sup A+\sup B\) . (c) If \(c\ge 0\) , then \(\sup(cA)=c\,\sup A\) . (d) If \(a\le b\) for every \(a\in A\) and every \(b\in B\) , then \(\sup A\le\inf B\) .
Proof. (a) \(\sup B\) is an upper bound of \(B\) , hence of the smaller set \(A\) , hence at least the least upper bound of \(A\) .
(b) Write \(\alpha=\sup A\) and \(\beta=\sup B\) . For \(a\in A\) and \(b\in B\) we have \(a+b\le\alpha+\beta\) , so \(\alpha+\beta\) is an upper bound of \(A+B\) . Let \(\varepsilon>0\) . By Lemma 1.6 there are \(a\in A\) with \(a>\alpha-\varepsilon/2\) and \(b\in B\) with \(b>\beta-\varepsilon/2\) . Then \(a+b>\alpha+\beta-\varepsilon\) . By Lemma 1.6 again, \(\alpha+\beta=\sup(A+B)\) .
(c) If \(c=0\) both sides are \(0\) . If \(c>0\) , then \(a\le\sup A\) gives \(ca\le c\sup A\) , so \(c\sup A\) is an upper bound of \(cA\) ; and if \(u\) is any upper bound of \(cA\) then \(u/c\) is an upper bound of \(A\) , so \(\sup A\le u/c\) and \(c\sup A\le u\) .
(d) Fix \(b\in B\) . It is an upper bound of \(A\) , so \(\sup A\le b\) . This holds for every \(b\in B\) , so \(\sup A\) is a lower bound of \(B\) , and therefore \(\sup A\le\inf B\) .
Part (b) used the trick of splitting \(\varepsilon\) into two halves, one for each set. You will see \(\varepsilon/2\) and \(\varepsilon/3\) on almost every page from here on; the choice is made with hindsight so that the final estimate comes out as a clean \(\varepsilon\) .
For a real-valued function \(f\) on a set \(D\) we write \(\sup_D f\) for the supremum of the set of values \(\{f(x):x\in D\}\) , when that set is bounded above.
Example 1.4: A set that oscillates
Let \(S=\{(-1)^n+1/n:n\in\mathbb N\}\) . The first few elements are \(0\) , \(3/2\) , \(-2/3\) , \(5/4\) , \(-4/5\) , \(7/6\) . For even \(n\) the element is \(1+1/n\) , which is largest when \(n=2\) ; for odd \(n\) it is \(-1+1/n\le 0\) . So \(3/2\) is an upper bound that belongs to \(S\) : \(\sup S=\max S=3/2\) .
For the infimum, every element is greater than \(-1\) , since \((-1)^n\ge-1\) and \(1/n>0\) . So \(-1\) is a lower bound. Given \(\varepsilon>0\) , choose by Theorem 1.9(b) an odd \(n\) with \(1/n<\varepsilon\) ; then \(-1+1/n<-1+\varepsilon\) . By the infimum form of Lemma 1.6, \(\inf S=-1\) . It is not attained, so \(S\) has no minimum. With \(\varepsilon=0.003\) the choice \(n=335\) works, since \(335\) is odd and \(1/335\approx 0.002985<0.003\) .
Example 1.5: The supremum of a sum of functions can be smaller than the sum of the suprema
On \(D=[0,1]\) let \(f(x)=x\) and \(g(x)=1-x\) . Then \(\sup_D f=1\) (attained at \(x=1\) ) and \(\sup_D g=1\) (attained at \(x=0\) ), but \(f(x)+g(x)=1\) for every \(x\) , so \(\sup_D(f+g)=1\) , not \(2\) .
This does not contradict Proposition 1.15(b). There the sum set \(A+B\) pairs every element of \(A\) with every element of \(B\) . The values of \(f+g\) form the smaller set \(\{f(x)+g(x):x\in D\}\) , in which both functions are evaluated at the same point, and \(f\) and \(g\) are large at different points. By part (a) of the proposition, what survives is an inequality:
valid for any two functions bounded above on \(D\) . A second illustration: for \(f(x)=x^2\) and \(g(x)=-x\) on \([0,1]\) , \(\sup_D f+\sup_D g=1+0=1\) , while \(f(x)+g(x)=x^2-x\le 0\) with equality at the endpoints, so \(\sup_D(f+g)=0\) .
This inequality is the reason the upper integral of Chapter 7 is only subadditive at first sight, and why proving that the integral of a sum is the sum of the integrals takes an argument.
The chapter has produced one axiom and a toolkit: the approximation property, the Archimedean property, density, nested intervals, and the rules for suprema. What it has not yet done is describe approach. The lists in Example 1.3 visibly close in on \(\sqrt2\) , and we had to say so informally. Chapter 2 makes that precise with the definition of a limit, and shows that completeness can be restated entirely in terms of sequences.
Exercises
-
For each set find the supremum and the infimum, and say whether each is attained: (a) \([0,3)\) ; (b) \(\{1/n:n\in\mathbb N\}\) ; (c) \(\{x\in\mathbb Q:x^2<9\}\) ; (d) \(\{2-1/n^2:n\in\mathbb N\}\) .
Answer
(a) \(\sup=3\) , not attained; \(\inf=0\) , attained. (b) \(\sup=1\) , attained at \(n=1\) ; \(\inf=0\) , not attained. (c) \(\sup=3\) and \(\inf=-3\) , neither attained, since \(x^2<9\) excludes \(\pm 3\) and rationals come arbitrarily close to both. (d) \(\sup=2\) , not attained; \(\inf=1\) , attained at \(n=1\) .
-
Using only the order axioms (O1) to (O4) and the field axioms, prove that \(0<a<b\) implies \(a^2<b^2\) , and deduce that a positive real number has at most one positive square root.
Hint
Multiply \(a<b\) by the positive number \(a\) to get \(a\cdot a<a\cdot b\) , and by the positive number \(b\) to get \(a\cdot b<b\cdot b\) ; both steps are (O4). Then use (O2). For uniqueness, if \(\beta\ne\gamma\) are positive, (O1) says one is smaller, and then their squares differ.
-
Prove that there is no rational number whose square is \(3\) . Then explain exactly where the same argument breaks down if \(3\) is replaced by \(4\) .
Solution
Suppose \(r=p/q\) is rational with \(r^2=3\) , where \(p,q\) are integers with no common factor and \(q\ne 0\) . Then \(p^2=3q^2\) , so \(3\) divides \(p^2\) . We claim \(3\) divides \(p\) . Every integer has the form \(3k\) , \(3k+1\) , or \(3k-1\) , and
\[ (3k\pm 1)^2=9k^2\pm 6k+1=3(3k^2\pm 2k)+1 \]leaves remainder \(1\) on division by \(3\) . So if \(3\) does not divide \(p\) , it does not divide \(p^2\) . Hence \(p=3k\) for some integer \(k\) , and \(9k^2=3q^2\) gives \(q^2=3k^2\) . The same claim shows that \(3\) divides \(q\) . Now \(3\) is a common factor of \(p\) and \(q\) , a contradiction.
With \(4\) in place of \(3\) the argument would start from \(p^2=4q^2\) and need the step “if \(4\) divides \(p^2\) then \(4\) divides \(p\) ”. That step is false: \(4\) divides \(2^2\) and does not divide \(2\) . The property used for \(3\) was that \(3\) is prime. From \(p^2=4q^2\) one can only conclude that \(p\) is even, \(p=2k\) , and then \(q^2=k^2\) , which is no contradiction. Indeed \(r=2\) is a rational square root of \(4\) .
-
Let \(S\) be a nonempty set of real numbers and let \(u\) be an upper bound of \(S\) that belongs to \(S\) . Prove that \(u=\sup S\) , and give an example of a bounded set for which no upper bound belongs to the set.
Answer
\(u\) is an upper bound by hypothesis. If \(v\) is any upper bound, then \(u\le v\) because \(u\in S\) . So \(u\) is the least upper bound. The interval \((0,1)\) is bounded and none of its upper bounds, the numbers \(v\ge 1\) , belongs to it.
-
Let \(A\subseteq B\) be nonempty bounded sets of real numbers. Prove the chain \(\inf B\le\inf A\le\sup A\le\sup B\) , and give an example in which \(A\ne B\) but all four numbers satisfy \(\inf A=\inf B\) and \(\sup A=\sup B\) .
Solution
All four numbers exist by completeness and Proposition 1.8, because \(A\) and \(B\) are nonempty and bounded.
\(\sup A\le\sup B\) . This is Proposition 1.15(a): \(\sup B\) is an upper bound of \(B\) , so it is an upper bound of the subset \(A\) , and the least upper bound of \(A\) cannot exceed it.
\(\inf B\le\inf A\) . Symmetrically, \(\inf B\) is a lower bound of \(B\) , hence of \(A\) , and the greatest lower bound of \(A\) is at least as large as any lower bound of \(A\) .
\(\inf A\le\sup A\) . Since \(A\) is nonempty, pick \(a\in A\) . Then \(\inf A\le a\le\sup A\) .
For the example take \(A=(0,1)\) and \(B=[0,1]\) . Then \(A\subseteq B\) and \(A\ne B\) , while \(\inf A=\inf B=0\) and \(\sup A=\sup B=1\) . Enlarging a set by points that are already its infimum or supremum changes nothing.
-
Let \(A\) be a nonempty bounded set and let \(c<0\) . Prove that \(\sup(cA)=c\,\inf A\) and \(\inf(cA)=c\,\sup A\) .
Solution
Let \(\ell=\inf A\) and \(s=\sup A\) , which exist because \(A\) is nonempty and bounded. Let \(c<0\) .
\(\sup(cA)=c\ell\) . For every \(a\in A\) we have \(\ell\le a\) ; multiplying by the negative number \(c\) reverses the inequality, so \(ca\le c\ell\) . Thus \(c\ell\) is an upper bound of \(cA\) . Let \(u\) be any upper bound of \(cA\) . Then \(ca\le u\) for all \(a\in A\) , and dividing by \(c<0\) reverses the inequality again: \(a\ge u/c\) for all \(a\in A\) . So \(u/c\) is a lower bound of \(A\) , whence \(u/c\le\ell\) , and multiplying by \(c<0\) gives \(u\ge c\ell\) . Therefore \(c\ell\) is the least upper bound of \(cA\) .
\(\inf(cA)=cs\) . The same argument with the inequalities reversed: \(a\le s\) gives \(ca\ge cs\) , so \(cs\) is a lower bound of \(cA\) ; if \(t\) is any lower bound of \(cA\) , then \(a\le t/c\) for all \(a\in A\) , so \(s\le t/c\) and \(t\le cs\) .
The special case \(c=-1\) is Proposition 1.8.
-
Use the Archimedean property to prove that \(\inf\{1/n:n\in\mathbb N\}=0\) , and find the smallest natural number \(n\) with \(1/n<0.004\) .
Answer
\(0\) is a lower bound because every \(1/n\) is positive. Given \(\varepsilon>0\) , Theorem 1.9(b) supplies \(n\) with \(1/n<0+\varepsilon\) , so by the infimum form of Lemma 1.6 the infimum is \(0\) . Since \(1/250=0.004\) exactly, the smallest \(n\) with \(1/n<0.004\) is \(n=251\) .
-
Prove that for every real number \(x\) there is exactly one integer \(m\) with \(m\le x<m+1\) . (This integer is the floor of \(x\) ; the proof of Theorem 1.10 contains most of the argument.)
Hint
Existence: as in the proof of Theorem 1.10, the Archimedean property traps \(x\) between two integers \(-k_2<x<k_1\) ; among the finitely many integers in that range take the largest \(m\) with \(m\le x\) , and show \(x<m+1\) by maximality. Uniqueness: if \(m\le x<m+1\) and \(m'\le x<m'+1\) with \(m<m'\) , then \(m+1\le m'\le x\) , contradicting \(x<m+1\) .
-
Adapt the proof of Theorem 1.11 to show that there is a positive real number \(\alpha\) with \(\alpha^3=2\) . State clearly the set whose supremum you take and the two estimates that rule out \(\alpha^3<2\) and \(\alpha^3>2\) .
Solution
Let \(S=\{x\in\mathbb R:x\ge 0\ \text{and}\ x^3<2\}\) . Then \(1\in S\) , and \(2\) is an upper bound because \(x>2\) gives \(x^3>8\) . Let \(\alpha=\sup S\) , so \(1\le\alpha\le 2\) . Note that for nonnegative numbers \(0\le x<y\) implies \(x^3<y^3\) .
\(\alpha^3<2\) is impossible. For \(0<h<1\) we have \(h^2<h\) and \(h^3<h\) , so
\[ (\alpha+h)^3=\alpha^3+3\alpha^2h+3\alpha h^2+h^3<\alpha^3+(3\alpha^2+3\alpha+1)h . \]If \(\alpha^3<2\) , choose \(h\) with \(0<h<1\) and \(h<(2-\alpha^3)/(3\alpha^2+3\alpha+1)\) . Then \((\alpha+h)^3<2\) , so \(\alpha+h\in S\) , contradicting that \(\alpha\) is an upper bound.
\(\alpha^3>2\) is impossible. For \(0<h<\alpha\) ,
\[ (\alpha-h)^3=\alpha^3-3\alpha^2h+h^2(3\alpha-h)>\alpha^3-3\alpha^2h . \]If \(\alpha^3>2\) , take \(h=(\alpha^3-2)/(3\alpha^2)\) . Then \(h>0\) , and \(h<\alpha\) because \(\alpha^3-2<3\alpha^3\) . The estimate gives \((\alpha-h)^3>\alpha^3-(\alpha^3-2)=2\) . Every \(x\in S\) satisfies \(x^3<2<(\alpha-h)^3\) , hence \(x<\alpha-h\) . So \(\alpha-h\) is an upper bound of \(S\) below \(\alpha\) , contradicting that \(\alpha\) is least.
By trichotomy \(\alpha^3=2\) .
-
Apply the recipe in the proof of Theorem 1.10 to \(a=\sqrt5\) and \(b=2.24\) : find the denominator \(n\) and numerator \(m\) it produces, and verify \(a<m/n<b\) without using a decimal expansion of \(\sqrt5\) .
Solution
The denominator. The recipe needs \(1/n<b-a\) , that is \(\sqrt5<2.24-1/n\) , which for positive numbers is the same as \((2.24-1/n)^2>5\) . In integers: \(2.24-1/n=(56n-25)/(25n)\) , so the condition is \((56n-25)^2>3125n^2\) . For \(n=254\) : \(14199^2=201611601\) and \(3125\cdot 254^2=201612500\) , so the condition fails. For \(n=255\) : \(14255^2=203205025\) and \(3125\cdot 255^2=203203125\) , so it holds. The smallest admissible denominator is \(n=255\) .
The numerator. We need the smallest integer \(m\) with \(m>255\sqrt5\) , that is \(m^2>5\cdot 255^2=325125\) . Since \(570^2=324900<325125<326041=571^2\) , we get \(m=571\) .
Verification. The recipe returns \(q=571/255\) . We have \(q>\sqrt5\) because \(571^2=326041>325125=5\cdot 255^2\) . And \(q<2.24\) because \(2.24\times 255=571.2>571\) . So \(\sqrt5<571/255<2.24\) ; in decimals \(571/255\approx 2.239216\) .
-
A student writes: “Let \(s=\sup S\) . For each \(\varepsilon>0\) the number \(s-\varepsilon\) is not an upper bound of \(S\) , hence \(s-\varepsilon\in S\) .” Identify the error, and give a set \(S\) for which the conclusion \(s-\varepsilon\in S\) fails for every \(\varepsilon>0\) .
Answer
“\(s-\varepsilon\) is not an upper bound” means that some element of \(S\) is larger than \(s-\varepsilon\) . It does not say that \(s-\varepsilon\) is itself an element. For \(S=\{1\}\) we have \(s=1\) , and \(1-\varepsilon\notin S\) for every \(\varepsilon>0\) .
-
Show that both hypotheses “closed” and “bounded” in the nested interval theorem are needed, by computing \(\bigcap_n(0,1/n)\) and \(\bigcap_n[n,\infty)\) with proof. Then give nested closed bounded intervals whose intersection is an interval of positive length.
Solution
The open intervals. Suppose \(x\in(0,1/n)\) for every \(n\) . Then \(x>0\) , and by Theorem 1.9(b) there is \(n\) with \(1/n<x\) , so \(x\notin(0,1/n)\) for that \(n\) . Hence \(\bigcap_n(0,1/n)=\emptyset\) . These intervals are nested and bounded but not closed; the point \(0\) that the nested interval theorem would produce has been removed from each of them.
The unbounded intervals. Suppose \(x\in[n,\infty)\) for every \(n\) . Then \(x\ge n\) for every natural number \(n\) , so \(x\) is an upper bound of \(\mathbb N\) , contradicting Theorem 1.9(a). Hence \(\bigcap_n[n,\infty)=\emptyset\) . These intervals are nested and closed but not bounded.
Positive length. Take \(I_n=[-1/n,\,1+1/n]\) . These are nested closed bounded intervals. Every point of \([0,1]\) lies in all of them. A point \(x>1\) fails to lie in \(I_n\) once \(1/n<x-1\) , and similarly for \(x<0\) . So the intersection is \([0,1]\) . Here the lengths \(1+2/n\) have infimum \(1\) , not \(0\) , which is consistent with the uniqueness clause of the theorem.
-
Prove that the set of irrational numbers in \([0,1]\) is not countable. You may use that a union of two countable sets is countable.
Hint
Argue by contradiction. If the irrationals in \([0,1]\) were countable, then \([0,1]\) would be the union of two countable sets, the rationals in \([0,1]\) and the irrationals in \([0,1]\) . Interleave the two lists to list \([0,1]\) and quote Theorem 1.14.
-
Let \(A\) and \(B\) be nonempty sets with \(a\le b\) for all \(a\in A\) and \(b\in B\) . Prove that \(\sup A=\inf B\) if and only if for every \(\varepsilon>0\) there are \(a\in A\) and \(b\in B\) with \(b-a<\varepsilon\) .
Solution
The set \(A\) is bounded above by any element of \(B\) , and \(B\) is bounded below by any element of \(A\) , so \(\sup A\) and \(\inf B\) exist. The argument that proves Proposition 1.15(d) uses only this, and not that \(B\) is bounded above: each \(b\in B\) is an upper bound of \(A\) , so \(\sup A\le b\) , and hence \(\sup A\) is a lower bound of \(B\) . So \(\sup A\le\inf B\) in every case.
If the \(\varepsilon\) condition holds. Let \(\varepsilon>0\) and choose \(a\in A\) , \(b\in B\) with \(b-a<\varepsilon\) . Then
\[ \inf B\le b<a+\varepsilon\le\sup A+\varepsilon . \]So \(0\le\inf B-\sup A<\varepsilon\) for every \(\varepsilon>0\) . A nonnegative number smaller than every positive number is \(0\) ; hence \(\sup A=\inf B\) .
If \(\sup A=\inf B\) . Call the common value \(c\) and let \(\varepsilon>0\) . By Lemma 1.6 there is \(a\in A\) with \(a>c-\varepsilon/2\) , and by its infimum form there is \(b\in B\) with \(b<c+\varepsilon/2\) . Then \(b-a<(c+\varepsilon/2)-(c-\varepsilon/2)=\varepsilon\) .
This is exactly the shape of the integrability criterion in Chapter 7, with \(A\) the set of lower sums and \(B\) the set of upper sums.
-
Show that the completeness axiom is equivalent to the statement “every nonempty set of real numbers that is bounded below has an infimum”, by proving that the second statement implies the first.
Hint
Assume every nonempty set bounded below has an infimum, and let \(S\) be nonempty and bounded above. Let \(U\) be the set of all upper bounds of \(S\) . Show that \(U\) is nonempty and bounded below (by any element of \(S\) ), put \(t=\inf U\) , and prove two things: each \(x\in S\) is a lower bound of \(U\) , so \(x\le t\) ; and \(t\le u\) for each \(u\in U\) . Conclude \(t=\sup S\) .
-
The Archimedean property was proved from completeness. Show that the converse implication fails: explain why \(\mathbb Q\) satisfies both parts of Theorem 1.9 although it is not complete.
Answer
A rational \(x=p/q\) with \(q\ge 1\) satisfies \(x\le\lvert p\rvert<\lvert p\rvert+1\) , and \(\lvert p\rvert+1\) is a natural number; so part (a) holds in \(\mathbb Q\) with no appeal to suprema, and (b) follows from (a) as before. But \(\mathbb Q\) is not complete, by Example 1.3. So the Archimedean property is strictly weaker than completeness.
-
Find, with proof, the supremum and infimum of \(\{m/(m+n):m,n\in\mathbb N\}\) , and decide whether either is attained.
Solution
Let \(S=\{m/(m+n):m,n\in\mathbb N\}\) . Since \(m\) and \(n\) are positive, \(0<m<m+n\) , so every element satisfies \(0<m/(m+n)<1\) . Thus \(0\) is a lower bound and \(1\) is an upper bound, and neither belongs to \(S\) .
Supremum. Let \(\varepsilon>0\) . Take \(n=1\) and, by Theorem 1.9(b), \(m\) with \(1/(m+1)<\varepsilon\) . Then \(m/(m+1)=1-1/(m+1)>1-\varepsilon\) . By Lemma 1.6, \(\sup S=1\) . For instance \(m=999\) , \(n=1\) gives \(0.999\) .
Infimum. Let \(\varepsilon>0\) . Take \(m=1\) and \(n\) with \(1/(n+1)<\varepsilon\) . Then \(1/(1+n)<0+\varepsilon\) . By the infimum form of Lemma 1.6, \(\inf S=0\) .
Neither is attained, because every element lies strictly between \(0\) and \(1\) . So \(S\) has neither a maximum nor a minimum.
-
For \(f(x)=x^2\) and \(g(x)=1-2x\) on \(D=[0,1]\) , compute \(\sup_D f\) , \(\sup_D g\) , \(\sup_D(f+g)\) , and \(\inf_D(f+g)\) , and state which rule of Section 1.6 the first three numbers illustrate.
Answer
\(\sup_D f=1\) and \(\sup_D g=1\) . Since \(f(x)+g(x)=(x-1)^2\) , \(\sup_D(f+g)=1\) (at \(x=0\) ) and \(\inf_D(f+g)=0\) (at \(x=1\) ). The first three numbers illustrate \(\sup_D(f+g)\le\sup_D f+\sup_D g\) with strict inequality, \(1<2\) : \(f\) is largest at \(x=1\) and \(g\) at \(x=0\) .
-
Give a second proof that \(\sqrt2\) exists using nested intervals: starting from \([1,2]\) , bisect repeatedly, keeping at each stage a half \([a_n,b_n]\) with \(a_n^2\le 2\le b_n^2\) , and prove that the common point \(x\) satisfies \(x^2=2\) .
Hint
Start with \(a_1=1\) , \(b_1=2\) . Given \([a_n,b_n]\) with \(a_n^2\le 2\le b_n^2\) , let \(c\) be the midpoint; keep \([a_n,c]\) if \(c^2\ge 2\) and \([c,b_n]\) otherwise. The lengths are \(2^{-(n-1)}\) , whose infimum is \(0\) by the Archimedean property (use \(2^{n}>n\) ). Let \(x\) be the common point. From \(a_n\le x\le b_n\) deduce \(a_n^2\le x^2\le b_n^2\) , so both \(2\) and \(x^2\) lie in \([a_n^2,b_n^2]\) , whose length \((b_n-a_n)(b_n+a_n)\le 4(b_n-a_n)\) has infimum \(0\) . Conclude \(\lvert x^2-2\rvert=0\) .
-
Let \(x\) be a real number. Prove that \(x=\sup\{q\in\mathbb Q:q<x\}\) . Explain in one sentence how this lets one think of a real number as a set of rationals.
Solution
Let \(Q_x=\{q\in\mathbb Q:q<x\}\) . By Theorem 1.10 there is a rational between \(x-1\) and \(x\) , so \(Q_x\) is nonempty. It is bounded above by \(x\) . Let \(s=\sup Q_x\) ; since \(x\) is an upper bound, \(s\le x\) .
Suppose \(s<x\) . By Theorem 1.10 there is a rational \(q\) with \(s<q<x\) . Then \(q\in Q_x\) and \(q>s\) , contradicting that \(s\) is an upper bound of \(Q_x\) . Hence \(s=x\) .
So a real number is completely determined by the set of rational numbers below it: different reals have different sets \(Q_x\) , and \(x\) is recovered from \(Q_x\) as its supremum. Dedekind’s construction of the real numbers turns this around and defines a real number to be such a set of rationals.