[SOLVED] Fixed point

**Bruno J.** · May 5th 2010, 06:29 PM

Let $f:[0,1] \rightarrow [0,1]$ be increasing. Show that there exists $a \in [0,1]$ such that $f(a)=a$ .

**Drexel28** · May 5th 2010, 09:00 PM

Originally Posted by Bruno J.

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.

**Bruno J.** · May 5th 2010, 09:42 PM

Originally Posted by Drexel28

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$ .

**undefined** · May 5th 2010, 10:01 PM

Originally Posted by Bruno J.

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!

**Bruno J.** · May 5th 2010, 10:09 PM

Originally Posted by undefined

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!

**undefined** · May 5th 2010, 10:39 PM

Originally Posted by Bruno J.

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}$ .

**Deadstar** · May 6th 2010, 03:32 AM

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.

**Opalg** · May 6th 2010, 05:33 AM

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.

**Dinkydoe** · May 6th 2010, 05:49 AM

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.

**Bruno J.** · May 7th 2010, 07:32 AM

Originally Posted by Opalg

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!

**Bruno J.** · May 7th 2010, 07:33 AM

Originally Posted by Dinkydoe

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?

**Dinkydoe** · May 7th 2010, 07:50 AM

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.

**Bruno J.** · May 7th 2010, 08:04 AM

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$ ?

**Dinkydoe** · May 7th 2010, 08:30 AM

If $p\in T$ then by definition of $T$ we have $f(p)<p$ and since $f(p)\in T$ we 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?

**kompik** · May 7th 2010, 08:34 AM

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.

Thread: [SOLVED] Fixed point

LinkBack

Thread Tools

Display

[SOLVED] Fixed point

Similar Math Help Forum Discussions

show that f has a fixed point

Fixed point iteration help

The fixed point

[SOLVED] Fixed Point

fixed point?

Search Tags