<< . .

. 28
( : 70)



. . >>


Exercise 10.2.9. (This requires some experience with probability.) Write
Yij = 1 if Si and Sj intersect [i = j], Yij = 0, otherwise. What is EYij ?
What is E 1¤j<i¤N Yij ? If q is small show that E 1¤j<i¤N Yij is large.
What does this tell you about the number of intersecting balls?

If the balls intersect, then, even if less than qn errors are made, in trans-
mission, the received message may belong to two or more balls. In such a
case we simply agree that our system has failed. How probable is such a
failure? Suppose we transmit y1 and receive z = y1 + e. Since the remaining
yj with 2 ¤ j ¤ N , have been chosen at random, independently of yj , the
probability that z lies in N Sj has nothing to do with how we de¬ned z
j=2
and is just

Vol( N Sj ) N
Vol Sj
j=2 j=2
¤ ≈ ·.
Vol X Vol X
Thus the probability of failure of the type discussed in this paragraph can
be kept at any speci¬ed level · whilst still allowing roughly · Vol S1 / Vol X
code words.

Exercise 10.2.10. How can you reconcile this last result with Exercise 10.2.9?

We have thus obtained the full Shannon™s theorem.
241
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Theorem 10.2.11. (Shannon.) Consider our noisy channel. If p, the
probability of error in a single bit, is less than 1/2, then, choosing p < p <
1/2, we can transmit, with error rate as small as we please, so that informa-
tion is passed at a rate of 1 ’ H(p ) times that of our original channel.

Exercise 10.2.12. (For the knowledgeable only.) The statement ˜We have
thus obtained the full Shannon™s theorem™ is a bit optimistic since there are
quite a lot of loose ends to tie up. Tie them up.

In the 50 or so years since Shannon proved his theorem, no one has
produced non-random codes to match his random codes for long code words.
However, non-random methods are beginning to catch up. For our ¬rst
problem of sphere packing in Rn , the best known packings in high dimensions
are lattice (so very highly ordered) packings. The experts believe that this
re¬‚ects our ignorance rather than the truth.


10.3 Metric spaces
We discovered our proof of Shannon™s theorem (at least in the form of
Lemma 10.2.8) by drawing heavily on analogies with distance and volume in
Rn . Many proofs in analysis and elsewhere have been discovered by exploit-
ing analogies between the usual distance in Rn and ˜things that look more
or less like distance™.
Recalling that ˜once is a trick, twice is a method, thrice a theorem and
four times a theory™, we seek to codify this insight.
Our ¬rst try is to model the properties of Euclidean distance set out in
Lemma 4.1.4.

De¬nition 10.3.1. Let V be a real vector space and N : V ’ R a function.
We write x = N (x) and say that is a norm if the following conditions
hold.
(i) x ≥ 0 for all x ∈ V ,
(ii) If x = 0, then x = 0,
(iii) If » ∈ R and x ∈ V , then »x = |»| x .
(iv) (The triangle inequality) If x, y ∈ V , then x + y ¤ x + y .

·
Note that some mathematicians prefer to write instead of . The
˜·™ acts as a placeholder.

Exercise 10.3.2. Check that the usual Euclidean norm on Rm is indeed a
norm.
242 A COMPANION TO ANALYSIS

The appropriate de¬nition when V is a vector space over C, rather than
R, runs similarly.

De¬nition 10.3.3. Let V be a complex vector space and N : V ’ R a
function. We write x = N (x) and say that is a norm if the following
conditions hold.
(i) x ≥ 0 for all x ∈ V ,
(ii) If x = 0, then x = 0,
(iii) If » ∈ C and x ∈ V , then »x = |»| x .
(iv) (The triangle inequality) If x, y ∈ V , then x + y ¤ x + y .
We say that (V, ) is a normed space.

However, we wish to have a notion of distance which applies to spaces
which do not have a vector space structure. We seek a de¬nition modelled
on those properties of Euclidean distance which do not refer to vector space
structures. (Thus you should both compare and contrast De¬nition 10.3.1.)

De¬nition 10.3.4. We say that (X, d) is a metric space if X is a set and
d : X 2 ’ R is a function with the following properties:-
(i) d(x, y) = 0 if and only if x = y.
(ii) d(x, y) = d(y, x) for all x, y ∈ X.
(iii) (The triangle inequality) d(x, z) ¤ d(x, y)+d(y, z) for all x, y, z ∈ X.

Exercise 10.3.5. Show that, if (X, d) is a metric space, then d(x, y) ≥ 0 for
all x, y ∈ X.

It is a remarkable fact that the general notion of a metric space was ¬rst
introduced by Fr´chet in 1906 and the general notion of a normed space by
e
Banach in 1932! (We shall see one reason for the late emergence of the notion
of a norm in Theorem 10.4.6.)

Exercise 10.3.6. If is a norm over the (real or complex) vector space
V and we set d(x, y) = x ’ y , show that (V, d) is a metric space.

The conditions of De¬nition 10.3.4 are sometimes called the axioms for
metric space. However, they are not axioms in the same sense as the Funda-
mental Axiom of Analysis which asserts a fundamental principle of argument
which is to be accepted without further proof3 . Instead they try to isolate the
common properties of an interesting class of mathematical objects. (Com-
pare the de¬nition of birds as ˜oviparous, warm-blooded, amniotic vertebrates
which have their anterior extremities transformed into wings. Metacarpus
3
Within the context of a particular system. The axioms of one system may be theorems
in a another. We shall discuss this further in Section 14.3.
243
Please send corrections however trivial to twk@dpmms.cam.ac.uk

and ¬ngers carry feathers or quills. There is an intertarsal joint and not
more than 4 toes, of which the ¬rst is a hallux.™ Thus penguins are and
dodos were birds but dragon¬‚ies and bats are not.)
At ¬rst sight, axiom systems like that for metric systems seem merely
methods for economising on the number of theorems we have to prove. A
theorem which applies to all metric spaces will not need to be proved for
each individually. However, a successful axiom system should be a powerful
research tool by suggesting appropriate questions. (You will learn more about
a penguin by comparing it to a hawk than by comparing it to a frog.) Thus
if we have a ˜space on which we do analysis™ we can ask ˜can we make it into
a metric space?™. If it is a metric space we can then compare and contrast
it with other metric spaces that we know and this may well suggest new
theorems.
Although concepts like metric space are intended to apply to important
natural systems, we often study ˜toy examples™ in order to gain insight into
what can happen in such a system. Here is such a ˜toy example™.

Exercise 10.3.7. We work in Rm with the usual Euclidean norm. Show that
if d(x, y) = x + y when x = y and d(x, x) = 0, then (R m , d) is a metric
space.

This metric is called the British Railway non-stop metric. To get from A
to B in the fastest time, we travel via London (the origin). Here is another
version of the same idea which we call the British Railway stopping metric.

Exercise 10.3.8. We work in Rm with the usual Euclidean norm. If there
exists a real » such that »x = y, we write d(x, y) = x ’ y . Otherwise, we
set d(x, y) = x + y . Show that (Rm , d) is a metric space.

Much of the ˜mere algebra™ which we did for the Euclidean metric car-
ries over with hardly any change to the general metric case. Compare the
following de¬nition with De¬nition 4.1.8.

De¬nition 10.3.9. Let (X, d) be a metric space. If an ∈ X for each n ≥ 1
and a ∈ X, then we say that an ’ a if, given > 0, we can ¬nd an n0 ( )
such that

for all n ≥ n0 ( ).
d(an , a) <

We call a the limit of an .

Exercise 10.3.10. (i) Let d1 be the British Railway non-stop metric on Rm
de¬ned in Exercise 10.3.7. Show that xn ’ x in (Rm , d1 ) if and only if
244 A COMPANION TO ANALYSIS

(A) there exists an N such that xn = x for all n ≥ N , or
(B) x = 0 and xn ’ 0 as n ’ ∞.
(ii) Find and prove the corresponding result for the British Railway stop-
ping metric of Exercise 10.3.8.
If (V, ) is a normed space, we say that xn ’ x in (V, ) if xn ’ x in
the derived metric. The following result on limits in such spaces is an easy
generalisation of Lemma 4.1.9.
Lemma 10.3.11. Let V be a real vector space and a norm on V .
(i) The limit is unique. That is, if an ’ a and an ’ b as n ’ ∞, then
a = b.
(ii) If an ’ a as n ’ ∞ and n(1) < n(2) < n(3) . . . , then an(j) ’ a as
j ’ ∞.
(iii) If an = c for all n, then an ’ c as n ’ ∞.
(iv) If an ’ a and bn ’ b as n ’ ∞, then an + bn ’ a + b.
(v) Suppose that an ∈ V , a ∈ V , »n ∈ R, and » ∈ R. If an ’ a and
»n ’ », then »n an ’ »a.
Proof. Left to the reader. The reader who looks for the proof of Lemma 4.1.9
will ¬nd herself referred backwards to the proof of Lemma 1.2.2, but will ¬nd
the proofs for a general norm on a general vector space just as easy as the
proofs for the Euclidean norm in one-dimension.
Exercise 10.3.12. What changes are necessary (if any) in the statements
and proofs of Lemma 10.3.11 if we make V be a complex vector space?
If we consider a general metric, then we have no algebraic structure and
the result corresponding to Lemma 10.3.11 has far fewer parts.
Lemma 10.3.13. Let (X, d) be a metric space.
(i) The limit is unique. That is, if an ’ a and an ’ b as n ’ ∞, then
a = b.
(ii) If an ’ a as n ’ ∞ and n(1) < n(2) < n(3) . . . , then an(j) ’ a as
j ’ ∞.
(iii) If an = c for all n, then an ’ c as n ’ ∞.
The proof is again left to the reader.
The material on open and closed sets from Section 4.2 goes through es-
sentially unchanged (and proofs are therefore left to the reader).
De¬nition 10.3.14. Let (X, d) be a metric space. A set F ⊆ X is closed if
whenever xn ∈ F for each n and xn ’ x as n ’ ∞ then x ∈ F .
A set U ⊆ X is open if, whenever x ∈ U , there exists an > 0 such that,
whenever d(x, y) < , we have y ∈ U .
245
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Example 10.3.15. Let (X, d) be a metric space. Let x ∈ X and r > 0.
(i) The set B(x, r) = {y ∈ X : d(x, y) < r} is open.
¯
(ii) The set B(x, r) = {y ∈ X : d(x, y) ¤ r} is closed.
¯
We call B(x, r) the open ball of radius r and centre x. We call B(x, r)
the closed ball of radius r and centre x.
Lemma 10.3.16. Let (X, d) be a metric space. A subset U of X is open if
and only if each point of U is the centre of an open ball lying entirely within
U.
Exercise 10.3.17. Find the open balls for the two British rail metrics. (For
all but one point there is a di¬erence between balls of small and large ra-
dius.) Show that the open sets for the British Railway stopping metric of
Exercise 10.3.8 consist of sets of the form A ∪ B where A is empty or
A = {x : x < δ} (here is the Euclidean norm and δ > 0) and B
is the union of sets of the form {»u : a < » < b} where 0 < a < b and
u = 0.
Find the open sets for the British Railway non-stop metric of Exercise 10.3.7.
De¬nition 10.3.18. The set N is a neighbourhood of the point x if we can
¬nd an r > 0 such that B(x, r) ⊆ N .
Lemma 10.3.19. Let (X, d) be a metric space. A subset U of X is open if
and only if its complement X \ U is closed.
Lemma 10.3.20. Let (X, d) be a metric space. Consider the collection „ of
open sets in X.
(i) … ∈ „ , X ∈ „ .
(ii) If U± ∈ „ for all ± ∈ A, then ±∈A U± ∈ „ .
(iii) If U1 , U2 , . . . , Un ∈ „ , then n Uj ∈ „ .
j=1

Lemma 10.3.21. Let (X, d) be a metric space. Consider the collection F
of closed sets in X.
(i) … ∈ F, X ∈ F.
(ii) If F± ∈ F for all ± ∈ A, then ±∈A F± ∈ F.
(iii) If F1 , F2 , . . . , Fn ∈ F, then n Fj ∈ F.
j=1

The new de¬nition of continuity only breaks the chain of translations
slightly because it involves two metric spaces.
De¬nition 10.3.22. Let (X, d) and (Z, ρ) be metric spaces. We say that a
function f : X ’ Z is continuous at some point x ∈ X if, given > 0, we
can ¬nd a δ( , x) > 0 such that, if y ∈ X and d(x, y) < δ( , x), we have
ρ(f (x), f (y)) < .
246 A COMPANION TO ANALYSIS

If f is continuous at every point x ∈ X, we say that f is a continuous
function on X.
The reader may feel that De¬nition 4.2.14 is more general than De¬ni-
tion 10.3.22 because it involves a set E. The following remark shows that
this is not so.
Lemma 10.3.23. Let (X, d) be a metric space and let E ⊆ X. Let dE :
E 2 ’ R be given by dE (u, v) = d(u, v) whenever u, v ∈ E. Then (E, dE ) is a
metric space.
We conclude this section with more results taken directly from Section 4.2
Lemma 10.3.24. Let (X, d) and (Z, ρ) be metric spaces and suppose that
the function f : X ’ Z is continuous at x ∈ X. Then, if xn ∈ E and
xn ’ x, it follows that f (xn ) ’ f (x).
Lemma 10.3.25. Let (X, d) and (Z, ρ) be metric spaces. The function f :
X ’ Z is continuous if and only if f ’1 (O) is open whenever O is open.
Lemma 10.3.26. Let (X, d), (Y, θ) and (Z, ρ) be metric spaces. If f : X ’
Y and g : Y ’ Z are continuous, then so is their composition g —¦ f .


10.4 Norms and the interaction of algebra
and analysis
Starting from one metric we can produce a wide variety of ˜essentially equiv-
alent metrics™.
Exercise 10.4.1. Let (X, d) be a metric space.
(i) If we de¬ne d1 (x, y) = min(1, d(x, y)), show that (X, d1 ) is a metric
space. Show further that, if xn ∈ X [n ≥ 0], then d1 (xn , x0 ) ’ 0 as n ’ ∞
if and only if d(xn , x0 ) ’ 0.
(ii) If we de¬ne d2 (x, y) = d(x, y)2 , show that (X, d2 ) is a metric space.
Show further that, if xn ∈ X [n ≥ 0], then d2 (xn , x0 ) ’ 0 as n ’ ∞ if and
only if d(xn , x0 ) ’ 0.
(iii) Let ± > 0 and de¬ne d± (x, y) = d(x, y)± . For which values of ± is
(X, d± ) always a metric space? For those values of ±, is it always true that,
if xn ∈ X [n ≥ 0], then d± (xn , x) ’ 0 as n ’ ∞ if and only if d(xn , x) ’ 0?
Prove your statements.
(iv) (This is trivial but explains why we had to be careful in the statement
of (iii).) Give an example of metric space (X, d) with X an in¬nite set such
that (X, d± ) is a metric space for all ± > 0.
247
Please send corrections however trivial to twk@dpmms.cam.ac.uk

Because norms re¬‚ect an underlying vector space structure they are much
more constrained.

Lemma 10.4.2. Let 1 and 2 be norms on a vector space V . Then the
following two statements are equivalent.
(a) There exist K, L > 0 such that K x 1 ≥ x 2 ≥ L x 1 for all
x∈V.
(b) If xn ∈ V [n ≥ 0], then xn ’ x0 1 ’ 0 as n ’ ∞ if and only if
xn ’ x0 2 ’ 0.

Proof. It is easy to see that (a) implies (b), since, for example, if xn ’x0 ’
2
0, then

¤ L’1 xn ’ x0
xn ’ x0 ’ 0,
1 2


and so xn ’ x0 1 ’ 0 as n ’ ∞.
To see that (b) implies (a), suppose that (a) is false. Without loss of
generality, suppose that there is no K > 0 such that K x 1 ≥ x 2 for all
x ∈ V . Then we can ¬nd yn ∈ V such that

> n2 y n 1 .
yn 2

’1
Setting x0 = 0 and xn = n’1 yn for n ≥ 1, we obtain
1 yn


xn ’ x0 = 1/n ’ 0
= xn
1 1


and

xn ’ x0 = xn > n,
2 2


so xn ’ x0 0 as n ’ 0. Thus (b) is false if (a) is false
2


Exercise 10.4.3. Let d1 and d2 be metrics on a space X. Consider the
following two statements.
(a) There exist K, L > 0 such that Kd1 (x, y) ≥ d2 (x, y) ≥ Ld1 (x, y) for
all x, y ∈ X.
(b) If xn ∈ X [n ≥ 0] then d1 (xn , x0 ) ’ 0 as n ’ ∞ if and only if
d2 (xn , x0 ) ’ 0.
Show that (a) implies (b) but that (b) does not imply (a).

Although we shall not make much use of this, the concepts just introduced
have speci¬c names.
248 A COMPANION TO ANALYSIS

De¬nition 10.4.4. (i) Let K ≥ 0. If (X, d) and (Y, ρ) are metric spaces, we
say that a function f : X ’ Y is Lipschitz with constant K if ρ(f (x), f (y)) ¤
Kd(x, y) for all x, y ∈ X.
(ii) We say that two metrics d1 and d2 on a space X are Lipschitz equiv-
alent if there exist K, L > 0 such that Kd1 (x, y) ≥ d2 (x, y) ≥ Ld1 (x, y) for
all x, y ∈ X.
Exercise 10.4.5. (i) If (X, d) and (Y, ρ) are metric spaces, show that any
Lipschitz function f : X ’ Y is continuous. Give an example to show that
the converse is false.
(ii) Show that Lipschitz equivalence is indeed an equivalence relation be-
tween metric spaces.
The following result is a less trivial example of the interaction between
algebraic and metric structure.
Theorem 10.4.6. All norms on Rn are Lipschitz equivalent.
Proof. We consider the standard Euclidean norm given by
1/2
n
x2
x= j
j=1

and show that it is equivalent to an arbitrary norm —.
One of the required inequalities is easy to obtain. If we write ei for the
unit vector along the xi axis we have,
n n
¤ |xj | ej
x = xj ej
— —
j=1 j=1

¤ n max |xr | max er ¤ (n max er — ) x .

1¤r¤n 1¤r¤n 1¤r¤n

We have thus shown the existence of a K such that K x ≥ x — .
To obtain the other inequality we use an argument from analysis4 . Ob-
serve that, if we give Rn and R the usual Euclidean metric and de¬ne
f : Rn ’ R by
f (x) = x — ,
then, using the triangle inequality for and the result of the previous

paragraph,
|f (x) ’ f (y)| = | x ’ y —| ¤ x ’ y ¤K x’y ,
— —
4
Experts may be interested in Exercises K.184 and K.185. Non-experts should ignore
this footnote.
249
Please send corrections however trivial to twk@dpmms.cam.ac.uk

and so f is continuous. Now the unit sphere

S(0, 1) = {x ∈ Rn : x = 1}

is closed and bounded for the usual Euclidean metric and so, by Theo-
rem 4.3.4, f is bounded on S(0, 1). In particular, we can ¬nd k ∈ S(0, 1)
where f attains its minimum, that is to say,

f (k) ¤ f (x)

<< . .

. 28
( : 70)



. . >>