Bessaga’s converse to the contraction mapping theorem
by Willie Wong
In preparing some lecture notes for the implicit function theorem, I took a look at Schechter’s delightfully comprehensive Handbook of Analysis and its Foundations (which you can also find on his website), and I learned something new about the Banach fixed point theorem. To quote Schechter:
… although Banach’s theorem is quite easy to prove, a longer proof cannot yield stronger results.
I will write a little bit here about a “converse” to the Banach theorem due to Bessaga, which uses a little bit of help from the Axiom of Choice.
The theorem states:
Let be a complete non-empty metric space. Let be a strict contraction: that is to say, suppose there exists some such that always hold. Then has a unique fixed point .
Proof. Let be arbitrary and fixed. Consider the sequence , and for . Let . Easily we see that by triangle inequality, for and so we can choose sufficiently large (using convergence) such that . But then the triangle inequality implies
giving a contradiction to the assumption that is a contraction. Similarly, is unique since for two fixed points we must have
Note that one immediate corollary is that: if is a contraction mapping, then each iterate possesses exactly one (the same) fixed point .
Let be a set and . Suppose is a function such that for any we have
then there exists a complete metric on such that is a strict contraction.
Sketch of proof. First we define an equivalence relation on . We say if there exists positive integers such that . If we define
and where is the value that attains .
We also define
Observe that is symmetric in its arguments and antisymmetric.
Now, by the axiom of choice, there exists a choice function that chooses for each equivalence class of a representative, this extends to a function . From this we can define a function by
Now we are in a position to define our distance function . We do it in several steps.
- If , we define
where the empty sum yields 0.
- If , we define
- If and neither is , we define
This definition is obviously symmetric and non-negative. And it is easy to check that and . Triangle inequality involves a little bit more work, but most cases are immediately obvious except when . Here we need to check that
which we do right now. Suppose and . WLOG we can take . Then we have that . This shows that . And this proves the inequality above.
It is easy to see that any Cauchy sequence either is eventually constant, or must converge to : if we have that
and this shows that is a complete metric. Now, it remains to verify that is a contraction. Noting that and we see easily that is a contraction with Lipschitz constant . QED