continuous map is again closed.

For example, the set consisting of a single point in R is closed. Since the

map d(A, ·) is continuous, we conclude that the set

{x|d(A, x) = 0}

consisting of all point at zero distance from A is a closed set. It clearly is a closed

set which contains A. Suppose that S is some closed set containing A, and y ∈ S.

Then there is some r > 0 such that Br (y) is contained in the complement of

C, which implies that d(y, w) ≥ r for all w ∈ S. Thus {x|d(A, x) = 0} ‚ S.

In short {x|d(A, x) = 0} is a closed set containing A which is contained in all

closed sets containing A. This is the de¬nition of the closure of a set, which is

denoted by A. We have proved that

A = {x|d(A, x) = 0}.

In particular, the closure of the one point set {x} consists of all points u such

that d(u, x) = 0.

Now the relation d(x, y) = 0 is an equivalence relation, call it R. (Transitiv-

ity being a consequence of the triangle inequality.) This then divides the space

X into equivalence classes, where each equivalence class is of the form {x}, the

closure of a one point set. If u ∈ {x} and v ∈ {y} then

d(u, v) ¤ d(u, x) + d(x, y) + d(y, v) = d(x, y).

108 CHAPTER 5. THE CONTRACTION FIXED POINT THEOREM

since x ∈ {u} and y ∈ {v} we obtain the reverse inequality, and so

d(u, v) = d(x, y).

In other words, we may de¬ne the distance function on the quotient space X/R,

i.e. on the space of equivalence classes by

d({x}, {y}) := d(u, v), u ∈ {x}, v ∈ {y}

and this does not depend on the choice of u and v. Axioms 1)-3) for a metric

space continue to hold, but now

d({x}, {y}) = 0 ’ {x} = {y}.

In other words, X/R is a metric space. Clearly the projection map x ’ {x} is

an isometry of X onto X/R. (An isometry is a map which preserves distances.)

In particular it is continuous. It is also open.

In short, we have provided a canonical way of passing (via an isometry) from

a pseudo-metric space to a metric space by identifying points which are at zero

distance from one another.

A subset A of a pseudo-metric space X is called dense if its closure is the

whole space. From the above construction, the image A/R of A in the quotient

space X/R is again dense. We will use this fact in the next section in the

following form:

If f : Y ’ X is an isometry of Y such that f (Y ) is a dense set of X, then

f descends to a map F of Y onto a dense set in the metric space X/R.

5.2 Completeness and completion.

The usual notion of convergence and Cauchy sequence go over unchanged to

metric spaces or pseudo-metric spaces Y . A sequence {yn } is said to converge

to the point y if for every > 0 there exists an N = N ( ) such that

∀ n > N.

d(yn , y) <

A sequence {yn } is said to be Cauchy if for any > 0 there exists an N = N (

such that

∀ m, n > N.

d(yn , ym ) <

The triangle inequality implies that every convergent sequence is Cauchy. But

not every Cauchy sequence is convergent. For example, we can have a sequence

of rational numbers which converge to an irrational number, as in the approxi-

mation to the square root of 2. So if we look at the set of rational numbers as a

metric space R in its own right, not every Cauchy sequence of rational numbers

converges in R. We must “complete” the rational numbers to obtain R, the set

of real numbers. We want to discuss this phenomenon in general.

109

5.2. COMPLETENESS AND COMPLETION.

So we say that a (pseudo-)metric space is complete if every Cauchy sequence

converges. The key result of this section is that we can always “complete” a

metric or pseudo-metric space. More precisely, we claim that

Any metric (or pseudo-metric) space can be mapped by a one to one isometry

onto a dense subset of a complete metric (or pseudo-metric) space.

By the italicized statement of the preceding section, it is enough to prove

this for a pseudo-metric spaces X. Let Xseq denote the set of Cauchy sequences

in X, and de¬ne the distance between the Cauchy sequences {xn } and {yn } to

be

d({xn }, {yn }) := lim d(xn , yn ).

n’∞

It is easy to check that d de¬nes a pseudo-metric on Xseq . Let f : X ’ Xseq

be the map sending x to the sequence all of whose elements are x;

f (x) = (x, x, x, x, · · · ).

It is clear that f is one to one and is an isometry. The image is dense since by

de¬nition

lim d(f (xn ), {xn }) = 0.

Now since f (X) is dense in Xseq , it su¬ces to show that any Cauchy sequence

of points of the form f (xn ) converges to a limit. But such a sequence converges

to the element {xn }. QED

Of special interest are vector spaces which have metric which is compatible

with the vector space properties and which is complete: Let V be a vector space

over the real numbers. A norm is a real valued function

v’ v

on V which satis¬es

1. v ≥ 0 and > 0 if v = 0,

2. rv = |r| v for any real number r, and

3. v + w ¤ v + w ∀ v, w ∈ V .

Then d(v, w) := v’w is a metric on V , which satis¬es d(v+u, w+u) = d(v, w)

for all v, w, u ∈ V . The ball of radius r about the origin is then the set of all v

such that v < r. A vector space equipped with a norm is called a normed

vector space and if it is complete relative to the metric it is called a Banach

space.

110 CHAPTER 5. THE CONTRACTION FIXED POINT THEOREM

5.3 The contraction ¬xed point theorem.

Let X and Y be metric spaces. Recall that a map f : X ’ Y is called a

Lipschitz map or is said to be “Lipschitz continuous”, if there is a constant C

such that

dY (f (x1 ), f (x2 )) ¤ CdX (x1 , x2 ), ∀ x1 , x2 ∈ X.

If f is a Lipschitz map, we may take the greatest lower bound of the set of all

C for which the previous inequality holds. The inequality will continue to hold

for this value of C which is known as the Lipschitz constant of f and denoted

by Lip(f ).

A map K : X ’ Y is called a contraction if it is Lipschitz, and its Lipschitz

constant satis¬es Lip(K) < 1. Suppose K : X ’ X is a contraction, and

suppose that Kx1 = x1 and Kx2 = x2 . Then

d(x1 , x2 ) = d(Kx1 , Kx2 ) ¤ Lip(K)d(x1 , x2 )

which is only possible if d(x1 , x2 ) = 0, i.e. x1 = x2 . So a contraction can have

at most one ¬xed point. The contraction ¬xed point theorem asserts that if the

metric space X is complete (and non-empty) then such a ¬xed point exists.

Theorem 5.3.1 Let X be a non-empty complete metric space and K : X ’ X

a contraction. Then K has a unique ¬xed point.

Proof. Choose any point x0 ∈ X and de¬ne

xn := K n x0

so that

xn+1 = Kxn , xn = Kxn’1

and therefore

d(xn+1 , xn ) ¤ Cd(xn , xn’1 ), 0¤C <1