# Contraction mapping does not hold in metric space

Let $X=\mathbb{Q}\cap [1,2]$, i.e $X$ is the set of rational number between 1 and 2 inclusive. We can consider $X$ to be a metric space by endowing it with the usual distance function, i.e for $x,y \in X$ we put $d(x,y)=|x-y|$. Now we define $f:X\rightarrow X$ by $f(x)=x-\dfrac{x^2-2}{2x}$. Ones should check that if$x\in X$ , then $f(x)\in X$ as well. This means checking that if $x$ is rational and in $[1,2]$ then $f(x)$ is also rational and in $[1,2]$. Prove that $f$ is a contraction mapping but $f$ does not has a fixed point. This is my homework exercise, but I am not good at mathematics, so please feel freely helping me. Thank you very much !

• You have three things to prove: (a) $f$ is a function from $x$ to $X$. (b) $f$ is a contraction. (c) $f$ has no fixed point. Can you prove any of these statements? What have you tried? – Chris Eagle Oct 29 '11 at 14:56
• By definition of contraction mapping, you need to show that there exists $0 \leq k < 1$ such that, for all $x, y \in X$... (among other things) – The Chaz 2.0 Oct 29 '11 at 14:57
• Yes, I can prove that $f$ is a contraction.Infact, I can prove that $|f(x)-f(y)|\le \dfrac{3}{2}|x-y|$. But what about the proof for fixed point ? is it too obvious that we have to solve the equation $f(x)=x$? – Arsenaler Oct 29 '11 at 15:02
• @msnaber: look again at the definition of a contraction: what you have proven is not enough. Yes, a fixed point of $f$ is exactly a solution (in $X$) of $f(x)=x$. – Chris Eagle Oct 29 '11 at 15:07
• Ah, I remember false, $\frac{3}{2}\ge 1$. but that's why I need you help in solving this problem. I may be need a more precise solution. sorry because I am not good at mathematic. – Arsenaler Oct 29 '11 at 15:13

Ok, first you can transform $f(x)$ into $f(x) = \frac{x^2+2}{2x}$ (by taking $x$ to the fraction and subtracting from $2x^2$ the value $x^2-2$). Then you can notice, that in the numerator and the denominator there are rational numbers, since you multiply and add rational numbers. So the whole fraction is rational.

Now: is it in $[1,2]$? Assuming that $x \gt 0$ we have:
$\frac{x^2+2}{2x} \ge 1$ iff $x^2+2 \ge 2x$ iff $x^2 - 2x + 2 \ge 0$ iff $(x - 1)^2 + 1 \ge 0$ which is true for any $x$.
Is it smaller than 2?
$\frac{x^2+2}{2x} \le 2$ iff $x^2 + 2 \le 4x$
Hint for that: analyse the maximum and minimum values of appropriate sides of the inequality.

Now you want to show that it is a contraction. It means that you want it to be Lipschitz, and the Lipschitz constant should be smaller than one. In these situations the easiest way is to use the Lagrange theorem. The derivative is a simple monotonous function (wolfram says: $1/2 - \frac{1}{x^2}$), so you can easily notice that its supremum (actually supremum of its modulus) is smaller than 1.

And finally a less calculus-like part of the task: Why is there no constant point?

If you look at f as a function from $[1,2]$ (without intersecting with rational numbers), then all the above calculations are still true. Let it be called $F$. $[1,2]$ is a complete metric space, so a contraction must have a constant point and it is unique. You can easily calculate that $F(x)=x$ holds for $x=\heartsuit$, so the only constant point of $F$ is $\heartsuit$. Since $\heartsuit$ is not a rational number we know that $f$ has no constant points.

• Well, actually the last part is also calculus-like, there is no need to use topology and complete spaces here =) – savick01 Oct 29 '11 at 15:34
• thank you very much savicko! – Arsenaler Oct 29 '11 at 15:41
• Pedantic nitpick: In your second paragraph, you're not assuming that $x\neq 0$, but rather that $x > 0$. This guarantees the inequalites don't reverse direction when you multiply by $2x$. +1 anyway for the $\heartsuit$! – Jason DeVito Nov 28 '11 at 19:28
• This is a very nice answer. Just an idle question: is there some reason you write "Lagrange's Theorem" instead of "The Mean Value Theorem"? First, as an American mathematician it was news to me that this theorem was traditionally associated with Lagrange. (See the footnote jstor.org/pss/2324274 for some historical information.) Second, if this is a theorem of Lagrange, it is one of hundreds of such things. When you don't have hyperlinks available, doesn't this make it a little difficult for the reader to determine which Lagrange Theorem you mean? – Pete L. Clark Feb 8 '12 at 14:28
• @PeteL.Clark: Thanks. There is no special reason. Maybe at first I didn't remember the English name and preferred to use the surname. At my university this theorem is always associated with Lagrange. Or maybe I assumed that when speaking about basic analysis it is clear which theorem is intended. Good to know that the MVT isn't commonly associated with Lagrange, I'll try to remember about it in the future. Anyway, even if one is offline, the destination address of a hyperlink is available after mouseover and the address here contains the name, so I hope not to have troubled anyone too much. – savick01 Feb 13 '12 at 18:25

Somewhere between a comment and an answer: the map $f$ is nothing else than the "amelioration function" $T(x) = x - \frac{f(x)}{f'(x)}$ one studies when applying Newton's method to search for roots of a differentiable function $f$: here the function is $f(x) = x^2-2$.

Aside from providing general orientation, this observation is directly helpful in at least one part of the problem: a glance at the above formula for $T$ shows that a real number $c$ is a fixed point for $T$ iff it is a root of $f$: $T(c) = c \iff f(c) = 0$. Thus the fixed points of $T$ on all of $\mathbb{R}$ are $\pm \sqrt{2}$. Since these are not rational numbers, we see that the given function (which I am calling $T$) has no fixed points on $\mathbb{Q} \cap [1,2]$.

I recently covered Newton's method in my "Spivak calculus" course: some notes on it are available here. One point that I found interesting was that in the analysis of the convergence of Newton's method one uses contraction mappings but not the Contraction Mapping Principle. This comes down to the point made above: in general, $T$ has a fixed point iff $f$ has a root. Now of course just starting with a differentiable function $f$ it need not have any roots (e.g. if $f(x) = e^x$, $T(x) = x-1$). But one can show that if $f$ has a simple root $c$, then there is an interval $[c-\delta,c+\delta]$ which is $T$-invariant and on which $T$ is a contraction mapping. Then the rate of convergence to the known fixed point comes in handy, and for this we do not need completeness!

• If you assume just differentiability of $f$ and $f'(c)\neq 0$, there might be $f'(c+\varepsilon)=0$ for arbitrarily small $|\varepsilon |$, so $T$ is not well defined unless I am mistaken. In your notes you have some additional assumptions about $f$. I think we need $f'$ to be away from $0$ to prevent Newton's method from going away and to be bounded in order not to lose the contracting property. But it seems not enough to get the contracting property. What do you propose? $f \in C^2$ like in your notes? – savick01 Feb 13 '12 at 19:48
• @savick01: yes, I am not just assuming differentiability of $f$: as you say, in order to prove the convergence to the root I assume that $f$ is $C^2$, although for the point in question it would be enough for $f$ to be $C^1$. (It seems likely that $C^2$ is stronger than one really needs to assume, but $C^1$ is probably really needed.) – Pete L. Clark Feb 13 '12 at 22:55