0
$\begingroup$

prove or disprove: Let $f:[0,1]\rightarrow[0,1]$ be a monotone (need not be strict) function then f has a fixed point.

Can I have a hint?

$\endgroup$
  • $\begingroup$ But no continuity is given $\endgroup$ – Selvakumar A Mar 20 '18 at 11:44
  • $\begingroup$ I tried it but not succeeded. $\endgroup$ – Selvakumar A Mar 20 '18 at 11:46
  • 1
    $\begingroup$ Well, now you changed the question, yes it can. Take $f(x)=x$. But fixed points do not always exist for monotone functions in general. $\endgroup$ – The Phenotype Mar 20 '18 at 11:47
  • $\begingroup$ But in this case, I think it will that's why I asked proof. $\endgroup$ – Selvakumar A Mar 20 '18 at 11:49
  • $\begingroup$ I'll give you a way to visualize the problem: draw the plane $[0,1]\times [0,1]$ and $y=x$. Now construct any (discontinuous) function that does not intersect $y=x$. $\endgroup$ – The Phenotype Mar 20 '18 at 11:50
4
$\begingroup$

This is a special case of the Knaster-Tarski fixed point theorem.

Suppose $f:[0,1] \to [0,1]$ is any monotonous function, i.e. whenever we have $x \le y$ in $[0,1]$ we have $f(x) \le f(y)$. (no continuity assumptions).

Define $A = \{x \in [0,1]: x \le f(x)\}$. The set $A$ is non-empty, as $0 \in A$.

So by completeness of $\mathbb{R}$ (every bounded above non-empty set has a supremum, and $1$ surely is an upperbound) $s:= \sup(A) \le 1$ exists. I claim that $f(s) = s$.

To see this: if $x \in A$ then $x \le s$, so $x\le f(x) \le f(s)$, and as $x \in A$ is arbitary, $f(s)$ is an upperbound for $A$ as well and $s$ is the least upper bound for $A$, so $s \le f(s)$.

$s \le f(s)$ shows that in fact $s \in A$ itself, and also implies that $f(s) \le f(f(s))$, which shows that $f(s) \in A$ as well. This implies $f(s) \le s$ (as $s$ is an upperbound for $A$) and so $f(s) = s$ from both inequalities.

So $f$ has a fixed point. If $f$ is monotonous the other way round ($x \le y \rightarrow f(x) \ge f(y)$) adapt the argument using $\inf$ e.g. (Or compose with an order reversing bijection of $[0,1]$, like $h(x) = 1-x$ and apply the above to the composed map first).

$\endgroup$
  • 1
    $\begingroup$ You said you assume any monotone function, but infact you assumed a non-decreasing one. And a decreasing function may miss a fixed point, e.g. $f(x)=1-x/2$ for $0\le x\le 0.5$ and $f(x)=(1-x)/2$ for $0.5 < x\le 1$. $\endgroup$ – CiaPan Mar 20 '18 at 12:31
  • $\begingroup$ Actually, he assumes increasing $\endgroup$ – Selvakumar A Mar 20 '18 at 15:12
  • $\begingroup$ @SelvakumarA: the function $f(x)=\frac12$ meets the constraints of the answer, so $f$ is non-decreasing, not necessarily increasing. $\endgroup$ – robjohn Mar 20 '18 at 22:31
  • $\begingroup$ Your last paragraph is obscure, because you neglected to state a conclusion. It sounds as if you are saying that a function $f$ such that $x\le y\to f(x)\ge f(y)$ has a fixed point, which is of course false. $\endgroup$ – bof Jan 24 at 10:25
2
$\begingroup$

This might be a somewhat simpler argument.

Suppose that $f:[0,1]\mapsto[0,1]$ is non-decreasing and assume that $f$ has no fixed point.

Define $$ s=\sup\{x:f(x)\gt x\} $$ Note that $0\in\{x:f(x)\gt x\}$, so $s\in[0,1]$.

If $f(s)\gt s$, then for all $x\in(s,f(s))$, we must have $\ f(x)\lt x$ by the definition of $s$. But then $f(x)\lt x\lt f(s)$ contradicts that $f$ is non-decreasing.

If $f(s)\lt s$, then, by the definition of $s$, there must be some $x\in(f(s),s)$ so that $f(x)\gt x$. But then $f(s)\lt x\lt f(x)$ contradicts that $f$ is non-decreasing.

Thus, the assumption that $f$ has no fixed point must be false.

$\endgroup$
0
$\begingroup$

Let $g(x):[0,1]$ be a monotone function. Suppose that $g$ has no fixed points. Then $g(x)\neq x$ for all $x\in [0,1]$, so that we can decompose $[0,1]$ into two (non empty) disjoint sets: $$ [0,1] = \{x: g(x)>x\} \cup \{x:g(x)<x\} = G^+ \cup G^-, \quad G^+\cap G^- = \emptyset, \quad 0 \in G^+,\ 1\in G^-. $$ Now let $\delta = \sup G^+$. I claim that $\delta \in G^+$. Indeed, by definition of the sup, there is a sequence $x_n \uparrow \delta, x_n\in G^+$ for all $n\in \mathbb{N}$. Then $$ g(\delta)\geq g(x_n) >x_n, \quad g(\delta)\geq \lim_n x_n = \delta. $$ Since $g(\delta)\neq \delta$ we conclude that $g(\delta) > \delta$ and $\delta \in G^+$. Now, since $\delta = \sup G^+$ and $\delta<1$, the interval $(\delta, 1]\subset G^-$. Now let $x_n \in G^-, x_n \downarrow \delta$. We obtain $$ g(\delta)\leq g(x_n)<x_n, \quad g(\delta)\leq \lim_n x_n = \delta, $$ and again, since $g(\delta)\neq \delta$, $g(\delta)<\delta$. So $\delta \in G^-$, but this is contradiction since $G^-\cap G^+=\emptyset$.

This shows that $g$ has a fixed point. In particular we showed that, if $g(0)>0$ and $g(1)<1$, then $g(\delta)=\delta$.

$\endgroup$
0
$\begingroup$

If you allow decreasing functions, counterexamples are easy . . .

For a counterexample where $f$ is non-strictly decreasing, let $f:[0,1]\to [0,1]$ be defined by $$ f(x)= \begin{cases} 1&\text{if}\;x=0 \qquad\;\;\;\;\;\,\\[4pt] 0&\text{otherwise} \end{cases} $$ For a counterexample where $f$ is strictly decreasing, let $f:[0,1]\to [0,1]$ be defined by $$ f(x)= \begin{cases} 1-\frac{x}{2}&\text{if}\;x < \frac{1}{2}\\[4pt] \frac{1}{2}-\frac{x}{2}&\text{otherwise} \end{cases} $$ On the other hand . . .

Claim:

If $f:[0,1]\to [0,1]$ is monotonically (not necessarily strictly) increasing, then $f$ has a fixed point.

Proof:

Suppose $f:[0,1]\to [0,1]$ is a monotonically (not necessarily strictly) increasing function such that $f$ does not have a fixed point.

Our goal is to derive a contradiction.

Let $A=\{x\in [0,1]\mid f(x) > x\}$, and let $B=\{x\in [0,1]\mid f(x) < x\}$.

Since $f$ has no fixed point, we get $f(0) > 0$, and $f(1) < 1$, so we have $0 \in A$, and $1\in B$.

Then $A,B$ are nonempty, disjoint, and $A \cup B = [0,1]$.

Let $c=\text{glb}(B)$, and let $d=f(c)$.

Consider two cases . . .

Case $(1)$:$\;c\in A$.

Then $f(c) > c$, hence $f(f(c)) \ge f(c)$, so $f(d) \ge d$.

Since $f$ has no fixed point, we get $f(d) > d$.

Thus, $c < f(c) = d < f(d)$.

Since $c=\text{glb}(B)$, and $c \notin B$, there exists $b\in B$, with $c < b < d$. \begin{align*} \text{Then}\;\;&c < b\\[4pt] \implies\;&f(c) \le f(b)&&\text{[by monotonicity of $f$]}\\[4pt] \implies\;&d \le f(b)&&\text{[since $d=f(c)$]}\\[4pt] \implies\;&b < f(b)&&\text{[since $b < d$]}\\[4pt] \end{align*} contrary to $b\in B$.

Case $(2)$:$\;c\in B$. \begin{align*} \text{Then}\;\;&d = f(c)\\[4pt] \implies\;&d < c&&\text{[since $f(c) < c$]}\\[4pt] \implies\;&f(d) \le f(c)&&\text{[by monotonicity of $f$]}\\[4pt] \implies\;&f(d) \le d&&\text{[since $d=f(c)$]}\\[4pt] \implies\;&f(d) < d&&\text{[since $f$ has no fixed points]}\\[4pt] \implies\;&d \in B\\[4pt] \end{align*} contradiction, since $c=\text{glb(B)}$, and $d < c$.

Thus, both cases yield a contradiction, which completes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.