Part B Since every non-empty set bounded above has a supremum, E has a

supremum, call it c.

35

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Part C Let > 0. Since f is continuous at c we can ¬nd a δ > 0 such that

if x ∈ [a, b] and |x ’ c| < δ then |f (x) ’ f (c)| < . We must consider three

possible cases according as a < c < b, c = b or c = a.

If a < c < b, we proceed as follows. Since c = sup E we can ¬nd x0 ∈ E

such that 0 ¤ c ’ x0 < δ and so |f (x0 ) ’ f (c)| < . Since x0 ∈ E, f (x0 ) ≥ 0

and so f (c) ≥ ’ . On the other hand, choosing y0 = c + min(b ’ c, δ)/2 we

know that 0 ¤ y0 ’ c < δ and so |f (x0 ) ’ f (c)| < . Since y0 > c it follows

that y0 ∈ E so f (y0 ) < 0 and f (c) < . We have shown that |f (c)| ¤ .

/

If c = b, we proceed as follows. Since c = sup E, we can ¬nd x0 ∈ E such

that 0 ¤ c ’ x0 < δ and so |f (x0 ) ’ f (c)| < . Since x0 ∈ E, f (x0 ) ≥ 0 and

so f (c) ≥ ’ . By hypothesis f (b) ¤ 0 so |f (c)| ¤ .

If c = a we proceed as follows. Since c = a we know that f (c) ≥ 0. On

the other hand, choosing y0 = c + min(b ’ c, δ)/2 we know that 0 ¤ y0 ’ c < δ

and so |f (y0 ) ’ f (c)| < . Since y0 > c it follows that y0 ∈ E so f (y0 ) < 0

/

and f (c) < . We have shown that |f (c)| < .

In all three cases we have shown that |f (c)| ¤ for all > 0 so f (c) =

0.

Exercise 3.1.13. In both the ˜lion hunting™ and the ˜supremum argument™

proofs we end up with a point c where f (c) = 0, that is a ˜zero of f ™. Give an

example of a function f : [a, b] ’ R satisfying the hypotheses of the interme-

diate value theorem for which ˜lion hunting™ and the ˜supremum argument™

give di¬erent zeros.

Let us summarise the proof just given. In Part A we construct a set E

on which f has a certain kind of behaviour and show that E is bounded and

non-empty. In Part B we use the fact that E is bounded and non-empty to

give us a point c = sup E which is in some sense a ˜transition point™. Finally

in Part C we examine the point c to make sure that it really has the desired

property. Note that we had to examine the cases c = a and c = b separately.

This often happens when we use the ˜supremum argument™.

Let us see what goes wrong if we omit parts of the hypotheses of The-

orem 3.1.12. If we omit the condition f (a) ≥ 0, then we cannot even start

Part A of the argument.

If we have f (a) ≥ 0 but replace R by another ordered ¬eld for which it is

not necessarily true that every non-empty bounded subset has a supremum,

Part A goes through perfectly but Part B fails.

If we have f (a) ≥ 0 ≥ f (b) and we work over R but we do not demand f

continuous then Part C fails. Part C also fails if f (a) ≥ 0 and f is continuous

but we do not know that 0 ≥ f (b).

As a second example of how a ˜supremum argument™ can be used we

reprove Lemma 1.7.4 from which the mean value inequality (Theorem 1.7.1)

36 A COMPANION TO ANALYSIS

follows.

Lemma 3.1.14. Let U be the open interval (±, β) on the real line R. Suppose

that a, b ∈ U and b > a. If f : U ’ R is di¬erentiable with f (t) ¤ K for

all t ∈ U and > 0 then

f (b) ’ f (a) ¤ (b ’ a)(K + ).

Proof. Consider the set

E = {x ∈ [a, b] : f (t) ’ f (a) ¤ (K + )(t ’ a) for all a ¤ t ¤ x}.

We observe that f (a) ’ f (a) = 0 = (K + )(a ’ a) ≥ 0 so a ∈ E and E is

non-empty. Since x ∈ E implies x ¤ b, the set E is automatically bounded

above.

Since every non-empty set bounded above has a supremum, E has a

supremum, call it c.

Since f is di¬erentiable at c, we can ¬nd a δ > 0 such that (c’δ, c+δ) ⊆ U

and

f (c + h) ’ f (c)

’ f (c) < /2

h

whenever 0 < |h| < δ. Thus

|f (c + h) ’ f (c) ’ f (c)h| ¤ |h|/2

whenever |h| < δ, and so, since f (c) ¤ K,

f (c + h) ’ f (c) ¤ (K + /2)h for 0 ¤ h < δ

f (c) ’ f (c + h) ¤ ’(K + /2)h for ’δ ¤ h ¤ 0

We must consider three possible cases according as a < c < b, c = b or c = a.

If a < c < b we proceed as follows. If a ¤ t < c, then, by the de¬nition of

the supremum, we can ¬nd an x ∈ E with t < x ¤ c and so, by the de¬nition

of E,

f (t) ’ f (a) ¤ (K + )(t ’ a).

If c ¤ t < c + δ, then, choosing a t0 ≥ a with c > t0 > c ’ δ, we have

f (t0 ) ’ f (a) ¤ (K + )(t0 ’ a)

whilst, by the result of the previous paragraph,

f (c) ’ f (t0 ) ¤ (K + /2)(c ’ t0 )

f (t) ’ f (c) ¤ (K + /2)(t ’ c),

37

Please send corrections however trivial to twk@dpmms.cam.ac.uk

so, adding the last three inequalities, we obtain

f (t) ’ f (a) ¤ (K + )(t ’ a).

Thus f (t) ’ f (a) ¤ (K + )(t ’ a) for all a ¤ t < c + δ, contradicting the

de¬nition of c.

If c = a, then we know that f (t) ’ f (a) ¤ (K + /2)(t ’ a) for all

a ¤ t < a + δ, again contradicting the de¬nition of c. Since we have shown

that it is impossible that c = a or a < c < b, it follows that c = b. Since the

supremum of a set need not belong to that set we must still prove that b ∈ E.

However, if we choose a t0 ≥ a with b > t0 > b ’ δ the arguments of the

previous paragraph give f (b) ’ f (t0 ) ¤ (K + /2)(b ’ t0 ) and f (t0 ) ’ f (a) ¤

(K + )(t0 ’ a), so f (c) ¤ (K + )(c ’ a). The arguments of the previous

paragraph also give f (t) ’ f (a) ¤ (K + )(t ’ a) for a ¤ t < c, so c ∈ E and

the theorem follows.

We now discuss the relation between the fundamental axiom and the

supremum principle. In the proof of Theorem 3.1.7 we saw that the funda-

mental axiom together with the usual rules of algebra implies the supremum

principle. In the proof of Theorem 3.1.12 we saw that the supremum principle

together with the usual rules of algebra implies the intermediate value the-

orem. However, Theorem 1.8.1 tells us that the intermediate value theorem

together with the usual rules of algebra implies the fundamental axiom.

Although our argument has been a bit informal the reader should be

satis¬ed that the following is true. (If she is not satis¬ed she may write out

the details for herself.)

Theorem 3.1.15. Let (F, +, —, >) be an ordered ¬eld. Then the following

two statements are equivalent.

(i) Every increasing sequence bounded above has a limit.

(ii) Every non-empty set bounded above has a supremum.

The next exercise sketches a much more direct proof that the supremum

principle implies the fundamental axiom.

Exercise 3.1.16. Let (F, +, —, >) be an ordered ¬eld such that every non-

empty set bounded above has a supremum. Suppose that an ∈ F for each

n ≥ 1, A ∈ F, a1 ¤ a2 ¤ a3 ¤ . . . and an < A for each n. Write E = {an :

n ≥ 1}. Show that E has a supremum, a say, and that an ’ a.

3.2 The Bolzano-Weierstrass theorem

This section is devoted to the following important result.

38 A COMPANION TO ANALYSIS

Theorem 3.2.1. (Bolzano-Weierstrass.) If xn ∈ R and there exists a K

such that |xn | ¤ K for all n, then we can ¬nd n(1) < n(2) < . . . and x ∈ R

such that xn(j) ’ x as j ’ ∞.

Mathematicians say a sequence converges if it tends to a limit. The

Bolzano-Weierstrass theorem thus says that every bounded sequence of reals

has a convergent subsequence. Notice that we say nothing about uniqueness;

if xn = (’1)n then x2n ’ 1 but x2n+1 ’ ’1 as n ’ ∞.

Exercise 3.2.2. (i) Find a sequence xn ∈ [0, 1] such that, given any x ∈

[0, 1], we can ¬nd n(1) < n(2) < . . . such that xn(j) ’ x as j ’ ∞.

(ii) Is it possible to ¬nd a sequence xn ∈ [0, 1] such that, given any x ∈

[0, 1] with x = 1/2, we can ¬nd n(1) < n(2) < . . . and x ∈ R such that

xn(j) ’ x as j ’ ∞ but we cannot ¬nd m(1) < m(2) < . . . such that

xm(j) ’ 1/2 as j ’ ∞? Give reasons for your answer.

The proof of the Bolzano-Weierstrass theorem given in modern textbooks

depends on an ingenious combinatorial observation.

Lemma 3.2.3. If xn ∈ R, then at least one of the following two statements

must be true.

(A) There exist m(1) < m(2) < . . . such that xm(j) ≥ xm(j+1) for each

j ≥ 1.

(B) There exist n(1) < n(2) < . . . such that xn(j) ¤ xn(j+1) for each

j ≥ 1.

Exercise 3.2.4. Prove Theorem 3.2.1 from Lemma 3.2.3 and the fundamen-

tal axiom.

Proof of Lemma 3.2.3. Call an integer m ≥ 1 a ˜far seeing integer™ if xm ≥ xn

for all n ≥ m. (The term ˜far seeing™ is invented for use in this particular

proof and is not standard terminology.) There are two possibilities:

(A) There exist in¬nitely many far seeing integers. Thus we can can ¬nd

m(1) < m(2) < . . . such that each m(j) is far seeing and so xm(j) ≥ xm(j+1)

for each j ≥ 1.

(B) There are only ¬nitely many far seeing integers. Thus there exists

an N such that, if n ≥ N , there exists an n > n with xn > xn and so, in

particular, xn ≥ xn . Thus, given n(j) ≥ N , we can ¬nd n(j + 1) > n(j)

with xn(j) ¤ xn(j+1) . Proceeding inductively, we obtain n(1) < n(2) < . . .

with xn(j) ¤ xn(j+1) for each j ≥ 1.

I admit that the proof above is very clever but I feel that clever proofs

should only be used when routine proofs do not work. Here is a proof of the

Bolzano-Weierstrass theorem by lion hunting.

39

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise 3.2.5. We assume the hypotheses of Theorem 3.2.1. Set [a0 , b0 ] =

[’K, K]. Show that we can ¬nd a sequence of pairs of points an and bn such

that

xm ∈ [an , bn ] for in¬nitely many values of m,

an’1 ¤ an ¤ bn ¤ bn’1 ,

and bn ’ an = (bn’1 ’ an’1 )/2,

for all n ≥ 1.

Show that an ’ c as n ’ ∞ for some c ∈ [a0 , b0 ]. Show further that

we can ¬nd m(j) with m(j + 1) > m(j) and xm(j) ∈ [aj , bj ] for each j ≥ 1.

Deduce the Bolzano-Weierstrass theorem.

Exercise 3.2.5 links directly with the origins of the theorem. Proof by

successive bisection (our ˜lion hunting™) was invented by Bolzano and used

by Weierstrass to prove Theorem 3.2.1.

Here is another natural proof of Theorem 3.2.1 this time using a supre-

mum argument.

Exercise 3.2.6. We assume the hypotheses of Theorem 3.2.1. Explain why

yn = sup{xm : m ≥ n}

is well de¬ned. Show that the yn form a decreasing sequence bounded below

and conclude that yn tends to a limit y.

Show carefully that we can ¬nd n(j) with n(j + 1) > n(j) such that

|y ’ xn(j) | < j ’1 . Deduce the Bolzano-Weierstrass theorem.

The y of Exercise 3.2.6 is called lim supn’∞ xn . More formally we have

the following de¬nition.

De¬nition 3.2.7. If xn is a sequence of real numbers which is bounded above

we write

lim sup xn = lim sup{xm : m ≥ n}.

n’∞

n’∞

Exercise 3.2.8. Let xn be a bounded sequence of real numbers.

(i) De¬ne lim inf n’∞ xn by analogy with lim sup, showing that lim inf n’∞ xn

exists.

(ii) Show that lim inf n’∞ xn = ’ lim supn’∞ (’xn ).

(iii) Show that lim inf n’∞ xn ¤ lim supn’∞ xn .

(iv) Show that lim inf n’∞ xn = lim supn’∞ xn if and only if xn tends to

a limit.

40 A COMPANION TO ANALYSIS

(v) If n(1) < n(2) < . . . and xn(j) ’ x as j ’ ∞ show that

lim inf xn ¤ x ¤ lim sup xn .

n’∞ n’∞

(vi) If lim inf n’∞ xn ¤ x ¤ lim supn’∞ xn , does it follow that there

exist n(1) < n(2) < . . . such that xn(j) ’ x as j ’ ∞? Give a proof or

counterexample.

(vii) Show that y = lim supn’∞ xn if and only if both the following con-

ditions hold.

(A) Given > 0 we can ¬nd an N ( ) such that xn < y + for all

n ≥ N ( ).

(B) Given > 0 and N we can ¬nd n(N, ) ≥ N such that xn(N, ) > y’ .

State and prove a similar result for lim inf.

Although we mention lim sup from time to time, we shall not make great

use of the concept.

The reader will not be surprised to learn that the Bolzano-Weierstrass

theorem is precisely equivalent to the fundamental axiom.

Exercise 3.2.9. Suppose that F is an ordered ¬eld for which the Bolzano-

Weierstrass theorem holds (that is, every bounded sequence has a convergent

subsequence). Suppose that an is an increasing sequence bounded above. Use

the Bolzano-Weierstrass theorem to show that there exists an a ∈ F and

n(1) < n(2) < . . . such that an(j) ’ a as j ’ ∞. Show that an ’ a as

n ’ ∞ and so F obeys the fundamental axiom.

We illustrate the use of the Bolzano-Weierstrass theorem by applying it

to the familiar example of the intermediate value theorem.

Theorem 3.2.10. We work in R. If f : [a, b] ’ R is continuous and f (a) ≥

0 ≥ f (b), then there exists a c ∈ [a, b] such that f (c) = 0.

Proof. Our proof will have three labelled main parts which may be compared

with those in ˜lion hunting proof™ on page 15 and the ˜supremum proof™ on

page 34.

Part A Without loss of generality, we may suppose a = 0 and b = 1. Consider

the real numbers f (0), f (1/n), f (2/n), . . . , f (1). Since f (0) ≥ 0 and f (1) ¤

0 there must exist an integer r with 0 ¤ r ¤ n ’ 1 such that f (r/n) ≥ 0 ≥

f ((r + 1)/n). Set xn = r/n.

Part B Since the xn ∈ [0, 1], they form a bounded sequence and so, by the

Bolzano-Weierstrass theorem, we can ¬nd a c ∈ [0, 1] and n(1) < n(2) < . . .

such that xn(j) ’ c as j ’ ∞.

41

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Part C Since f is continuous and xn(j) ’ c, it follows that f (xn(j) ) ’ f (c)

as j ’ ∞. Since f (xn(j) ) ≥ 0, it follows that f (c) ≥ 0.

By the axiom of Archimedes, xn(j) + n(j)’1 ’ c so f (xn(j) + n(j)’1 ) ’

f (c) as j ’ ∞. Since f (xn(j) + n(j)’1 ) ¤ 0 it follows that f (c) ¤ 0.

Combining this result with that of the paragraph above, we obtain f (c) = 0

as required.

Exercise 3.2.11. Produce a version of the proof just given in which we do

not assume that a and b take particular values.

Exercise 3.2.12. Extend Exercise 3.1.13 to cover the ˜Bolzano-Weierstrass™

argument as well.

Let us summarise the proof just given. In Part A we construct a sequence

of points xn which look ˜more and more promising™. In Part B we use the fact

that every bounded sequence has a convergent subsequence to give a point

which ˜ought to be very promising indeed™. Finally in Part C we examine the

point c to make sure that it really has the desired property.

Let us see what goes wrong if we omit parts of the hypotheses of Theo-

rem 3.2.10. If we omit the condition f (a) ≥ 0, f (b) ¤ 0 then we cannot even

start Part A of the argument.

If we have f (a) ≥ 0 ≥ f (b) but replace R by another ordered ¬eld

for which the Bolzano-Weierstrass theorem does not hold then Part A goes

through perfectly but Part B fails. As usual this is shown by Example 1.1.3.

If we have f (a) ≥ 0 ≥ f (b) and we work over R but we do not demand f

continuous then Part C fails.

Exercise 3.2.13. Let f : [0, 1] ’ R Show that, if f (1)’f (0) ≥ L, then there

must exist an integer r with 0 ¤ r ¤ n ’ 1 such that f ((r + 1)/n) ’ f (r/n) ≥

L/n.

By imitating the proof of Theorem 3.2.10, give a Bolzano-Weierstrass

proof of Lemma 1.7.4 and thus of Theorem 1.7.1 (the mean value inequality).

Exercise 3.2.14. In this exercise you may use the axiom of Archimedes and

the fact that any non-empty bounded set of integers has a maximum.

(i) Let E be a non-empty set of real numbers which is bounded above

(that is there exists a K such that K ≥ x whenever x ∈ E). If n is a strictly

positive integer show that there exists an integer r such that

there exists an e ∈ E with e ≥ r/n

but (r + 1)/n ≥ x whenever x ∈ E.

(ii) Arguing in the manner of the proof of Theorem 3.2.10, show, using

the Bolzano-Weierstrass theorem, that E has a supremum.

42 A COMPANION TO ANALYSIS

3.3 Some general remarks

We have now obtained three di¬erent but equivalent forms of the fundamental

axiom (the fundamental axiom itself, the existence of a supremum for a non-

empty bounded set, and the Bolzano-Weierstrass theorem) and used methods

based on these three forms to prove the intermediate value theorem and the

mean value inequality (themselves equivalent to the fundamental axiom). I

make no excuse for the time we have spent on this programme. All of analysis

rests like an inverted pyramid on the fundamental axiom so it makes sense

to study it closely.

For reasons which will become clear in the next chapter, we will rely most

strongly on ˜Bolzano-Weierstrass™ techniques. However, there will be several

places where we prefer ˜supremum methods™. Exercises K.118 to K.121 show

that lion hunting is useful in theory of integration and, although it lies outside

the scope of this book, it should be remarked that the standard proof of

Cauchy™s theorem, on which complex analysis is based, relies on lion hunting.

There is a fourth method of exploiting the fundamental axiom based on

˜Heine-Borel™ or ˜compactness™ which is not discussed here (see Exercises K.29

to K.36, which are intended to be done after reading Chapter 4) but which,

when she does meet it, the reader should consider in the context of this

chapter.

Whenever we use one of these techniques it is instructive to see how the

others could have been used. (Often this is easy but occasionally it is not.)

It is also worth bearing in mind that, whenever we genuinely need to use one

of these methods or some theorem based on them, we are using the basic

property of the reals. Everything that depends on the fundamental axiom is

analysis ” the rest is mere algebra.

However, the reader should also remember most of the di¬culties in anal-

ysis are resolved not by the precise manipulation of axioms but by the clear

understanding of concepts.

Chapter 4

Higher dimensions

4.1 Bolzano-Weierstrass in higher dimensions

In 1908, Hardy wrote a textbook to introduce the new rigorous analysis (or

˜continental analysis™ as it was known in a Cambridge more insular than

today) to ˜¬rst year students at the Universities whose abilities approach

something like what is usually described as “scholarship standard” ™. Apart

from the fact that even the most hardened analyst would now hesitate to

call an introduction to analysis A Course of Pure Mathematics [23], it is

striking how close the book is in both content and feel to a modern ¬rst

course in analysis. (And, where there are changes, it is often not clear that

the modern course1 has the advantage.) One major di¬erence is that Hardy

only studies the real line but later advances in mathematics mean that we

must now study analysis in Rm as well.

We start with some algebra which is probably very familiar to most of

my readers. If x, y ∈ Rm , we de¬ne the inner product (or dot product) x · y

of the two vectors by

m

x·y = xj yj .

j=1

(We shall sometimes use the alternative notation x, y = x · y. Many texts

use the notation x.y = x · y.)

Lemma 4.1.1. If x, y, z ∈ Rm and » ∈ R then

(i) x · x ≥ 0 with equality if and only if x = 0,

1

Indeed, anyone who works through the exercises in Hardy as a ¬rst course and the

exercises in Whittaker and Watson™s even older A Course of Modern Analysis [47] as a

second will have had a splendid education in analysis.

43

44 A COMPANION TO ANALYSIS

(ii) x · y = y · x,

(iii) (»x) · y = »(x · y),

(iv) (x + y) · z = x · z + y · z.

Proof. Direct calculation which is left to the reader.

Since x · x ≥ 0 we may de¬ne the ˜Euclidean norm of x™ by

x = (x · x)1/2

where we take the positive square root.

Lemma 4.1.2. (The Cauchy-Schwarz inequality.) If x, y ∈ Rm then

|x · y| ¤ x y .

Proof. If x = 0, then x = 0, so x · y = 0 and the inequality is trivial. If

not, we observe that

0 ¤ (»x + y) · (»x + y)

= »2 x 2 + 2»x · y + y 2

2

(x · y)2

x·y 2

’

= »x + +y .

x2

x

If we now set » = ’(x · y)/ x 2 , this gives us

(x · y)2

2

0¤ y ’ ,

x2

which, after rearrangement and taking square roots, gives the desired result 2 .

Exercise 4.1.3. Although the proof just given is fairly detailed, it is a worth-

while exercise to extend it so that all the steps are directly justi¬ed by reference

to the properties of the inner product given in Lemma 4.1.1.

We can now obtain the standard properties of the Euclidean norm.

2

The reader may ask why we do not ˜simply™ say that x · y = x y cos θ where θ is

the angle between the vectors x and y. The Cauchy-Schwarz inequality is then ˜simply™

the statement that | cos θ| ¤ 1. However, our program is to deduce all of analysis from a

limited set of statements about R. We have not yet discussed what ˜cos™ is to be and, even

more importantly what the ˜angle between two vectors™ is to mean. When we ¬nally reach

a de¬nition of angle in Exercise 5.5.6, the reader will see that we have actually reversed