Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $(X,d)$ be a metric space. Banach's fixed point theorem states that if $X$ is complete, then every contraction map $f:X\to X$ has a unique fixed point. A contraction map is a continuous map for which there is an real number $0\leq r < 1$ such that $d(f(x),f(y))\leq rd(x,y)$ holds for all $x,y\in X$.

Suppose $X$ is a metric space such that every contraction map $f:X\to X$ has a unique fixed point. Is $X$ complete?

share|improve this question

4 Answers 4

up vote 7 down vote accepted

The answer is no, for example look at the graph of $\sin(1/x)$ on $(0,1]$. But for more information and related questions check out "On a converse to Banach's Fixed Point Theorem" by Márton Elekes.

share|improve this answer
    
If we map every point on the graph to the point on the "next wave on the left" with the same y-value, we get a contraction without fixpoints. Am I missing something? –  Martin Brandenburg May 27 '10 at 9:00
    
That does it. -I am a bit disappointed by the first sentence in that paper which reads "Converses to the Banach Fixed Point Theorem have a very long history." and therefore indicates that my question was not a very original one. –  Xandi Tuni May 27 '10 at 9:06
    
@Martin: I was also thinking about that. The missing point is that the constant $r<1$ (as in the question) has to be uniform, which is not the case when you move waves to the left. Theorem 1.2 of the paper cited by Gjergji gives a proof that the graph of sin(1/x) has the "fixed point property". –  Xandi Tuni May 27 '10 at 9:09
    
@Xandi: Ok. Thanks. –  Martin Brandenburg May 27 '10 at 9:13

If you want a sort of positive result, this comes to my mind, for what is worth:

If X is a metric space such that any contraction map T:Y→Y on any nonempty closed subset of X has a fixed point, then X is complete.

Indeed, a Cauchy sequence (xn) converges if and only if some subsequence converges. Up to extracting a subsequence, a Cauchy sequence is either stationary (thus convergent) or injective, and verifies d(xp+1,xq+1)≤d(xp,xq)/2. If the set {xn: n∈N} were closed in X, T(xn):=xn+1 defines a contraction with no fixed points there. Hence it's not closed, thus it's closure contains exactly one more point, the limit of the sequence.

share|improve this answer
3  
Also $X$ is complete iff every closed subspace of $X$ is complete. Thus your theorem is (at least for me) a true converse of Banach's fixed point theorem. –  Martin Brandenburg May 27 '10 at 13:42

As has been pointed out, the putative converse to the Contraction Mapping Theorem suggested in the question is not true. But there is a result which may reasonably be viewed as the converse of CMT.

Theorem (Bessaga, 1959): Let $X$ a set and $f: X \rightarrow X$ a function such that for all $n \in \mathbb{Z}^+$, the iterate $f^n$ has a unique fixed point. Then there exists a complete metric on $X$ with respect to which $f$ is a contraction mapping (for any preassigned constant $c \in (0,1)$).

[Addendum: I just looked at Elekes' paper and saw that it cites this result of Bessaga and says that it is seemingly the earliest converse. So I guess this post is not exactly exciting news. Oh well.]

I learned about this result from a talk that Keith Conrad gave in the Undergraduate Math Club at UGA. For more information, see his "blurb"

http://www.math.uconn.edu/~kconrad/blurbs/analysis/contractionshort.pdf

In later correspondence with him I pointed out the following result, which is now included in his writeup:

Theorem: For a function $f: X \rightarrow X$, the following are equivalent:
(i) Every iterate $f^n$ has at most one fixed point.
(ii) There is a metric (not necessarily complete!) with respect to which $f$ is a contraction.

This is not an earth-shattering result but it has a nice, crisp statement and afterwards I decided that it was too good to be true that I was the first to think of it. And I was right -- after a quick internet search I found the result in a published paper. (Unfortunately I didn't take note of the reference. Sorry, K.)

share|improve this answer
2  
I think Bessaga's result is interesting in that it suggest that, in order to solve a fixed point problem T(x)=x, where unicity is suspected (together with unicity of periodic points), then one should rather look for a convenient distance that makes T a contraction, instead of creating another variant of the Banach contraction theorem (Btw, there are thousands of generalizations of the contraction theorem, but many of them reduce to the classic case with a smart distance). –  Pietro Majer May 27 '10 at 9:56
1  
Pietro, that is a very good interpretation of what Bessaga's result means practically! (I say "practically" because the proof itself creates a very strange metric to achieve its goal, if I recall correctly.) Wolfang Walter came up with a proof of the Cauchy-Kovalevskaya theorem using the contraction mapping theorem precisely because the uniqueness in CK theorem plus Bessaga's result suggested there ought to be some contraction out there which would prove the CK theorem. Thus inspired, he searched around and found a metric. See Amer. Math. Monthly 92 (1985), 115--126. –  KConrad May 28 '10 at 0:57
    
Pete, if you locate the reference again, let me know. –  KConrad May 28 '10 at 0:58
    
@K: Here it is: tmna.ncu.pl/files/v15n1-14.pdf –  Pete L. Clark May 28 '10 at 1:19

This is now an old thread, but I just came across it. The question you are asking was asked by Behrends a couple of years ago, and he knew about the counter example on the plane that Gjergji points out. Behrends was specifically asking for an incomplete metric space that is a subset of the line and has the fixed point property.

I came up with a partition of $\mathbb R$ into two dense sets $X_0$ and $X_1$ such that for all $i\in\{0,1\}$, every map $f:X_i\to X_i$ that satisfies $$\forall x,y\in X_i(x\not=y\rightarrow|f(x)-f(y)|<|x-y|)$$ is actually constant (and in particular has a fixed point). The $X_i$ can be constructed by an easy transfinite recursion and there is no control of how complicated the sets are. This is the huge advantage of Elekes' examples which are Borel.

The notes with my proof are here: http://www.hausdorff-center.uni-bonn.de/people/geschke/papers/Behrends.pdf

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.