Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - [SOLVED] Fixed point

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    [SOLVED] Fixed point

    Let f:[0,1] \rightarrow [0,1] be increasing. Show that there exists a \in [0,1] such that f(a)=a.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Let f:[0,1] \rightarrow [0,1] be increasing. Show that there exists a \in [0,1] such that f(a)=a.
    I have not given this an extreme amount of thought, but my first guess is to consider \left\{f^n(0)\right\}_{n\in\mathbb{N}}. We first can note that since f([0,1])\subseteq[0,1] that 0\leqslant f(0) and so since f is increasing we have that f(0)\leqslant f(f(0))=f^2(0) and so f^2(0)\leqslant f^3(0) and thus by induction f^n(0)\leqslant f^{n+1}(0). Thus, \left\{f^n(0)\right\}_{n\in\mathbb{N}} is a bounded monotone sequence and so by the monotone convergence theorem it is convergent with limit \alpha\in[0,1]. So, I have absolutely no proof (yet) but it may be true that \alpha is the fixed point. If f were continuous this would obviously be true since f(\alpha)=f\left(\lim_{n\to\infty}f^n(0)\right)=\l  im_{n\to\infty}f^{n+1}(0)=\alpha. But, from there I'm not sure yet.

    That said, I feel that can't be right. The fact that [0,1] is compact seems like it should come into play.

    Just some input.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Drexel28 View Post
    I have not given this an extreme amount of thought, but my first guess is to consider \left\{f^n(0)\right\}_{n\in\mathbb{N}}. We first can note that since f([0,1])\subseteq[0,1] that 0\leqslant f(0) and so since f is increasing we have that f(0)\leqslant f(f(0))=f^2(0) and so f^2(0)\leqslant f^3(0) and thus by induction f^n(0)\leqslant f^{n+1}(0). Thus, \left\{f^n(0)\right\}_{n\in\mathbb{N}} is a bounded monotone sequence and so by the monotone convergence theorem it is convergent with limit \alpha\in[0,1]. So, I have absolutely no proof (yet) but it may be true that \alpha is the fixed point. If f were continuous this would obviously be true since f(\alpha)=f\left(\lim_{n\to\infty}f^n(0)\right)=\l  im_{n\to\infty}f^{n+1}(0)=\alpha. But, from there I'm not sure yet.

    That said, I feel that can't be right. The fact that [0,1] is compact seems like it should come into play.

    Just some input.
    Something to consider : what about this function?

    Let i_0=0 and let i_n=i_{n-1}+\frac{1}{2^{n+1}} for n>0.

    The sets [i_0, i_1)= \left[0, \frac{1}{4}\right), [i_1, i_2) = \left[\frac{1}{4}, \frac{3}{8}\right), \dots partition [0, 1/2). Now let f(x)=i_n if x \in [i_{n-1}, i_n) and f(x)=1 for x \in \left[\frac{1}{2}, 1\right]. Clearly this function is increasing. In particular we have f(1/2)=1. But f(0)=1/4, f(1/4)=3/8, f(3/8)=7/16, \dots converges to 1/2, and yet f(1/2)\neq 1/2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bruno J. View Post
    Let f:[0,1] \rightarrow [0,1] be increasing. Show that there exists a \in [0,1] such that f(a)=a.
    I'm wondering whether this more general proposition is also true:

    Let f:[0,1] \rightarrow [0,1] be increasing, and let g:[0,1] \rightarrow [0,1] be continuous and increasing, with g(0) = 0 and g(1) = 1. Then there exists a \in [0,1] such that f(a)=g(a).

    I don't think I'm mathematically equipped for these kinds of proofs presently, though. Need to study more!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by undefined View Post
    I'm wondering whether this more general proposition is also true:

    Let f:[0,1] \rightarrow [0,1] be increasing, and let g:[0,1] \rightarrow [0,1] be continuous and increasing, with g(0) = 0 and g(1) = 1. Then there exists a \in [0,1] such that f(a)=g(a).

    I don't think I'm mathematically equipped for these kinds of proofs presently, though. Need to study more!
    I'd say it's definitely true, and I'll see if I can adapt my proof to this beautiful generalization!

    Tomorrow though. There's a time for sleep and a time for math - the boundaries of both often blend together, but healthy living requires there be a time of the day where they unambiguously intersect!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bruno J. View Post
    I'd say it's definitely true, and I'll see if I can adapt my proof to this beautiful generalization!

    Tomorrow though. There's a time for sleep and a time for math - the boundaries of both often blend together, but healthy living requires there be a time of the day where they unambiguously intersect!
    I like your ideas on sleep!

    What if we went even further and removed the restriction that g is increasing? While we're at it, also change the codomain of g so that now g:[0,1] \rightarrow \mathbb{R}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Hmm I was just going to use the Intermediate value theorem but then I saw you haven't stated f is continuous so trouble...

    Let f(x) = F(x) - x

    We have that F(0) \geq 0 and F(1) \leq 1.

    Then at this point I would've said. By IVT there exists an \alpha etc... But I need continuity... Hmm will think some more.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    If f(0) = 0 or f(1) = 1 there is nothing to prove. So we may assume that f(0) > 0 and f(1) < 1.

    Let A = \{x\in[0,1]:0\leqslant y\leqslant x\;\Rightarrow\;y\leqslant f(y)\}. Then A is nonempty because 0\in A. Let u = \sup A, and notice that u > 0 because [0,f(0)]\subseteq A. Given \varepsilon with 0<\varepsilon<u, u-\varepsilon \leqslant f(u-\varepsilon) \leqslant  f(u) (since f is increasing). Therefore u \leqslant f(u). If u = 1 that would imply f(1) = 1, so we may assume that u < 1.

    Then given \delta>0 there exists a point v\in[0,1] with u<v<u+\delta such that v\notin A and therefore there exists w with u < w < v such that f(w)<w. So f(u)\leqslant f(w) < w < u+\delta. Since this holds for all \delta>0 it follows that f(u)\leqslant u.

    Therefore f(u) = u.

    I haven't checked carefully, but I think that this argument will extend to deal with undefined's generalisations of the problem.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Just my few cents here. Please correct me where I'm wrong, but I believe the idea is ok.

    Let f:[0,1]\to [0,1] increasing and suppose there's no such \alpha then we either have f(x)<x or f(x)>x and we can partition [0,1] = S\cup T where S= \left\{x:f(x)>x\right\} and T =\left\{x:f(x)<x\right\}. Observe that S and T are non-empty since 0\in S and 1\in T

    From this we can conclude that S and T must at least consist of a countable set of points, since x_0\in S\rightarrow f(x_0)\in S. Idem for T.

    To show this is true, let x_0\in S and suppose that f(x_0)\in T then f(f(x_0))<f(x_0). Then we either have x_0<f(f(x_0))< f(x_0) or f(f(x_0))<x_0<f(x_0) and this contradicts the fact that f increases. (for increasing f we'd have x_1< x_2 \rightarrow f(x_1)\leq f(x_2)) Similar things can be said for T.

    This is where I feel a nice topological argument would be in it's place, although I couldn't think of any good one.

    Anyway, we can safely assume there's a p\in \overline{S}\cap \overline{T}. Suppose p\in T then by the above observations f(p)\in T\cap [0,p) and we can find x_n\in (p-\epsilon,p)\cap S such that f(x_n) is close enough to p that f(p)< f(x_n). And since x_n< p this contradicts that f increases.

    Similar things can be said for p\in S. I believe this is the desired contradiction.
    Last edited by Dinkydoe; May 7th 2010 at 08:54 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Opalg View Post
    If f(0) = 0 or f(1) = 1 there is nothing to prove. So we may assume that f(0) > 0 and f(1) < 1.

    Let A = \{x\in[0,1]:0\leqslant y\leqslant x\;\Rightarrow\;y\leqslant f(y)\}. Then A is nonempty because 0\in A. Let u = \sup A, and notice that u > 0 because [0,f(0)]\subseteq A. Given \varepsilon with 0<\varepsilon<u, u-\varepsilon \leqslant f(u-\varepsilon) \leqslant  f(u) (since f is increasing). Therefore u \leqslant f(u). If u = 1 that would imply f(1) = 1, so we may assume that u < 1.

    Then given \delta>0 there exists a point v\in[0,1] with u<v<u+\delta such that v\notin A and therefore there exists w with u < w < v such that f(w)<w. So f(u)\leqslant f(w) < w < u+\delta. Since this holds for all \delta>0 it follows that f(u)\leqslant u.

    Therefore f(u) = u.

    I haven't checked carefully, but I think that this argument will extend to deal with undefined's generalisations of the problem.
    Excellent as usual Oplag!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Dinkydoe View Post
    Just my few cents here. Please correct me where I'm wrong, but I believe the idea is ok.

    Let f:[0,1]\to [0,1] increasing and suppose there's no such \alpha then f strictly increases.
    Why?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Why?
    Good you mentioned it. It's an error on my part, but I didn't use it anywhere

    Except for some side-comment in the middle, "strictly" increasing can be replaced by 'increasing'. I'll edit my post if you don't mind.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    I'm still not convinced by your proof! I do not see why this line

    Suppose then by the above observations and we can find such that is close enough to that . And since this contradicts that increases.
    is true. Is it true for all shared boundary points p that ?
    Why can we find such an interval to the left of p all of which lies in T?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    If p\in T then by definition of Twe have f(p)<p and since f(p)\in Twe obtain f(p)\in [0,p)\cap T.

    But if p\in S then f(p)\in S and f(p)>p and we get f(p)\in (p,1]\cap S
    Then we make the reversed argument: we can find x_n\in (p,p+\epsilon)\cap T close enough to p such that f(x_n)< f(p). Again since p< x_n this contradicts that f increases.

    But maybe you're right. It doesn't feel as water-tight proof ;p

    About you're second question. I don't see where I made such an assumption. Maybe implicitly?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    I just want to mention, that this is a special case of Knaster-Tarski theorem, which holds in complete lattices. It says that every order-preserving function f:L->L has a fixpoint, if L is a complete lattice. (In fact, it claims even more, but this is what is needed here.)

    In fact, the proof of this theorem at wikipedia is similar to Opalg's one.

    Knaster-Tarski theorem can be used to make a nice and short proof of Cantor-Bernstein theorem.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. show that f has a fixed point
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 19th 2011, 09:05 AM
  2. Fixed point iteration help
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: November 8th 2011, 12:19 PM
  3. The fixed point
    Posted in the Geometry Forum
    Replies: 0
    Last Post: April 2nd 2011, 11:57 AM
  4. [SOLVED] Fixed Point
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 2nd 2009, 09:27 AM
  5. fixed point?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 1st 2006, 02:46 AM

Search Tags


/mathhelpforum @mathhelpforum