1

So we have a function $f: \mathbb{R} \rightarrow \mathbb{R}$ which is a contraction mapping. Can we find any example of $f$ that has no fixed points? We take into account standard Euclidean distance.

Norbert Dąbrowski
  • 121

1 Answers1

3

We have the Banach fixed-point theorem, which says you cannot.

The intuition: if you are in a metric space which is complete (meaning all Cauchy sequences have a limit), then a contraction applied to an arbitrary starting point will define a Cauchy sequence through its iterations, which in turn defines a limit. With some work, you can show that the limit of this sequence is a fixed point of the function. With a bit more work, you show that actually any such sequence gives you the same fixed point, regardless of the starting point, so you even get uniqueness!

Good point from the comments: In this context, a contraction is understood as a function $f$ such that $$ d(f(x), f(y)) \leq c d(x, y),$$ uniformly, for some constant $c <1$. Having $$ d(f(x), f(y)) < d(x, y),$$ is not sufficient, as one can concoct counterexamples!

R_B
  • 1,589
  • 4
    And notice how important that $|f(x)-f(y)|/|x-y|$ is not just less than $1$ but universally bounded by a constant less than $1$: otherwise $f(x) = x - \arctan x - \frac\pi2$ would be a counterexample. – Greg Martin May 29 '20 at 07:32
  • Okay, on the other hand. We know that definition of contraction is that there exists $\alpha \in (0,1)$ that for all $x$ and $y$ we have $|f(x) - f(y)| \leq \alpha |x-y|$ if it comes to metric space that I talked about before. I am wondering, if we could swap quantifiers and find function $f: \mathbb{R}\to \mathbb{R}$ such that: $$\forall_{x,y\in\mathbb{R}} \exists_{\alpha\in(0,1)} |f(x)-f(y)|\leq \alpha |x-y|$$ and has no fixed points. – Norbert Dąbrowski May 30 '20 at 08:22
  • 1
    Norbert, what you describe is relaxing the uniformity requirement. Greg's comment gives an example of such function. – R_B May 30 '20 at 08:59
  • Sorry, I don't get it. I am trying to show that $f(x)$ holds requirments that I talked and I stucked: $$|x-y+\arctan(y)-\arctan(x)| \leq |x-y| + |\arctan(y)-\arctan(x)|$$ What's next? – Norbert Dąbrowski May 30 '20 at 13:07
  • 1
    Don't do it directly; compute the derivative of $f$ and use the mean value theorem. – R_B May 30 '20 at 14:23
  • I know this theorem, but I am not sure how to use it – Norbert Dąbrowski May 31 '20 at 07:13
  • 1
    The mean value theorem gives you, for every pair $x, y$, $x < y$, $$\frac{f(y)-f(x)}{y-x} = f'(c)$$ for some $c \in [x, y]$. Call the left hand side $L$, you want to show $|L| < 1$ holds but $|L| \leq c < 1$ does not hold for any $c\in(0, 1)$. You can prove this for the right hand side, $f'(c)$, instead, by proving it for $f'$ at every point. – R_B May 31 '20 at 07:36
  • Ohhh yes! Thank you very much! Now I see it. – Norbert Dąbrowski May 31 '20 at 09:05