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

2. Originally Posted by Bruno J.
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.

3. Originally Posted by Drexel28
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.

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

4. Originally Posted by Bruno J.
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!

5. Originally Posted by undefined
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!

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

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

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

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

10. 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 $\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!

11. Originally Posted by Dinkydoe
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?

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

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

14. 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?

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

Page 1 of 2 12 Last