that ( 5 ’ 1)/2 and its relatives are indeed the ˜worst approximable™ num-

bers. (Chapter X of [25] deals with continued fractions and Chapter XI with

problems of approximation by rationals.) We discussed a related problem in

Exercise K.12.

Exercise K.15. (L´vy™s universal chord theorem.) [1.6, P] Suppose

e

f : [0, 1] ’ R is continuous and f (0) = f (1). By considering the function

g : [0, 1/2] ’ R de¬ned by g(x) = f (x + 1 ) ’ f (x) show that there exist

2

1

a, b ∈ [0, 1] such that b ’ a = 2 and f (b) = f (a). Show, more generally, that

1

there exist ±n , βn ∈ [0, 1] such that βn ’ ±n = n and f (βn ) = f (±n ). (This is

L´vy™s universal chord theorem. For more discussion, including a proof that

e

1

you cannot replace n by a more general h, see [8], page 109.)

Show that we can ¬nd an , bn ∈ [0, 1] such that an ¤ an+1 < bn+1 ¤ bn ,

bn ’ an = 2’n and f (bn ) = f (an ).

Now suppose that δ > 0, that f is de¬ned on the larger interval (’δ, 1+δ)

and f : (’δ, 1+δ) ’ R is everywhere di¬erentiable. Show that if f (0) = f (1),

then there exists a c ∈ [0, 1] such that f (c) = 0. (A little extra thought gives

the full Rolle™s theorem (Theorem 4.4.4).)

Exercise K.16. [1.6, P] Suppose that f : [a, b] ’ R is increasing and

g : [a, b] ’ R is continuous. Show that, if f (a) ≥ g(a) and f (b) ¤ g(b), then

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

Is it necessarily true that, if f (a) ¤ g(a) and f (b) ≥ g(b), then there

exists a c ∈ [a, b] such that f (c) = g(c). Is the result of the ¬rst paragraph

true if we replace ˜g continuous™ by ˜g decreasing™ ? Is the result of the ¬rst

paragraph true if we replace ˜f increasing™ by ˜f continuous™ ? Give proofs

or counterexamples as appropriate.

Exercise K.17. [3.1, P] Let c ∈ (a, b). Suppose fn : (a, b) ’ R is continu-

ous at c for each n ≥ 1.

Show that, if g : (a, b) ’ R is given by

g(x) = max(f1 (x), f2 (x), . . . , fN (x)),

then g is continuous at c, but show, by means of an example, that, even if

there exists a K such that |fn (x)| ¤ K for all n and all x ∈ (a, b), if we de¬ne

G : (a, b) ’ R by

G(x) = sup(f1 (x), f2 (x), . . . ),

then G need not be continuous at c.

442 A COMPANION TO ANALYSIS

Exercise K.18. [3.1, P] (This requires good command of the notion of

countability)

(i) Suppose that E is a bounded uncountable set of real numbers. Show

that there exist real numbers ± and β with ± < β such that both of the sets

{e ∈ E : e < γ} and {e ∈ E : e > γ}

are uncountable if and only if ± < γ < β.

(ii) State and prove the appropriate version of (ii) if we omit the condition

that E be bounded.

(iii) Give an example of a bounded in¬nite set E of real numbers such

that there does not exist a real γ with both of the sets

{e ∈ E : e < γ} and {e ∈ E : e > γ}

in¬nite.

Exercise K.19. [3.2, P] Consider a sequence of real numbers xn . Which of

the following statements are always true and which are sometimes true and

sometimes false? Give proofs or examples.

(i) There is a strictly increasing subsequence. (That is, we can ¬nd n(j)

with n(j + 1) > n(j) and xn(j+1) > xn(j) for all j ≥ 1.)

(ii) There is an increasing subsequence. (That is, we can ¬nd n(j) with

n(j + 1) > n(j) and xn(j+1) ≥ xn(j) for all j ≥ 1.)

(iii) If there is no increasing subsequence, there must be a strictly de-

creasing subsequence.

(iv) If there is no strictly increasing subsequence and no strictly decreasing

subsequence, then we can ¬nd an N such that xn = xN for all n ≥ N .

Exercise K.20. [3.2, P] (i) Suppose that an is a bounded sequence of real

numbers. Show that, if n(p) ’ ∞ as p ’ ∞ and an(p) ’ a, then

lim sup an ≥ a ≥ lim inf an .

n’∞

n’∞

(ii) Suppose that lim supn’∞ an = 1 and lim inf n’∞ an = 0. Show, by

means of examples, that it may happen that 1 and 0 are the only numbers

which are the limits of convergent subsequences of the an or it may happen

that every a with 0 ¤ a ¤ 1 is such a limit. [You may wish to investigate

precisely what sets can occur, but you will need the notion of a closed set.]

(iii) Suppose that an and bn are bounded sequences of real numbers.

Show, by means of an example, that the equation

?

lim sup(an + bn ) = lim sup an + lim sup bn

n’∞ n’∞ n’∞

443

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

need not hold. By giving a proof or a counterexample, establish whether the

following relation always holds.

?

lim sup(an + bn ) ≥ lim sup an + lim inf bn .

n’∞

n’∞ n’∞

Exercise K.21. (Ptolomey™s inequality.) [4.1, S] We work in a vector

x y

’

space with inner product. By squaring and rewriting the

x2 y2

result, or otherwise, prove Ptolomey™s inequality

x’y z ¤ y’z x + z’x y.

Exercise K.22. [4.2, P] We use the standard Euclidean norm on Rn and

Rn+1 . Which of the following statements are true and which are false? Give

proofs or counterexamples as appropriate.

(i) If E is a closed subset of Rn+1 then

{x ∈ Rn : (0, x) ∈ E}

is closed in Rn .

(ii) If U is an open subset of Rn+1 then

{x ∈ Rn : (0, x) ∈ U }

is open in Rn .

(iii) If E is a closed subset of Rn then

{(0, x) : x ∈ E}

is closed in Rn+1 .

(iv) If U is an open subset of Rn then

{(0, x) : x ∈ U }

is open in Rn+1 .

Exercise K.23. [4.2, T] We can extend De¬nition 4.2.20 as follows.

Let E ⊆ Rm , A ⊆ E, x ∈ E and l ∈ Rp Consider a function f : E \ {x} ’

Rp . We say that f (y) ’ l as y ’ x through values of y ∈ A if, given > 0,

we can ¬nd a δ( , x) > 0 such that, whenever y ∈ A and 0 < x’y < δ( , x),

we have

f (y) ’ l < .

444 A COMPANION TO ANALYSIS

(i) Let E ⊆ Rm , A ⊆ E, x ∈ E and l ∈ Rp Consider a function f :

E \ {x} ’ Rp . Show that if A is ¬nite (this includes the case A = …), then,

automatically, f (y) ’ l as y ’ x through values of y ∈ A.

(ii) Let E ⊆ Rm , A ⊆ E, x ∈ E and l ∈ Rp Consider a function f :

E \ {x} ’ Rp such that f (y) ’ l as y ’ x through values of y ∈ A. Show

that, if B ⊆ A, then f (y) ’ l as y ’ x through values of y ∈ A.

(iii) Let E ⊆ Rm , A ⊆ E, B ⊆ E, x ∈ E and l ∈ Rp . Consider a function

f : E \ {x} ’ Rp such that f (y) ’ l as y ’ x through values of y ∈ A and

f (y) ’ l as y ’ x through values of y ∈ B. Show that f (y) ’ l as y ’ x

through values of y ∈ A ∪ B.

Exercise K.24. [4.2, P] We work in R2 . The projections π1 , π2 : R2 ’ R

are de¬ned by π1 (x, y) = x and π2 (x, y) = y.

(i) Show that E = {(x, 1/x) : x > 0} is a closed set in R2 such that

π1 (E) is not closed.

(ii) Find a closed set E in R2 such that π2 (E) is closed, but π1 (E) is not

closed.

(iii) Show, however, that if E is a closed set in R2 with π2 (E) bounded,

then π1 (E) must be closed.

Exercise K.25. [4.2, P] Let E ⊆ Rn and let f : E ’ Rm be function. We

call

G = {(x, f (x)) : x ∈ E}

the graph of f .

(i) Show that, if G is closed, then E is. Show that, if G is bounded, then

E is.

(ii) Show that, if E is closed and f is continuous, then G is closed.

(iii) Show that G may be closed but f discontinuous. (Look at Exer-

cise K.24 if you need a hint.)

(iv) Show that, if G is closed and bounded, then f is continuous.

Exercise K.26. [4.3, P] Let E ⊆ Rn . A function f : E ’ R is said to be

upper semi-continuous on E if, given any x ∈ E and any > 0, we can ¬nd

a δ( , x) > 0 such that f (y) < f (x) + for all y ∈ E with y ’ x < δ( , x).

Give an example of a function f : [’1, 1] ’ R which is upper semi-continuous

on [’1, 1] but not continuous. If E ⊆ Rn and f : E ’ R is such that both

f and ’f are upper semi-continuous on E, show that f is continuous on E.

If K ⊆ Rn is closed and bounded and f : K ’ R is upper semi-

continuous, show that f is bounded above and attains its least upper bound.

Is it necessarily true that f is bounded below? Is it necessarily true that,

if f is bounded below, it attains its greatest lower bound? Give proofs or

counterexamples as appropriate.

445

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

Exercise K.27. [4.3, H, S] Suppose that f : (a, b) ’ R is a function with

continuous derivative f . The object of this question is to show, using the

mean value inequality (Theorem 1.7.1), that, if f (t) > 0 for all t ∈ (a, b), then

f is strictly increasing on (a, b). (We prove a stronger result in Lemma 4.4.2

using Theorem 4.4.1.)

To this end, suppose a < x < y < b.

(i) Using the fact that a continuous function on a closed bounded interval

is bounded and attains its bounds, show that there exists an m > 0 such

that f (t) ≥ m for all t ∈ [x, y].

(ii) Hence, using the mean value inequality or one of its corollaries, show

that f (y) ’ f (x) ≥ m(y ’ x) > 0.

Exercise K.28. [4.3, T!] Suppose x1 , x2 , . . . are real numbers. Show that

we can ¬nd closed intervals Kn = [an , bn ] (where bn > an ) such that xn ∈ /

Kn for all n ≥ 1 but Kn ⊆ Kn’1 for n ≥ 2. By applying the result of

Exercise 4.3.8 show that there exist a real y with y = xn for all n (i.e. the

reals are uncountable).

[The method of this exercise is quite close to that of Cantor™s original proof.]

Exercise K.29. [4.3, T] This easy question introduces a concept that will

be used in other questions. We say that a non-empty collection A of subsets

of some set X has the ¬nite intersection property if, whenever n ≥ 1 and

A1 , A2 , . . . , An ∈ A, we have n Aj = ….

j=1

(i) Fix N and let A(1) be the collection of subsets A of Z such that

A © {1, 2, 3, . . . , N, N + 1} has at least N members.

If A1 , A2 , . . . , AN ∈ A(1) show that N Aj = …. Show, however, that A(1)

j=1

does not have the ¬nite intersection property.

(ii) Let A(2) be the collection of subsets A of Z such that N \ A is ¬nite.

Show that A(2) has the ¬nite intersection property but A∈A(2) A = ….

(iii) (Requires countability.) Let A(3) be the collection of subsets A of R

such that R\A is ¬nite. Show that if A1 , A2 , · · · ∈ A(3) then ∞ Aj = … (so

j=1

that, in particular, A(3) has the ¬nite intersection property) but A∈A(3) A =

….

(iv) Let A(4) be the collection of subsets A of Z of the form

A = {kr : r ≥ 1}

for some k ≥ 1. Show that A(4) has the ¬nite intersection property but

A∈A(4) A = ….

446 A COMPANION TO ANALYSIS

Exercise K.30. [4.3, T] Suppose ± : Rn ’ Rn is a linear map which is self

adjoint, that is to say, such that

±(x) · y = x · (±y)

for all x, y ∈ Rn . (We use the standard inner product notation.)

(i) Show that the map f : Rn ’ R given by f (x) = x · ±x is continuous.

Hence, stating carefully any theorem that you use, show that there is an

e ∈ Rn with e = 1 such that

e · (±e) ≥ x · (±x),

whenever x = 1.

(ii) If e is as in (i), deduce that if e · h = 0 then

(1 + δ 2 )e · (±e) ≥ (e + δh).(±(e + δh))

for all real δ. By considering what happens when δ is small, or otherwise,

show that

e · (±h) + h · (±e) = 0

and so h · (±e) = 0.

(iii) In (ii) we showed that h · (±e) = 0 whenever e · h = 0. Explain why

this tells us that ±e = »e for some real » and so the vector e found in (i) is

an eigenvector.

(iv) Let U = {h : e · h = 0}. Explain why U is an n ’ 1 dimensional

subspace of V and ±(U ) ⊆ U . If β = ±|U , the restriction of ± to U , show that

β is self adjoint. Hence use induction to show that Rn has an orthonormal

basis e1 , e2 , . . . , en of eigenvectors of ±.

Exercise K.31. [4.3, T!] (i) Suppose that E is a subspace of Rn and y ∈ E.

/

Show that the map g : E ’ R given by

g(x) = x ’ y

is continuous. Hence, show carefully (note that, except in the trivial case

E = {0}, E itself is not bounded) that there exists a x0 ∈ E such that

x ’ y ≥ x0 ’ y

for all x ∈ E.

(ii) Show that x0 ’ y is perpendicular to E (that is (x0 ’ y) · x = 0

for all x ∈ E). (See Exercise K.30 (ii), if you need a hint.) Show that

x ’ y > x0 ’ y for all x ∈ E with x = x0 (in other words, x0 is unique).

447

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

(iii) Suppose that ± : Rm ’ R is linear and ± = 0. By setting

E = {x : ±x = 0}

and choosing an appropriate y, show that there exists an b, perpendicular to

E, with ±b = 0. Hence show that there exists a unit vector a, perpendicular

to E, with ±a = 0. By considering the e¬ect of ± on the vector x ’ (a · x)a,

show that

±x = a · x

for all x ∈ Rm .

Exercise K.32. (Hahn-Banach for Rn . [4.3, T!, ‘ ] This exercise extends

some of the ideas of Exercise K.31. Recall that a set E in Rm is called convex

if, whenever e1 , e2 ∈ E, and » ∈ [0, 1] we have »e1 + (1 ’ »)e2 ∈ E (in other

words, if two points lie in E, so does the chord joining them).

(i) Suppose that E is a non-empty closed convex set Rm and y ∈ E. Show

/

that there exists a x0 ∈ E such that

x ’ y ≥ x0 ’ y

for all x ∈ E.

(ii) Suppose that x0 = 0. Show that there exists a b such that x · b ¤ 0

for all x ∈ E but b · y > 0.

(iii) Returning to the general case, when all we know is that E is a non-

empty closed convex set Rm and y ∈ E, show that there exists an a ∈ Rm

/

and a real number c such that x · a ¤ c for all x ∈ E but a · y > c. (Results

like this are called Hahn-Banach type theorems.)

Exercise K.33. (Extreme points.) [4.3, T!, ‘ ] Here is an application of

Exercise K.32.

(i) Throughout this question K is a non-empty closed bounded convex

set in Rn . We say that a point z ∈ K is an extreme point for K, if, whenever

x, y ∈ K, 1 > » > 0 and »x + (1 ’ »)y = z, then x = y = z.

Show that the extreme points of the closed unit ball {x ∈ Rn : x ¤ 1}

are precisely those points z ∈ Rn with z = 1. Show that the extreme

points of the closed cube [’1, 1]n are precisely the 2n points (z1 , z2 , . . . , zn )

with |zj | = 1.

(ii) Suppose w ∈ K. By using Exercise K.32, show that there exists an

/

a ∈ R and a real number c such that x · a ¤ c for all x ∈ K but a · w > c.

n

Quoting carefully any theorems that you use, show that there exists a x0 ∈ K

such that x · a ¤ x0 · a for all for all x ∈ K.

448 A COMPANION TO ANALYSIS

Show that

K = {u : x0 + u ∈ K and u · a = 0}

is a non-empty closed convex subset of an n ’ 1 dimensional subspace of Rn .

Show further that, if u0 is an extreme point of K , then x0 + u0 is an extreme

point of K.

(iii) By using induction on the dimension n, or otherwise, show that every

non-empty closed bounded convex set in Rn contains an extreme point.

(iv) Suppose that T : Rn ’ R. Explain why there exists an x0 ∈ K such

that T (x0 ) ≥ (x) for all x ∈ K. By considering extreme points of the set

{x ∈ K : T (x) = T (x0 )},

or otherwise, show that there exists an extreme point e of K with T (e) =

T (x0 ). Thus every linear map T : Rn ’ R attains its maximum on a closed

bounded convex set at some extreme point of that set. This observation is

the foundation of the theory of linear optimisation.

(v) Suppose that L is a non-empty closed convex subset of K. If L = K

(so that there exists a w ∈ K with w ∈ L) use the ideas of (ii) to show that

/

there exists an extreme point of K which does not lie in L.

Exercise K.34. (Krein-Milman for Rn .) [4.3, T!, ‘ ] We continue with

the ideas of Exercise K.33.

(i) If L is a collection of convex sets in Rn , show that L∈L L is convex.

If M is a collection of closed convex sets in Rn , show that M ∈M M is a

closed convex set.

(ii) Explain why Rn is a closed convex set. If A is a subset of Rn , we

write

{L ⊇ A : L is closed and convex}

hull(A) =

and call hull(A) the closed convex hull of A. Show that hull(A) is indeed

closed and convex and that hull(A) ⊇ A. Show also that, if B is a closed

convex set with B ⊇ A, then B ⊇ hull(A).

[This argument parallels the standard approach to the closure and interior

set out in Exercise K.179.]

(iii) Use (ii) and part (v) of Exercise K.33 to show that the closed convex

hull of the set E of extreme points of a non-empty bounded closed convex

subset K of Rn is the set itself. (More brie¬‚y hull(E) = K.) Results of this

kind are known as Krein-Milman theorems.

449

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

Exercise K.35. [4.3, T, ‘ ] We work in R. Let K be a collection of closed

sets lying in some closed interval [a, b] and suppose that K has the ¬nite

intersection property (see Exercise K.29).

(i) If a ¤ c ¤ b and we write

K1 = {K © [a, c] : K ∈ K} and K2 = {K © [c, b] : K ∈ K},

show that at least one of K1 and K2 must have the ¬nite intersection property.

(ii) Use lion hunting to show that K∈K K = ….

Exercise K.36. (The Heine-Borel theorem.) [4.3, T, ‘ ] We work in

Rm . Consider the following two statements.

(A) Let R > 0. If a collection K of closed sets lying in [’R, R]m has the

¬nite intersection property then K∈K K = ….

(B) Let E be a bounded closed set. If a collection U of open sets is such

that U ∈U U ⊇ E, then we can ¬nd an n ≥ 1 and U1 , U2 , . . . , Un ∈ U such

that n Un ⊇ E.

j=1

(i) By considering sets of the form K = E \ U deduce statement (B) from

statement (A). Deduce statement (A) from statement (B).

(ii) Prove statement (A) by a lion hunting argument along the lines of

Exercises K.35 and 4.1.14. It follows from (i) that (B) holds. This result is

known as the theorem of Heine-Borel1 .

(iii) Explain why Exercise 4.3.8 is a special case of statement (A).

(iv) Suppose that E is a set with the properties described in the second

sentence of statement (B). Show that E is closed and bounded.

[Hint. To show E is closed, suppose x ∈ E and consider sets U of the form

/

U = {y : r > x ’ y > 1/r}

with r > 1.]

Exercise K.37. [4.3, H, ‘ ] (This complements Exercise K.35.) Suppose

that F is an ordered ¬eld with the following property.

(A) Whenever K is a collection of closed sets lying in some closed interval

[a, b] and K has the ¬nite intersection property it follows that K∈K K = ….