Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fiexed point theorem for contractions

  1. Jul 28, 2008 #1
    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.
     
  2. jcsd
  3. Jul 28, 2008 #2
    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: Jul 28, 2008
  4. Jul 28, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  5. Jul 31, 2008 #4

    gel

    User Avatar

    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
    [tex]X\supseteq f(X)\supseteq f^2(X)\supseteq f^3(X)\supseteq\cdots[/tex]
    but that doesn't work. Can still find C using transfinite induction, but that seems rather complicated for such a simple question.
     
  6. Aug 1, 2008 #5
    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: Aug 1, 2008
  7. Aug 1, 2008 #6
    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: Aug 1, 2008
  8. Aug 1, 2008 #7

    gel

    User Avatar

    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).
     
  9. Aug 1, 2008 #8

    gel

    User Avatar

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

    for every ordinal [itex]\alpha[/itex] (finite or infinite) define [itex]f^\alpha(X)[/itex] inductively by
    [tex]
    \begin{align*}
    &f^0(X)=X,\\
    &f^{\alpha+1}(X)=f(f^\alpha(X)),\\
    &f^\alpha(X)=\bigcap_{\beta<\alpha}f^
    \beta(X)\ \ \textrm{if $\alpha$ is a limit ordinal}
    \end{align*}
    [/tex]
    Transfinite induction says that this is well defined, and [itex]f^\alpha(X)[/itex] 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, [itex]C=f^\alpha(X)=f^{\alpha+1}(X)=f(C)[/itex].

    Also, by induction and the compactness of X, every [itex]f^\alpha(X)[/itex] will be closed and nonempty.


    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: Aug 1, 2008
  10. Aug 1, 2008 #9
    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 [itex]f^\alpha(X)[/itex] will eventually be constant.

    [itex]f^\alpha(X)[/itex] could be any subset of X with cardinality equal or less to [itex]f^{\alpha-1}(X)[/itex]. Intuitively, if the cardinality of X is finite, then the cardinality of [itex]f^\alpha(X)[/itex] 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: Aug 1, 2008
  11. Aug 1, 2008 #10

    gel

    User Avatar

    If you're familiar with Zorn's Lemma, you could also use that, applied to the non-empty closed subsets of X satisfying [itex]f(S)\subseteq S[/itex], 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 [itex]f^\alpha(X)[/itex] is eventually constant is the same as the reason why this Sketch of the proof of Zorn's lemma 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: Aug 1, 2008
  12. Aug 1, 2008 #11
    Mmm... that's all a little over my head right now. I'll meditate on it.
     
  13. Aug 2, 2008 #12
    Since X is compact, then there for a sequence [tex]{x_{n}[/tex] converges to x in X; but
    [tex]d(f(x_{n}),f(x)) \leq c d(x_{n},x)[/tex] such that [tex]{f(x_{n} \rightarrow f(x)[/tex].

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

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

    Then [tex]d(x,y)=0[/tex] 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).
     
  14. Aug 2, 2008 #13
    Since X is compact, every sequence has a convergent subsequence. But nothing tells us that any particular convergent subsequence satisfies [tex]f(x_{n})= x_{n+1}[/tex].
     
  15. Aug 2, 2008 #14

    gel

    User Avatar

    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.
     
  16. Aug 2, 2008 #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.
     
  17. Aug 2, 2008 #16

    gel

    User Avatar

    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.
     
  18. Aug 2, 2008 #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.
     
  19. Aug 2, 2008 #18

    gel

    User Avatar

    ok, here's another method that just occured 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.
     
  20. Aug 2, 2008 #19
    It's not obvious to me why this needs to be so.
     
  21. Aug 2, 2008 #20

    gel

    User Avatar

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Fiexed point theorem for contractions
  1. A point-set theorem (Replies: 22)

  2. Contractive Sequences (Replies: 1)

Loading...