24. The Banach Fixed Point Theorem

Remarks:

"The great difficulty in talking about non-algorithmic phenomena is that although we can say what it is in general terms that they do, it is impossible by their very nature to describe how they do it."

Buddhism, mind, mathematics and metamathematics

The Banach Fixed Point Theorem is a very good example of the sort of theorem that the author of this quote would approve. The theorem and proof:

  1. Tell us that under a certain condition there is a unique fixed point.

  2. Tell us that the fixed point is the limit of a certain computable sequence.

  3. Give us an estimate of how close each term of the sequence is to the fixed point.

24.1 Definition:

Given $\QTR{Large}{(M,d)}$ a Metric Space, a function MATH is said to be a contraction mapping if there is a constant $\QTR{Large}{q}$ with MATH such that for all MATH

MATH

.

24. 2 Theorem:(Banach Fixed Point Theorem)

Let $\QTR{Large}{(M,d)}$ be a complete metric space then every contraction has a unique fixed point.

Proof:

That the fixed point is unique follows from the observation that if MATH and MATH

then MATH, but $\QTR{Large}{q<1}$ so MATH0$\QTR{Large}{\ }$or $\QTR{Large}{x=y.}$

To show that a fixed point exists, pick any MATH . Setting MATH we define a sequence MATH by setting MATH

Rewriting the contraction formula we have

MATH

or

MATH

Finally, assuming n $\QTR{Large}{<}$ m

MATH

MATH

or

MATH

and since MATH1

* MATH

Thus MATH is Cauchy. Moreover we can use * to estimate the limit.

24.3 A Very Simple Application.

There are any number of important applications of The Banach Fixed Point Theorem. The text discusses one. Unfortunately, we will not have time to discuss any of them this semester. The following example, is just meant to give a taste of how the theorem is used.

Let MATH with the standard metric. Let MATH

Since MATH

MATH on $\QTR{Large}{M}$

It is indeed the case that for any MATH we have MATH0.

Note that on MATH , $\QTR{Large}{T}$ also has a unique fixed point.