<< . .

. 43
( : 70)

. . >>

[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)]|.

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 .


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


|[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.
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Paradise lost? ™™
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
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
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

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,
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-
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.
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.
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.
The massive Bourbaki volumes constitute a proof of this statement.
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
unlikely that such a programme could be successful.
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
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.

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

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.


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

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,
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


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.
The standard treatment via injectivity gives more ¬‚exible methods which are easily
extended to more general situations


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 .

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 . . . },

and so Aj is countable.

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
Marianna Cs¨rnyei claims that this is taught in Hungarian primary schools, but she
may exagerate.
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
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
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
ar x 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

<< . .

. 43
( : 70)

. . >>