used the idea of countability to give a new proof of this.

Let Aj be the set of all real roots of all polynomials P (t) = n ar tr such

r=0

that ar ∈ Z [0 ¤ r ¤ n], an = 0 and n ≥ 1 and

n

|ar | ¤ j.

n+

r=0

By considering properties of the Aj , show that the set of algebraic numbers

is countable. Deduce that not all real numbers are algebraic.

Exercise B.8. (i) A set S of non-negative real numbers is such that there

exists a positive constant K such that

x<K

x∈T

386 A COMPANION TO ANALYSIS

for every ¬nite subset T of S. Prove that the set of non-zero elements of S

is countable.

(ii) A set S of real numbers is such that, whenever a1 , a2 , . . . are distinct

members of S,

∞

an converges.

n=1

∞

Show that we can ¬nd b1 , b2 , . . . such that n=1 bn is absolutely convergent

and

S ⊆ {0} ∪ {bn : n ≥ 1}.

Exercise B.9. Consider a function f : (a, b) ’ R. Recall that we say that

c is a strict maximum (or strict local maximum) of f if we can ¬nd ± and β

such that a ¤ ± < c < β ¤ b such that

f (x) < f (c) for all x ∈ (±, β) with x = c.

By associating each such c with an interval with rational end points, or oth-

erwise, show that the set E of strict maxima is countable.

Give an example to show that E can be in¬nite.

Does the result remain true if we replace (a, b) by the real line R? Does an

appropriate version of the result (to be stated) remain true if we replace (a, b)

by R2 ? Does the result remain true if we replace ˜strict maxima™ by ˜maxima™

(that is, replace f (x) < f (c) in the de¬ning condition by ˜f (x) ¤ f (c)™)?

It is worth remarking that Exercise B.7 re¬‚ects a general principle.

Plausible statement B.10. The set of real numbers that we can describe

in any way is countable.

Plausible argument. I have only a ¬nite number N of symbols on my type-

writer. Thus the set Aj of real numbers that I can describe using j keystrokes

has at most N j members. Since Aj is ¬nite and so countable, we see that

the set ∞ Aj of real numbers that I can describe in any way is countable.

j=1

The reader should be warned that there are severe philosophical and math-

ematical obstacles in the way of any attempt to make precise the statement

and argument above. Never the less, most mathematicians are inclined to

accept the general thrust of the argument. When we talk about R we are

talking about a set most of whose members we can not describe.

Here is another reason to prefer rigour to intuition.

Appendix C

The care and treatment of

counterexamples

Mathematics students dislike questions beginning ˜¬nd a proof or counterex-

ample™. They know that it is much harder to prove or disprove a result if

you are not sure which of the two possible outcomes will occur.

In research we are faced with many uncertainties. We do not know

whether our problem is easy, hard or beyond our capabilities (whereas in

an exam we know that the problems will not exceed a certain level of dif-

¬culty). We often do not know if the solution of a particular problem will

open a path to further progress or turn out to be a dead end. And, whatever

our suspicions or hopes, we do not know whether the result we seek is true

or false.

In these circumstances, mathematicians often adopt a two pronged attack.

First they try to prove the result. When their attack fails, they try to identify

the point where it fails and try to construct a counterexample centred round

the point of failure. If they cannot construct a counterexample they try to

identify the reason why they cannot do so and this may give them a hint

as to how get round their previous di¬culty in the proof. By alternating

between determined attempts to seek a proof and determined attempts to

¬nd a counterexample they hope to arrive at a useful result.

If their attack ends in a counterexample, the counterexample may suggest

how to strengthen hypotheses or weaken conclusions so as to produce a true

theorem.

If the attack ends in a theorem the matter does not ¬nish there. Ex-

amination questions and exercises such as are found in this book are made

easier by the fact that we know that all the information supplied is relevant.

We know that, in real life, problems are made much harder by an excess

387

388 A COMPANION TO ANALYSIS

of irrelevant information1 . We expect, sometimes wrongly but often rightly,

that a proof which depends on unnecessary hypotheses will be less clear

than one which only uses the essential hypotheses. Thus, once a theorem

is established, we usually embark on a systematic programme of weakening

hypotheses and strengthening conclusions, not only in the hope of obtaining

a stronger theorem but also in the hope of obtaining a better proof. A the-

orem is therefore frequently accompanied by a collection of counterexamples

showing that hypotheses cannot be weakened or conclusions strengthened.

What I have said so far is probably obvious to the reader and to most

students of mathematics. However many students fail to draw the obvious

moral. Since counterexamples are not ends in themselves but objects which

we study in the hope of obtaining positive results,

counterexamples should be as simple as possible.

Let me illustrate this slogan by considering the notion of continuity. The

¬rst question we must ask after de¬ning the notion of a continuous function

is whether all functions are continuous. Here is the simplest counterexample

I can think of.

Example C.1. If we de¬ne f : R ’ R by

f (t) = 0 for t = 0

f (0) = 1,

then f is not continuous at 0.

The reader may feel that this is arti¬cial since f can be rede¬ned at one

point (by setting f (0) = 0) in such a way as to make it continuous. We may

therefore ask for a function which cannot be so de¬ned.

Example C.2. If we de¬ne H : R ’ R by

H(t) = 0 for t < 0

H(t) = 1 for t > 0

H(0) = a,

then, whatever the value of the real number a, H is not continuous at 0.

1

Remember the old riddle. A bus sets out from a depot with only the driver on board.

At the ¬rst stop two people get on. At the next, three get on and one gets o¬. At the

next, ¬ve get on and two get o¬. At the next, four get o¬ and two get on. At the next

three get o¬ and two get on. At the next ¬ve get on and two get o¬. How many stops has

the bus made?

389

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

Proof. If f : R ’ R is continuous at 0 then

f (1/n) ’ f (’1/n) ’ f (0) ’ f (0) = 0

as n ’ ∞. Since

H(1/n) ’ H(’1/n) = 1 0

as n ’ ∞, H is not continuous at 0.

The discontinuity exhibited by H is of a particularly simple kind since the

right and left limits

H(0+) = lim H(t) and H(0’) = lim H(t)

t’0, t>0 t’0, t<0

exist. We may, therefore, ask if there exist functions without such left and

right limits.

Example C.3. If we de¬ne f : R ’ R by

f (t) = 1/t for t = 0

f (0) = 0,

then f has neither a left limit nor a right limit at 0.

We may feel that this is unsatisfactory and ask whether this phenomenon

can occur for a bounded function.

Example C.4. If we de¬ne f : R ’ R by

f (t) = sin(1/t) for t = 0

f (0) = 0,

then f is bounded and has neither a left limit nor a right limit at 0.

1

Proof. Observe that f (1/(2nπ)) = 0 ’ 0 but f (1/((2n + 2 )π) = 1 ’ 1 as

n ’ ∞. Thus f (t) does not tend to a limit as t ’ 0 through values of t > 0.

Similarly, f (t) does not tend to a limit as t ’ 0 through values of t < 0.

Exercise C.5. Find a bounded function f : R ’ R such that f (t) ’ f (0)

as t ’ 0 through values of t > 0 but f (t) does not tend to a limit as t ’ 0

through values of t < 0.

The next exercise is a trivial complementary observation with a one line

proof.

390 A COMPANION TO ANALYSIS

Exercise C.6. Show that if f : R ’ R is such that f (t) ’ f (0) as t ’ 0

through values of t > 0 and f (t) ’ f (0) as t ’ 0 through values of t < 0

then f is continuous at 0.

In view of Exercise C.6 we may ask if a function F : R2 ’ R is such

that F (ut) ’ F (0) as t ’ 0 for all unit vectors u then F is continuous at

0 = (0, 0). This is a harder question and, instead of sitting around trying

to think of a function which might provide a counterexample, we actively

construct one ˜by hand™.

Exercise C.7. (i) Let rn = 1/n and θn = π/(2n) and take

xn = (rn cos θn , rn sin θn ).

Show that we can ¬nd δn > 0 such that xn /2 > δn > 0 and, writing

Bn = {y : xn ’ y ¤ δn },

we know that the following statement is true. If u is any unit vector, the line

{tu : t ∈ R} intersects at most one of the Bn . Give a sketch to illustrate

your result.

(ii) Show that there exists a continuous function gn : Rn ’ R such that

gn (xn ) = 1,

for all y ∈ Bn .

gn (y) = 0 /

Explain why setting F (x) = ∞ gn (x) gives a well de¬ned function. Show

n=1

that F (ut) ’ F (0) as t ’ 0 for all unit vectors u but F is not continuous

at 0.

Exercise C.8. (This exercise requires material from Chapter 6.)

(i) Show that we can ¬nd a twice continuously di¬erentiable function h :

R ’ R such that

h(0) = 1,

for all |t| > 1/2

h(t) = 0

1 ≥ h(t) ≥ 0 for all t.

If δ > 0 and z ∈ R2 sketch the function g : R2 ’ R given by g(x) =

h(δ ’1 z ’ x ).

(ii) By taking F = ∞ n’1 gn with appropriately chosen gn (you will

n=1

need to be more careful in the choice than we were in the previous exercise),

show that there exists a continuous function F : R2 ’ R with directional

derivative zero in all directions at 0 but which is not di¬erentiable at 0.

(iii) Why is the result of Exercise C.8 stronger than that of Example 7.3.14?

[We give a slight strengthening of this result in Exercise K.314.]

391

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

Exercise C.9. Consider a function f : R2 ’ R.

(i) Show that f is continuous at 0 = (0, 0) if and only if, whenever we

have a sequence xn ’ 0, it follows that f (xn ) ’ f (0) as n ’ ∞.

(ii) Show that f is continuous at 0 if and only if, whenever we have a

continuous function γ : [0, 1] ’ R2 with γ(0) = 0, it follows that f (γ(t)) ’

f (0) as t ’ 0 through values of t > 0.

Thus, if f (x) tends to f (0) along every path leading to 0, then f is

continuous. However, as we have seen, the result fails if we replace ˜every

path™ by ˜every straight-line path™.

If we wish to understand the ways in which a function can fail to be

continuous at a point, it is surely more instructive to begin with the simple

Example C.1 rather than rush to the complicated Exercise C.7. In the same

way, if we wish to give an example of a continuous function which fails to

be di¬erentiable it is surely best to look at the function f : R ’ R given

by f (x) = |x|, rather than the fairly intricate construction of a continuous

nowhere di¬erentiable function given in Exercise K.223.

Proceeding from the simple to the complex as we did in studying dis-

continuity at a point has a further advantage that it gives us a number of

examples of functions to think about rather than just one. To quote Halmos

If I had to describe my conclusions [on how to study mathe-

matics] in one word, I™d say examples. They are to me of paramount

importance. Every time I learn a new concept (free group, or

pseudodi¬erential operator, or paracompact space) I look for ex-

amples ” and, of course, non-examples. The examples should

include, whenever possible, the typical ones and the extreme de-

generate ones. Yes, to be sure, R2 is a real vector space, but so

is the space of all real polynomials with real coe¬cients and the

set of all analytic functions de¬ned on the open disc ” and what

about the 0-dimensional case. Are there examples that satisfy

all the conditions of the de¬nition except 1x = x? Is the set of

all real-valued monotone increasing functions de¬ned on, say, the

unit interval a real vector space? How about all the monotone

ones, both increasing and decreasing . . .

A good stock of examples, as large as possible, is indispens-

able for a thorough understanding of any concept and when I

want to learn something new, I make it my ¬rst job to build one.

Sometimes to be sure, that might require more of the theory than

the mere de¬nition reveals. When we ¬rst learn about transcen-

dental numbers, for instance, it is not at all obvious that such

392 A COMPANION TO ANALYSIS

things exist. Just the opposite happens when we are ¬rst told

about measurable sets. There are plenty of them, there is no

doubt about that; what is less easy is to ¬nd a single example of

a set that is not like that2 . [The quotation is from I Want to be

a Mathematician[21], a book well worth reading in its entirety.]

This quotation brings me to my second point. Halmos talks about typical

examples and illustrates his remarks with the idea of a vector space. In some

sense typical vector spaces exist since we have the following classi¬cation

theorem from algebra.

Theorem C.10. A ¬nite dimensional vector space over R is isomorphic to

Rn for some positive integer n.

[There is a similar but duller result for in¬nite dimensional vector spaces.]

There is no such result for continuous functions and I suspect that, to

misquote Haldane ˜The typical continuous function is not only odder than we

imagine, it is odder than we can possibly imagine™3 . This is why mathemati-

cians demand so much rigour in proof. When we showed, in Theorem 4.3.4,

that every real-valued continuous function on a closed bounded set in Rn is

bounded and attains its bounds we proved a result which applied not only to

all continuous functions that we know but to all continuous functions that

the human race will ever know and to continuous functions which nobody

will ever know and, if my belief is right, to continuous functions which are

so wild as to be literally unimaginable4 .

Even if we restrict ourselves to well behaved functions, I would argue that

it is much harder than it looks to obtain a su¬ciently large library of typical

functions. (See Remark 4 on page 347.)

On the other hand, when we talk about an example or a counterexample

we are talking about a single object and we do not need the obsessive rigour

demanded by a proof which will apply to many objects. To show that a

unicorn exists we need only exhibit a single unicorn. To show that no unicorn

exists requires much more careful argument.

2

The set considered in Exercise 8.1.4 is an example. (T.W.K.)

3

In spite of Theorem C.10, this may be true of vector spaces as well. Conway used to

say that one dimension is easy, two harder, three very hard, four still harder, . . . , that

somewhere about twenty eight things became virtually impossible but once you reached

in¬nite dimensions things became easier again.

4

Since the 1890™s it has been known that there exist everywhere di¬erentiable functions

which take a strict local maximum value at a dense set of points. Until you read this

footnote, did you imagine that such a thing was possible? Can you imagine it now? For

a modern proof see [27].

393

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

Demonstrations involving a single known object can be much

simpler than those involving a multitude of unknown objects.

Appendix D

A more general view of limits

One of the more tedious parts of the standard treatment of analysis given in

this book is the repeated de¬nition of various kinds of limits. Here is a small

selection.

De¬nition D.1. If an is a sequence of real numbers and a is a real number,

we say that an ’ a as n ’ ∞ if, given any > 0, we can ¬nd an n0 ( ) such

that |a ’ an | < for all n > n0 ( ).

De¬nition D.2. If an is a sequence of real numbers and a is a real number,

we say that an ’ ∞ as n ’ ∞ if, given any K, we can ¬nd an n0 (K) such

that an > K for all n > n0 (K).

De¬nition D.3. If f : (a, b) ’ R is a function and t ∈ (a, b), we say that

f (x) ’ c as x ’ t if, given any > 0, we can ¬nd an δ0 ( ) such that

|f (x) ’ c| < for all x ∈ (a, b) with 0 = |t ’ x| < δ0 ( ).

De¬nition D.4. If f : (a, b) ’ R is a function and t ∈ (a, b), we say that

f (x) ’ c as x ’ t through values of x > t if, given any > 0, we can ¬nd

an δ0 ( ) such that and |f (x) ’ c| < for all x ∈ (a, b) with 0 < x ’ t < δ 0 ( ).

In theory, each of these de¬nitions should be accompanied by a collection

of lemmas showing that each limit behaves in the way every other limit

behaves. In practice, such lemmas are left to the reader. (In this book I have

tended to look most carefully at de¬nitions of the type of De¬nition D.1.)

Experience seems to show that this procedure works quite well, both from

the pedagogic and the mathematical point of view, but it is, to say the least,

untidy.

In his book Limits, A New Approach to Real Analysis [2], Beardon pro-

poses an approach based on directed sets which avoids all these di¬culties1 .

1

The notion of a directed set goes back to E. H. Moore in 1910 but Beardon™s is the

only elementary text I know which uses it.

395

396 A COMPANION TO ANALYSIS

Figure D.1: A family tree for division

For a mixture of reasons, some good and some not so good, the teaching of

elementary analysis is extremely conservative2 and it remains to be seen if

this innovation will be widely adopted.

De¬nition D.5. A relation on a non-empty set X is called a direction if

(i) whenever x y and y z, then x z, and

(ii) whenever x, y ∈ X, we can ¬nd z ∈ X such that z x and z y.

We call (X, ) a directed set.

Notice that we do not demand that ˜all points are comparable™, that is,

we do not demand that, if x = y, then either x y or y x. (You should

reread De¬nition D.5 bearing this in mind.) We will use this extra liberty in

Exercises D.14 and D.16.

Exercise D.6. Consider the set N+ of strictly positive integers. Write n

m if m divides n. In Figure D.1, I draw a family tree of the integers 1 to

6 with n connected to m by a descending line if n m. Extend the tree to

cover the integers 1 to 16.

Show that is a direction.

Give an example of two incomparable integers (that is, integers n and m

such that it is not true that n = m or m n or n m).

We can use the notion of direction to de¬ne a limit.

De¬nition D.7. If is a direction on a non-empty set X and f is a func-

tion from X to F (where F is an ordered ¬eld such as R or Q), we say that

f (x) ’ a, with respect to the direction , if a ∈ F and, given any > 0, we

can ¬nd an x0 ( ) ∈ X such that |f (x) ’ a| < for all x x0 ( ).

The reader should have no di¬culty in proving the following version of

Lemma 1.2.2.

2

Interestingly, both [11] and [5] though radical in style are entirely standard in content.

397

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

Exercise D.8. Let be a relation on a non-empty set X, let f , g be func-

tions from X to F and let a, b, c be elements of F. Prove the following

results.

(i) The limit is unique. That is, if f (x) ’ a and f (x) ’ b, with respect

to the direction , then a = b.

(ii) Suppose Y is a non-empty subset of X with the property that if when-

ever x, y ∈ Y , we can ¬nd z ∈ Y such that z x and z y. Then, if Y

is the restriction of the relation to Y , Y is a direction on Y .

Suppose, in addition, that, given any x ∈ X we can ¬nd a y ∈ Y such that

y x. If f (x) ’ a, with respect to the direction , and fY is the restriction

of f to Y , then fY (x) ’ a, with respect to the direction Y .

(iii) If f (x) = c for all x ∈ X, then f (x) ’ c, with respect to the direction