[y(j)] + θ(j ’1 ) > θ(xj ) > [y(j)]

and so

|θ(xj ) ’ [y(j)]| < j ’1 .

We observe that

θ(|xj ’ xk |) = |θ(xj ) ’ θ(xk )|

¤ |θ(xj ) ’ [y(j)]| + |θ(xk ) ’ [y(k)]| + |[y(j)] ’ [y(k)]|

< θ(j ’1 ) + θ(k ’1 ) + |[y(j)] ’ [y(k)]|.

374 A COMPANION TO ANALYSIS

Given any ∈ Q, we can ¬nd an N such that N ’1 < /3 and |[y(j)]’[y(k)]| <

θ( /3) for all j, k ≥ N . The results of this paragraph show that

|xj ’ xk | < /3 + /3 + /3 =

for all j, k ≥ N , and so the xj form a Cauchy sequence.

We now wish to show that [y(n)] ’ [x] as n ’ ∞. Let [ ] > θ(0) be

given. Since the sequence [y(n)] is Cauchy, we can ¬nd an M such that

|[y(j)] ’ [y(k)]| < θ(1/2)[ ] for all j, k ≥ M .

We now use the axiom of Archimedes (Lemma 14.4.10) to show that we can

pick an N ≥ M such that θ(N ’1 ) < θ(1/6)[ ] and observe that the inequality

proved in the last paragraph gives

|θ(xj ) ’ θ(xk )| < θ(1/2)[ ] for all j, k ≥ N .

Thus

|[x] ’ θ(xk )| ¤ θ(1/2)[ ] for all k ≥ N ,

and

|[x] ’ [y(k)]| ¤ |[x] ’ θ(xk )| + |θ(xk ) ’ [y(k)]| ¤ θ(1/2)[ ] + θ(N ’1 ) < [ ]

for all k ≥ N , so we are done.

Exercise 4.6.22 shows that the general principle of convergence and the axiom

of Archimedes together imply the fundamental axiom of analysis. We have

thus proved our desired theorem.

Theorem 14.4.13. (R, +, —, >) is an ordered ¬eld satisfying the funda-

mental axiom of analysis.

As we remarked earlier, most of the construction given in this section

applies to any ordered ¬eld. In Appendix G we push this idea a little further.

As might be expected from Lemma 14.1.5 and the accompanying discussion,

the real number system is unique (in an appropriately chosen sense). The

details are given in Appendix A.

375

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

Paradise lost? ™™

14.5

Morris Kline once wrote that ˜A proof tells us where to concentrate our

doubts.™ Our construction of the reals from the rationals is such a remarkable

result that it merits further examination. We know that the rationals are

countable and the reals are uncountable. Where in the proof does the switch

from countable to uncountable occur? Inspection of the proof shows that

the switch happens right at the beginning with the sentence ˜We start by

considering the space X of Cauchy sequences x = (xn )∞ in Q.™ If pressed

n=1

to justify this step I might split it into two:-

(a) Consider the set QN of all sequences x = (xn )∞ in Q (that is all

n=1

functions x : N ’ Q, where N is the set of strictly positive integers).

(b) Consider the subset X of QN consisting of all sequences which satisfy

the Cauchy condition.

Unfortunately my justi¬cation resembles the following pair of de¬nitions.

(a ) Consider the set „¦ of all sets.

(b ) Consider the subset ¦ of „¦ consisting of all A ∈ „¦ such that A ∈ A.

/

As the reader no doubt knows, the de¬nition of ¦ leads to a contradiction.

If ¦ ∈ ¦ then ¦ ∈ ¦, but if ¦ ∈ ¦ then ¦ ∈ ¦.

/ /

There are two schools of thought regarding this paradox. The radical

school wishes to ban all de¬nitions of the form (a) and (b) from mathematics.

At ¬rst sight this seems an easy task “ a return to the simpler and healthier

practices of our ancestors. However, a householder who investigates a trace of

dry rot in one room may well discover that her whole house is so riddled with

fungus that the whole structure must be torn down and rebuilt. It turns out

that classical mathematics (that is the kind of mathematics discussed in this

book) depends so much on de¬nitions and arguments which are unacceptable

to the radicals that they have to rebuild mathematics from scratch.

The various schemes for rebuilding restrict mathematics to the study

of ˜constructible objects™ and break decisively even at the most elementary

level with the traditional practices of mathematicians. A striking example of

this break is that, in the rebuilt structure, all functions are continuous. In

Appendix H, I try to indicate why this is so.

The conservative school, to which most mathematicians belong, says that

there are ˜natural rules™ which bar at least one of (a ) and (b ) whilst al-

lowing both (a) and (b). Just as there are di¬erent radical theories with

di¬erent criteria as to what is a ˜constructible object™, so there are di¬erent

systems of conservative ˜natural rules™. The standard system of rules (the

Zermelo-Fraenkel system) is set out with great charm and clarity in Hal-

mos™s little masterpiece Naive Set Theory [20]. Halmos also shows how the

system of positive integers can be constructed in a rather natural way using

376 A COMPANION TO ANALYSIS

the Zermelo-Fraenkel axioms. The axioms for set theory must be supple-

mented by a system of rules setting out what kind of statements are allowed

in mathematics6 and what laws of inference we may use. Once you have read

Halmos, then Johnstone™s Notes on Logic and Set Theory [26] provide an

excellent short7 but rigorous account of all that the interested non-specialist

needs to know.

All of the analysis in this book and almost all of mathematics that

is presently known can be deduced from the small collection of Zermelo-

Fraenkel axioms in the same way and with the same standard of rigour8 as

Euclid deduced his geometry from his axioms9 . However, plausible as the

Zermelo-Fraenkel axioms seem, their plausibility is based on our experience

with ¬nite sets and to construct classical mathematics we must apply these

axioms to in¬nite sets which lie outside our physical and mental experience.

We cannot therefore be sure that the axioms may not lead to some subtle

contradiction10 . Kline quotes Poincar´, a witty, though not very profound,

e

critic of set theory as saying ˜We have put a fence around the herd to protect

it from the wolves but we do not know whether some wolves were not already

within the fence.™

Few mathematicians of the conservative school seem worried by this.

Partly, this is because in nearly a century of continuous scrutiny no one

has produced a contradiction. (Personally, I am less convinced that the hu-

man race will survive the next hundred years than that the Zermelo-Fraenkel

system will survive the century.) Partly it is because, if a contradiction ap-

peared in the Zermelo-Fraenkel system, we could simply use one of the rival

conservative systems of axioms or, if the worst came to the worst, we could

admit that the radicals were right, after all, and study one of their recon-

structed systems. (Modern mathematics thus appears as a ship towing a

long line of lifeboats. If the ship sinks we move to the ¬rst lifeboat. If the

¬rst lifeboat sinks we move to the second and so on.) Partly it is because

the failure of the Zermelo-Fraenkel system would be one of the most inter-

6

Thus excluding ˜This sentence is false or meaningless™, ˜The smallest positive integera

not de¬nable in less than ¬fty English words™, ˜When does the next train leave for London?™

and so on.

7

I emphasise the word short. The path from the Zermelo-Fraenkel axioms to the

positive integers can be traversed easily in a 24 hour course.

8

I choose my words carefully. Modern mathematicians have found gaps in Euclid™s

reasoning but none of these is large enough to invalidate the work.

9

The massive Bourbaki volumes constitute a proof of this statement.

10

Hilbert tried to avoid this problem by ¬nding a model for the Zermelo-Fraenkel system

inside some system like those proposed by the radicals which would be ˜obviously™ free

of contradiction. Most mathematicians agree that G¨del™s theorem makes it extremely

o

unlikely that such a programme could be successful.

377

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

esting things that could happen to mathematics. And ¬nally, we have come

to accept that no really interesting part of mathematics can be proved free

of contradiction11 .

So far in this section, I have tried to give a fair representation of the

thoughts of others. For the short remainder of this section, I shall give my

own views. Mathematics changes slowly. After ten years, some problems

have been solved and some new problems have arisen, but the subject is

recognisably the same. However, over a century it changes in ways which

mathematicians at the beginning of that century could not conceive. The

20th century has, for example, seen special and general relativity, quan-

tum mechanics, the electronic computer, the theorems of G¨del and Turing

o

and Kolmogorov™s axiomatisation of probability. The 19th century saw non-

Euclidean geometry, complex variable theory, quaternions and Cantor™s set

theory. The 17th and 18th century saw the invention of the calculus.

Given this, it seems presumptuous to seek a permanent foundation for

mathematics. It is a happy accident that almost all of mathematics, as we

now know it, can be deduced from one set of axioms but, just as history has

taught us that there is not one geometry but many, so it is not unlikely that

the future will present us with di¬erent mathematics deduced from radically

di¬erent axiom schemes. The art of the mathematician will still consist in

the rigorous proof of unexpected conclusions from simple premises but those

premises will change in ways that we cannot possibly imagine.

11

A hungry fox tried to reach some clusters of grapes which he saw hanging from a vine

trained on a tree, but they were too high. So he went o¬ and comforted himself by saying

˜They weren™t ripe anyhow™. (Aesop)

Appendix A

The axioms for the real

numbers

Axioms for an ordered ¬eld. An ordered ¬eld (F, +, —, >) is a set F,

together with two binary operations + and — and a binary relation >, obeying

the following rules. (We adopt the notation ab = a — b.)

(A1) a + (b + c) = (a + b) + c.

(A2) a + b = b + a.

(A3) There is a unique element 0 ∈ F such that a + 0 = a for all a ∈ F.

(A4) If a ∈ F, then we can ¬nd an ’a ∈ F such that a + (’a) = 0.

[Conditions (A1) to (A4) tell us that (F, +) is a commutative group. We

write a ’ b = a + (’b).]

(M1) a(bc) = (ab)c.

(M2) ab = ba.

(M3) There is a unique element 1 ∈ F such that a1 = a for all a ∈ F.

(M4) If a ∈ F and a = 0, then we can ¬nd an a’1 ∈ F such that

aa’1 = 1.

[Conditions (M1) to (M4) tell us, among other things, that (F \ {0}, —)

is a commutative group.]

(D) a(b + c) = ab + ac.

[Condition (D) is called the distributive law.]

If we write P = {a ∈ F : a > 0}, then

(P1) If a, b ∈ P, then a + b ∈ P.

(P2) If a, b ∈ P, then ab ∈ P.

(P3) If a ∈ F, then one and only one of the following three statements

is true: a ∈ P, ’a ∈ P or a = 0.

We call P the set of strictly positive elements of F and write a > b if and

only if a ’ b ∈ P.

379

380 A COMPANION TO ANALYSIS

Note that, although we state the axioms here, we shall not use

them explicitly in this book. Everything depending on these axioms is,

so far as we are concerned, mere algebra.

The following series of exercises show that, up to the appropriate iso-

morphism, the reals are the unique ordered ¬eld satisfying the fundamental

axiom. Although the reader should probably go through such a proof at some

time, it will become easier as she gets more experience (for example if she

has read the ¬rst four sections of Chapter 14) and is not needed elsewhere in

this book.

Exercise A.1. We work in an ordered ¬eld (F, +, —, >). You should cite

explicitly each of the axioms from the list given on page 379 that you use. We

write 1F for the unit of F (that is, for the unique element of F with 1F a = a

for all a ∈ F) and 0F for the zero of F (that is, for the unique element of F

with 0F + a = a for all a ∈ F).

(i) By considering the equality

ab + a(’b) + (’a)(’b) = ab + a(’b) + (’a)(’b),

show that (’a)(’b) = ab for all a, b ∈ F.

(ii) By (i), we have, in particular, a2 = (’a)2 . By applying axiom (P3),

show that a2 > 0F whenever a = 0F .

(iii) Deduce that 1F > 0F .

Exercise A.2. We continue with the discussion of Exercise A.1. If n is a

strictly positive integer, let us write

n

nF = 1 F + 1 F + · · · + 1 F .

Show, by induction, or otherwise, that nF > 0F , and so in particular nF = 0F .

In the language of modern algebra, we have shown that an ordered ¬eld

has characteristic ∞. It is a standard result that any ¬eld of characteristic

∞ contains a copy of the rationals.

Exercise A.3. We continue with the discussion of Exercise A.2. If n is a

strictly negative integer, let us write nF = ’(’n)F .

(i) Show that if we set „ (n) = nF , then „ : Z ’ F is a well de¬ned

injective map with

„ (n + m) = „ (n) + „ (m),

„ (nm) = „ (n)„ (m),

„ (n) > 0F whenever n > 0,

381

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

for all n, m ∈ Z.

(ii) If n, m ∈ Z and m = 0, let us set φ(n/m) = „ (n)„ (m)’1 . Show

that φ : Q ’ F is a well de¬ned (remember that rn/rm = n/m for r = 0)

injective map with

φ(x + y) = φ(x) + φ(y),

φ(xy) = φ(x)φ(y),

φ(x) > 0F whenever x > 0,

for all x, y ∈ Q.

So far we have merely been doing algebra.

Exercise A.4. We continue with the discussion of Exercise A.3, but now

we assume that F satis¬es the fundamental axiom. Let us write K = φ(Q)

(informally, K is a copy of Q in F). Prove the following slight improvement

of Lemma 1.5.6. If x ∈ F, we can ¬nd xj ∈ K with x1 ¤ x2 ¤ . . . such that

xj ’ x as j ’ ∞.

Exercise A.5. We continue with the discussion of Exercise A.4, so, in par-

ticular, we assume that F satis¬es the fundamental axiom.

(i) If x ∈ R, then, by Exercise A.4, we can ¬nd xj ∈ Q with x1 ¤ x2 ¤ . . .

such that xj ’ x. Show, by using the fundamental axiom, that there is a

a ∈ F such that φ(xj ) ’ a as j ’ ∞.

(ii) Show further that, if xj ∈ Q and xj ’ x, then φ(xj ) ’ a as j ’ ∞.

(iii) Conclude that we may de¬ne θ : R ’ F by adopting the procedure of

part (i) and setting θ(x) = a.

(iv) Show that θ : R ’ F is a bijective map.

(v) Show that, if x, y ∈ R, then

θ(x + y) = θ(x) + θ(y),

θ(xy) = θ(x)θ(y),

θ(x) > 0F whenever x > 0.

Appendix B

Countability

Most of my readers will already have met countability and will not need to

read this appendix. If you have not met countability this appendix gives a

˜quick and dirty™ introduction1 .

De¬nition B.1. A set E is called countable if E = … or the elements of E

can be written out as a sequence ej (possibly with repetition), that is, we can

¬nd e1 , e2 , . . . such that

E = {e1 , e2 , e3 . . . }

Lemma B.2. A set E is countable if and only if E is ¬nite or the elements

of E can be written out as a sequence ej without repetition, that is, we can

¬nd e1 , e2 , . . . all unequal such that

E = {e1 , e2 , e3 . . . }

Proof. If the elements of E can be written out as a sequence ej (possibly

with repetition), then either E is ¬nite or we can obtain E as a sequence

without repetition by striking out all terms equal to some previous one.

If E is ¬nite, then either E = …, so E is countable by de¬nition or we can

write E = {ej : 1 ¤ j ¤ N }. Setting en = eN for n ≥ N , we have

E = {e1 , e2 , e3 . . . }

Exercise B.3. Show that any subset of a countable set is countable.

1

The standard treatment via injectivity gives more ¬‚exible methods which are easily

extended to more general situations

383

384 A COMPANION TO ANALYSIS

b1 b3 b6 b10 . . . a1,1 a1,2 a1,3 a1,4 . . .

b2 b5 b9 . . . a2,1 a2,2 a2,3 . . .

b4 b8 . . . a3,1 a3,2 . . .

b7 . . . a4,1 . . .

... ...

Figure B.1: A sequence of sequences set out as a sequence

The key result on countability, at least so far as we are concerned, is given

in the next theorem.

∞

Theorem B.4. If A1 , A2 , . . . are countable, then so is Aj .

j=1

In other words, the countable union of countable sets is countable.

Proof. We leave it to the reader to give the proof when all of the Aj are empty

(easy) or not all the Aj are empty but all but ¬nitely many are (either modify

the proof below or adjoin in¬nitely many copies of one of the non-empty Aj ).

In the remaining case, in¬nitely many of the Aj are non-empty and, by

striking out all the empty sets, we may assume that all of the Aj are non-

empty. Let us write

Aj = {aj,1 , aj,2 , aj,3 , . . . }.

If we write

N (r) = 1 + 2 + · · · + (r ’ 1) = r(r ’ 1)/2

and set bN (r)+k = ar’k+1,k [1 ¤ k ¤ r, 1 ¤ r] (so that we follow the pattern

shown in Figure B.1), we see that

∞

Aj = {b1 , b2 , b3 . . . },

j=1

∞

and so Aj is countable.

j=1

Exercise B.5. Carry out the proofs asked for in the ¬rst sentence of the

proof of Theorem B.4

Theorem B.4 forms the basis for an argument2 known as the ˜hamburger

argument™. (Consider the set Aj of hamburgers to be found in a sphere

2

Marianna Cs¨rnyei claims that this is taught in Hungarian primary schools, but she

o

may exagerate.

385

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

radius j kilometres with centre the middle of Trafalgar square. Clearly A j

is ¬nite and so countable. But the set A of all hamburgers in the universe

is given by A = ∞ Aj so, since the countable union of countable sets

j=1

is countable, A is countable. We can enumerate all the hamburgers in the

universe as a sequence.)

Lemma B.6. The set Q of rational numbers is countable.

Proof. Let

Aj = {r/s : |r| + |s| ¤ j, s = 0, r, s ∈ Z}.

The set Aj is ¬nite and so countable. But Q = ∞ Aj so, since the countable

j=1

union of countable sets is countable, Q is countable.

In Exercise 1.6.7 we showed that the closed interval [a, b] with a < b is not

a countable set and so (by Exercise B.3) R is uncountable. Lemma B.6 thus

provides an indirect but illuminating proof that R = Q.

Exercise B.7. (Existence of transcendentals.) A real number x is called

algebraic if

n

ar x r = 0

r=0

for some ar ∈ Z [0 ¤ r ¤ n], an = 0 and n ≥ 1, (in other words x is a root of

a non-trivial polynomial with integer coe¬cients). The ¬rst proof that not all