2
$\begingroup$

I am trying to show that the function $f(x) = 2\pi+x-\tan^{-1}x$ is contractive but has no fixed points. Finally I wish to conclude that it does not contradict the contraction mapping theorem.

$f$ is contractive:

by the mean value theorem we have:

\begin{align} |f(x)-f(y)| =& |f'(x)(x-y)| \end{align} It is sufficient to show that $f'(x) < 1$: \begin{align} f'(x) =& 1 - \frac{1}{1+x^2} \\ =& \frac{x^2}{1+x^2} \end{align}

$f$ has no fixed points:

Suppose $f$ does have a fixed point. Then $\lim_{x_n\to\infty} = x:$ \begin{align} x_{n+1} =& 2\pi + x_n - \arctan(x_n) \\ \lim x_{n+1} =& \lim 2\pi + x_n - \arctan(x_n) \\ x =& 2\pi +x - \arctan(x) \\ 0 =& 2\pi - \arctan(x) \end{align} This is a contradiction as $\frac{-\pi}{2} < \arctan(x) < \frac{\pi}{2}$ for all $x$. Thus $f$ does not have a fixed point.

Now I am stuck on how to show that this does not contradict the contraction mapping theorem which says:

Let $C$ be a closed subset of the real line. If $F$ is a contractive mapping of $C$ into $C$ then $F$ has a unique fixed point. Morever, this fixed point is the limit of every sequence obtained from $x_n+1 = F(x)$ starting with $x_0\in C$.

For $f(x) = 2\pi+x-\arctan(x)$ the domain is all reals and so is the codomain. I don't see another premise that is violated by $f(x)$.

Thanks for all the help.

$\endgroup$
  • $\begingroup$ What is your closed subset $C$ such that $F:C \to C$? $\endgroup$ – Adrian Keister Aug 6 '13 at 13:30
  • $\begingroup$ The reals? The reals are closed right? $\endgroup$ – CodeKingPlusPlus Aug 6 '13 at 13:31
  • $\begingroup$ Does it need to be a strict subset? $\endgroup$ – Adrian Keister Aug 6 '13 at 13:32
  • 4
    $\begingroup$ You first conclusion is false. The Lipschitz constant of your Function is equal to $1$, not $<1$. What you need is $\exists \epsilon > 0:\ |f'(x)| \leq 1-\epsilon \ \forall x\in \mathbb{R}$ Which does not hold here, so $f$ is, in fact, no contraction. $\endgroup$ – AlexR Aug 6 '13 at 13:44
3
+25
$\begingroup$

Jonathan Y.'s answer is correct. I wanted to elaborate on his answer in a space longer than a comment, so I hope you'll pardon my bandwagoning.

It seems the OP's confusion lies with their understanding of the statement of the contraction mapping principle. Let's make sure we're on the same foot.

Let $(X,d)$ be a complete metric space. We say $f:X\to X$ is a contraction if there exists a constant $1>c>0$ so that $d(f(x),f(y))\le cd(x,y)$ for all $x,y\in X$.

Alternatively, provided the OP is comfortable with the notion of a supremum, we may say that $f:X\to X$ is a contraction if and only if

$\mathcal{L}_f:=\sup\left\{\frac{d(f(x),f(y))}{d(x,y)}: x,y\in X, x\ne y\right\}<1$.

It is a valuable exercise to you to verify that these two conditions are in fact equal. Now, this second formulation better illustrates the following point: the OP did not show that $f$ is a contraction. OP showed that $f$ is a weak contraction or, in other words, a short map.

Let's switch back to the example at hand. OP verified the following fact: for every pair $x,y$ there is a number $x<c_{xy}<y$, depending on $x,y$ so that

$|f(x)-f(y)|=|f'(c_{xy})|\cdot |x-y|=\left(1-\frac{1}{|1+c_{xy}^2|}\right)|x-y|$.

Consequently,

$\begin{align*}\mathcal{L}_f&=\sup\left\{\frac{{|f(x)-f(y)|}}{|{x-y}|}: x,y\in \mathbb{R}, x\ne y\right\}\\&= \sup\left\{1-\frac{1}{|1+c_{xy}^2|}:x,y\in \mathbb{R}, x<y\right\}\\ &\ge \sup\left\{1-\frac{1}{|1+c_{xy}^2|}:x,y\in \mathbb{R}, 0<x<y\right\}\qquad \text{As}\{x,y: 0<x<y\}\subseteq \{x,y: x<y\}\\&\ge \sup\left\{1-\frac{1}{|1+x^2|}:0<x\right\} \qquad \text{Since }0<x<c_{xy}\text{ and }1/(1+x^2)\text{ decreases on }\mathbb{R}^+.\\ &=1\end{align*}$

So $1\le \mathcal{L}_f$, and so $f$ is not a contraction.

$\endgroup$
  • $\begingroup$ I like this a lot and it follows nicely if those two conditions are equal. But how can I verify that the conditions are equal? At a glance this is not apparent to me. $\endgroup$ – CodeKingPlusPlus Aug 14 '13 at 16:46
  • $\begingroup$ Sure, no problem. Say that $f$ is a contraction, i.e. suppose there exists $0<c<1$ so that $d(f(x),f(y))<cd(x,y)$ for all $x,y\in X$ with $x\ne y$. Now, for all $x,y\in X$ with $x\ne y$, we have that $\frac{d(f(x),f(y))}{d(x,y)}<\frac{cd(x,y)}{d(x,y)}=c$. Taking the supremum over all nonequal pairs of $x,y\in X$, we see that $\mathcal{L}_f\le c<1$. This proves one direction. Suppose then that $\mathcal{L}_f<1$. If $x,y\in X$ and $x\ne y$, then by definition of $\mathcal{L}_f$ we have $d(f(x),f(y))<\mathcal{L}_fd(x,y).$ Thus, $f$ is a contraction (since we may take $c=\mathcal{L}_f$). $\endgroup$ – Adam Azzam Aug 14 '13 at 17:50
7
$\begingroup$

A contraction in a metric space is a mapping $f:X\to X$ such that there exists $0<c<1$ such that for all $x,y\in X$, $x\neq y$, it holds that $d(f(x),f(y))\leq cd(x,y)$. Indeed, the Banach fixed-point theorem shows that such mappings on complete metric spaces always have a unique fixed point.

However, if one relaxes the conditions to require only $d(f(x),f(y))<d(x,y)$ (for all $x\neq y$), the function in question no longer necessarily has a fixed point. Indeed, the example you provide demonstrates that principle well: note that where you show that $|f(x)-f(y)|=|f^\prime(x)(x-y)|$, based (I presume) on the mean-value theorem, in fact all that can be known is that there exists some $z\in(y,x)$ (or $(x,y)$, naturally) such that $f(x)-f(y)=f^\prime(z)(x-y)$. Hence, the fact that--for the provided function--$\lim_{z\to\infty}f^\prime(z)=1$ implies that no $c<1$ exists to be used in the conditions to the Banach fixed-point theorem.

It remains true, however, that such a mapping cannot have more than a single fixed point, as that part of the proof relies solely on the strict inequality. As an aside, if one accepts the assumption that $X$ is compact (hence, as @MattE reminds us, necessarily complete), then even such mappings still have a (unique) fixed-point, as the only possible minimum to the continuous function $F(x)=d(x,f(x))$.

$\endgroup$
  • $\begingroup$ What about the first part where I show that $f$ is contractive. Couldn't I just take any $x$ and use $f'(x)=c$? $\endgroup$ – CodeKingPlusPlus Aug 6 '13 at 13:32
  • $\begingroup$ @CodeKingPlusPlus In that case $c$ wouldn't be fixed; it would vary with $x$. $\endgroup$ – mdp Aug 6 '13 at 13:36
  • $\begingroup$ My definition of the CMT does not say either of those? Could you try explaining in terms of my definition? $\endgroup$ – CodeKingPlusPlus Aug 6 '13 at 13:38
  • $\begingroup$ Well, as you can see, without the assumption of a proper contraction (i.e., the existence of $c<1$), the theorem doesn't hold, except on compact domains (where it holds for a different reason). However, the condition you've specified is sufficient to insure that no more than a single fixed point exists. $\endgroup$ – Jonathan Y. Aug 6 '13 at 13:43
  • 1
    $\begingroup$ Dear Jonathan, A small remark, but a compact metric space is necessarily complete. Regards, $\endgroup$ – Matt E Aug 13 '13 at 21:01

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.