Fiexed point theorem for contractions

  • Thread starter Thread starter Epsilon36819
  • Start date Start date
  • Tags Tags
    Point Theorem
Epsilon36819
Messages
32
Reaction score
0
I apologize in advance for starting yet another thread, but I would really like to have some feedback on this one.

I have a "proof" of the theorem, which surely is wrong because it relaxes one of the conditions. Start with the "official" statement:

Let X be a compact metric space, f:X->X, and d(f(x),f(y)) < d(x,y) (or alternatively, d(f(x),f(y)) < a*d(x,y), 0<a<1) when x /= y. Then there exists a (unique) point x in X such that x=f(x).

Pf (of existence): Define x_n+1 = f(x_n). Since X is compact, the sequence {x_n} contains a convergent subsequence, say {x_n_k} with x_n_k --> x and x is in X. This implies that f(x) is also in X. d(f(x),f(y)) < d(x,y) implies that f is (uniformly) continuous, so x_n_k+1 = f(x_n_k) --> f(x). The limit point thus has the desired property.

Surely, this is wrong as the only condition I need is continuity of f. But somehow, I cannot figure out which step(s) is wrong.

Any help greatly appreciated.
 
Physics news on Phys.org
Aggrh... x_n_k+1 /= f(x_n_k). Actually, x_n_k+1 = f(x_p) with p the previous integer. This prevents me from equating both limits.
 
Last edited:
Roughly speaking, the proof of this fixed point theorem uses the fact that on every repeat of f, the (compact) set is mapped into a smaller set. Repeating that infinitely causes the entire set to converge to a single point, the fixed point. If you only have |f(x)- f(y)|< |x- y|, rather than |f(x)- f(y)|<= c|x-y| with c< 1, there is the possibility that the sequence, starting at different initial points converge to different limits: the entire set converges to the boundary of some non-trivial subset.
 
HallsofIvy said:
If you only have |f(x)- f(y)|< |x- y|, rather than |f(x)- f(y)|<= c|x-y| with c< 1, there is the possibility that the sequence, starting at different initial points converge to different limits: the entire set converges to the boundary of some non-trivial subset.

That doesn't look right. If X is compact there should be a unique fixed point.

First, as f is continuous there is a non-empty closed subset C with f(C) = C (*).

Let x,y in C maximize d(x,y). Then there are x', y' in C with f(x')=x, f(y')=y and if x' != y' this implies d(x,y)=d(f(x'),f(y'))<d(x',y') isn't maximal. So the only possibility is x'=y', and x=y. So C contains only one point, which will be the unique fixed point of f.

(*) Is the existence of C obvious? I was going to say take the intersection of the sequence
X\supseteq f(X)\supseteq f^2(X)\supseteq f^3(X)\supseteq\cdots
but that doesn't work. Can still find C using transfinite induction, but that seems rather complicated for such a simple question.
 
We can get rid of the need for C by letting g(x)= d(f(x),x). Then g(x) <= d(f(x),f(y)) + g(y) + d(x,y) so that g(x) - g(y) < 2*d(x,y). By letting x --> y, we obtain |g(x) - g(y)| < 2*d(x,y). Since g is continuous, if X is compact, g will attain a minimum, say g(p). If g(p)>0, then g(f(p)) = d(f(f(p)),f(p) < d(f(p),p) = g(p), a contradiction.
 
Last edited:
Come to think of it, the existence of C isn't obvious, at least to me. The proof you gave proves unicity, but not existence.
 
Last edited:
Sorry, I read HallsofIvy's post as saying the result was only true for |f(x)-f(y)| <= c|x-y|, c< 1, not in the more general case with |f(x)-f(y)|<1. Looks like I just misread it, and actually agree with what he said (I think).
 
Epsilon36819 said:
Come to think of it, the existence of C isn't obvious, at least to me. The proof you gave proves unicity, but not existence.

The proof of existence of C that occurs to me is the following:

for every ordinal \alpha (finite or infinite) define f^\alpha(X) inductively by
<br /> \begin{align*}<br /> &amp;f^0(X)=X,\\<br /> &amp;f^{\alpha+1}(X)=f(f^\alpha(X)),\\<br /> &amp;f^\alpha(X)=\bigcap_{\beta&lt;\alpha}f^<br /> \beta(X)\ \ \textrm{if $\alpha$ is a limit ordinal}<br /> \end{align*}<br />
Transfinite induction says that this is well defined, and f^\alpha(X) will eventually be constant, equal to some set C (otherwise you would have a 1-1 map from the proper class of ordinals into a set).
Then, C=f^\alpha(X)=f^{\alpha+1}(X)=f(C).

Also, by induction and the compactness of X, every f^\alpha(X) will be closed and nonempty.
Epsilon36819 said:
We can get rid of the need for C by letting g(x)= d(f(x),x). Then g(x) <= d(f(x),f(y)) + g(y) + d(x,y) so that g(x) - g(y) < 2*d(x,y). By letting x --> y, we obtain |g(x) - g(y)| < 2*d(x,y). Since g is continuous, if X is compact, g will attain a minimum, say g(p). If g(p)>0, then g(f(p)) = d(f(f(p)),f(p) < d(f(p),p) = g(p), a contradiction.

Ah, that's a much simpler proof of the original theorem. The existence of C is something much more general, but not needed here.
 
Last edited:
gel said:
Transfinite induction says that this is well defined, and f^\alpha(X) will eventually be constant, equal to some set C (otherwise you would have a 1-1 map from the proper class of ordinals into a set).

Mind you, I am absolutely not familiar with ordinals and transfinite induction, but with what I know, I am not sure why you say that f^\alpha(X) will eventually be constant.

f^\alpha(X) could be any subset of X with cardinality equal or less to f^{\alpha-1}(X). Intuitively, if the cardinality of X is finite, then the cardinality of f^\alpha(X) must become constant, but why should the set be constant? I could picture subsets A and B of X s.t. f^{\2k}(X)=A and f^{\2k+1}(X)=B, in the case that alpha is a natural number.

Again, sorry if I'm just not getting it. I guess I'll have to go surf wikipedia on ordinals now...:smile:
 
Last edited:
  • #10
Epsilon36819 said:
Mind you, I am absolutely not familiar with ordinals and transfinite induction, but with what I know, I am not sure why you say that f^\alpha(X) will eventually be constant.

If you're familiar with Zorn's Lemma, you could also use that, applied to the non-empty closed subsets of X satisfying f(S)\subseteq S, to show that there is a minimal such subset. Which will give you the set C. The transfinite induction approach just avoids the axiom of choice and constructs C in a unique way.

The reason f^\alpha(X) is eventually constant is the same as the reason why this http://en.wikipedia.org/wiki/Zorn's...orn.27s_lemma_.28from_the_axiom_of_choice.29" works.
Note that the class of all ordinals is a proper class, not a set. If it was a set, then this set would itself be an ordinal bigger than (and hence not equal to) any of its elements - a contradiction. It follows that no mapping from the class of ordinals to a set can be 1 to 1. And, any order preserving map into a (partially) ordered set must eventually be constant.
 
Last edited by a moderator:
  • #11
Mmm... that's all a little over my head right now. I'll meditate on it.
 
  • #12
Pf (of existence): Define x_n+1 = f(x_n). Since X is compact, the sequence {x_n} contains a convergent subsequence, say {x_n_k} with x_n_k --> x and x is in X. This implies that f(x) is also in X. d(f(x),f(y)) < d(x,y) implies that f is (uniformly) continuous, so x_n_k+1 = f(x_n_k) --> f(x). The limit point thus has the desired property.

Since X is compact, then there for a sequence {x_{n} converges to x in X; but
d(f(x_{n}),f(x)) \leq c d(x_{n},x) such that {f(x_{n} \rightarrow f(x).

But, f(x_{n})= x_{n+1}, then the sequence { f(x_n) }is a subsequence of the sequence {x_{n} such that f(x)=x which guarantees at least one fixed point.

For x,y in X, then 0 \leq d(x,y) = d(f(x),f(y)) \leq cd(x, y)

Then d(x,y)=0 if and only if x =y by definition of a metric space. Hence, there exists a (unique) point x in X such that x=f(x).
 
  • #13
konthelion said:
Since X is compact, then there for a sequence {x_{n} converges to x in X; but
d(f(x_{n}),f(x)) \leq c d(x_{n},x) such that {f(x_{n} \rightarrow f(x).

But, f(x_{n})= x_{n+1}, then the sequence { f(x_n) }is a subsequence of the sequence {x_{n} such that f(x)=x which guarantees at least one fixed point.

Since X is compact, every sequence has a convergent subsequence. But nothing tells us that any particular convergent subsequence satisfies f(x_{n})= x_{n+1}.
 
  • #14
I think Epsilon36819 was proving the Banach fixed point theorem, which has c<1. If you just have d(f(x),f(y))<d(x,y) then the proof given in post 5 seems to work fine.
 
  • #15
The (wrong) "proof" I initially gave was for the case d(f(x),f(y))<d(x,y). But it doesn't hold for the reason I gave in post 2 (and 13). For the case c<1, HallsofIvy's outline does it.
 
  • #16
I mean, minimize d(x,f(x)), then note that if it is non-zero, d(f(x),f(f(x)))<d(x,f(x)), which would be a contradiction. so d(x,f(x))=0. That's what you said in post 5, and it seems to be a very simple and correct proof. I thought HallsofIvy was simply pointing out why the method you tried in post 1 doesn't work. If you want to try to approach it by iterating f, it does seem that you end up with something like I was saying, which uses transfinite induction.
 
  • #17
Right. I knew how to prove the cases d(f(x),f(y))<d(x,y) (as in post 5) as well as d(f(x),f(y))<= c*d(x,y) (as in the first part of HallsofIvy's post), but I was looking for other proofs. Actually, I'll keep in mind your method and I'll get back to it once I have the proper math background.
 
  • #18
ok, here's another method that just occurred to me.
Let S1, S2 be any two nonempty closed subsets with f(S1) <= S1, f(S2) <= S2.
If x in S1 and y in S2 minimize d(x,y) then, if x != y, d(f(x),f(y))<d(x,y) which is a contradiction. So the intersection of S1 and S2 is nonempty.
By induction, the intersection of any finite set of closed sets Si with f(Si)<=Si is nonempty.
So, by compactness, the intersection of all closed nonempty subsets S with f(S)<=S is nonempty. If this intersection is C, then f(C) = C. My previous argument then shows that C contains a single point.
 
  • #19
gel said:
If this intersection is C, then f(C) = C.

It's not obvious to me why this needs to be so.
 
  • #20
because by construction, C is the smallest non-empty closed set satisfying f(C)<=C. If f(C) != C then you could replace C by f(C), which is smaller.
 
  • #21
Ah! Yes, of course. Good one!
 
Back
Top