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

Thread: [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 $\displaystyle f:[0,1] \rightarrow [0,1]$ be increasing. Show that there exists $\displaystyle a \in [0,1]$ such that $\displaystyle 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
    22
    Quote Originally Posted by Bruno J. View Post
    Let $\displaystyle f:[0,1] \rightarrow [0,1]$ be increasing. Show that there exists $\displaystyle a \in [0,1]$ such that $\displaystyle f(a)=a$.
    I have not given this an extreme amount of thought, but my first guess is to consider $\displaystyle \left\{f^n(0)\right\}_{n\in\mathbb{N}}$. We first can note that since $\displaystyle f([0,1])\subseteq[0,1]$ that $\displaystyle 0\leqslant f(0)$ and so since $\displaystyle f$ is increasing we have that $\displaystyle f(0)\leqslant f(f(0))=f^2(0)$ and so $\displaystyle f^2(0)\leqslant f^3(0)$ and thus by induction $\displaystyle f^n(0)\leqslant f^{n+1}(0)$. Thus, $\displaystyle \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 $\displaystyle \alpha\in[0,1]$. So, I have absolutely no proof (yet) but it may be true that $\displaystyle \alpha$ is the fixed point. If $\displaystyle f$ were continuous this would obviously be true since $\displaystyle 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 $\displaystyle [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 $\displaystyle \left\{f^n(0)\right\}_{n\in\mathbb{N}}$. We first can note that since $\displaystyle f([0,1])\subseteq[0,1]$ that $\displaystyle 0\leqslant f(0)$ and so since $\displaystyle f$ is increasing we have that $\displaystyle f(0)\leqslant f(f(0))=f^2(0)$ and so $\displaystyle f^2(0)\leqslant f^3(0)$ and thus by induction $\displaystyle f^n(0)\leqslant f^{n+1}(0)$. Thus, $\displaystyle \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 $\displaystyle \alpha\in[0,1]$. So, I have absolutely no proof (yet) but it may be true that $\displaystyle \alpha$ is the fixed point. If $\displaystyle f$ were continuous this would obviously be true since $\displaystyle 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 $\displaystyle [0,1]$ is compact seems like it should come into play.

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

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

    The sets $\displaystyle [i_0, i_1)= \left[0, \frac{1}{4}\right), [i_1, i_2) = \left[\frac{1}{4}, \frac{3}{8}\right), \dots$ partition $\displaystyle [0, 1/2)$. Now let $\displaystyle f(x)=i_n$ if $\displaystyle x \in [i_{n-1}, i_n)$ and $\displaystyle f(x)=1$ for $\displaystyle x \in \left[\frac{1}{2}, 1\right]$. Clearly this function is increasing. In particular we have $\displaystyle f(1/2)=1$. But $\displaystyle f(0)=1/4, f(1/4)=3/8, f(3/8)=7/16, \dots$ converges to $\displaystyle 1/2$, and yet $\displaystyle 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 $\displaystyle f:[0,1] \rightarrow [0,1]$ be increasing. Show that there exists $\displaystyle a \in [0,1]$ such that $\displaystyle f(a)=a$.
    I'm wondering whether this more general proposition is also true:

    Let $\displaystyle f:[0,1] \rightarrow [0,1]$ be increasing, and let $\displaystyle g:[0,1] \rightarrow [0,1]$ be continuous and increasing, with $\displaystyle g(0) = 0$ and $\displaystyle g(1) = 1$. Then there exists $\displaystyle a \in [0,1]$ such that $\displaystyle 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 $\displaystyle f:[0,1] \rightarrow [0,1]$ be increasing, and let $\displaystyle g:[0,1] \rightarrow [0,1]$ be continuous and increasing, with $\displaystyle g(0) = 0$ and $\displaystyle g(1) = 1$. Then there exists $\displaystyle a \in [0,1]$ such that $\displaystyle 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 $\displaystyle g$ is increasing? While we're at it, also change the codomain of $\displaystyle g$ so that now $\displaystyle 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 $\displaystyle f(x) = F(x) - x$

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

    Then at this point I would've said. By IVT there exists an $\displaystyle \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
    10
    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 $\displaystyle A = \{x\in[0,1]:0\leqslant y\leqslant x\;\Rightarrow\;y\leqslant f(y)\}$. Then A is nonempty because $\displaystyle 0\in A$. Let $\displaystyle u = \sup A$, and notice that u > 0 because $\displaystyle [0,f(0)]\subseteq A.$ Given $\displaystyle \varepsilon$ with $\displaystyle 0<\varepsilon<u$, $\displaystyle u-\varepsilon \leqslant f(u-\varepsilon) \leqslant f(u)$ (since f is increasing). Therefore $\displaystyle u \leqslant f(u)$. If u = 1 that would imply f(1) = 1, so we may assume that u < 1.

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

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

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

    To show this is true, let $\displaystyle x_0\in S$ and suppose that $\displaystyle f(x_0)\in T$ then $\displaystyle f(f(x_0))<f(x_0)$. Then we either have $\displaystyle x_0<f(f(x_0))< f(x_0)$ or $\displaystyle f(f(x_0))<x_0<f(x_0)$ and this contradicts the fact that $\displaystyle f$ increases. (for increasing $\displaystyle f$ we'd have $\displaystyle x_1< x_2 \rightarrow f(x_1)\leq f(x_2)$) Similar things can be said for $\displaystyle 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 $\displaystyle p\in \overline{S}\cap \overline{T}$. Suppose $\displaystyle p\in T$ then by the above observations $\displaystyle f(p)\in T\cap [0,p)$ and we can find $\displaystyle x_n\in (p-\epsilon,p)\cap S$ such that $\displaystyle f(x_n)$ is close enough to $\displaystyle p$ that $\displaystyle f(p)< f(x_n)$. And since $\displaystyle x_n< p$ this contradicts that $\displaystyle f$ increases.

    Similar things can be said for $\displaystyle p\in S$. I believe this is the desired contradiction.
    Last edited by Dinkydoe; May 7th 2010 at 07: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 $\displaystyle A = \{x\in[0,1]:0\leqslant y\leqslant x\;\Rightarrow\;y\leqslant f(y)\}$. Then A is nonempty because $\displaystyle 0\in A$. Let $\displaystyle u = \sup A$, and notice that u > 0 because $\displaystyle [0,f(0)]\subseteq A.$ Given $\displaystyle \varepsilon$ with $\displaystyle 0<\varepsilon<u$, $\displaystyle u-\varepsilon \leqslant f(u-\varepsilon) \leqslant f(u)$ (since f is increasing). Therefore $\displaystyle u \leqslant f(u)$. If u = 1 that would imply f(1) = 1, so we may assume that u < 1.

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

    Therefore $\displaystyle 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 $\displaystyle f:[0,1]\to [0,1]$ increasing and suppose there's no such $\displaystyle \alpha$ then $\displaystyle 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 $\displaystyle p$ that ?
    Why can we find such an interval to the left of $\displaystyle p$ all of which lies in $\displaystyle T$?
    Follow Math Help Forum on Facebook and Google+

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

    But if $\displaystyle p\in S$ then $\displaystyle f(p)\in S$ and $\displaystyle f(p)>p$ and we get $\displaystyle f(p)\in (p,1]\cap S$
    Then we make the reversed argument: we can find $\displaystyle x_n\in (p,p+\epsilon)\cap T$ close enough to p such that $\displaystyle f(x_n)< f(p)$. Again since $\displaystyle 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: Nov 19th 2011, 08:05 AM
  2. Fixed point iteration help
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: Nov 8th 2011, 11:19 AM
  3. The fixed point
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Apr 2nd 2011, 10:57 AM
  4. [SOLVED] Fixed Point
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: Oct 2nd 2009, 08:27 AM
  5. fixed point?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jan 1st 2006, 01:46 AM

Search Tags


/mathhelpforum @mathhelpforum