Converse to Banach’s fixed point theorem for ordered fields? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T20:28:21Z http://mathoverflow.net/feeds/question/65874 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65874/converse-to-banachs-fixed-point-theorem-for-ordered-fields Converse to Banach’s fixed point theorem for ordered fields? James Propp 2011-05-24T17:04:55Z 2011-05-25T21:18:38Z <p>Suppose $R$ is an ordered field. Call a continuous map $f: R \rightarrow R$ a contraction if there exists $r &lt; 1$ (in $R$) such that $|f(x)-f(y)| \leq r |x-y|$ for all $x,y \in R$ (where $|x| := \max(x,-x)$). Suppose that every contraction from $R$ to $R$ has a unique fixed point. Must $R$ be the field of real numbers?</p> <p>For a related question, see <a href="http://mathoverflow.net/questions/26119/converse-to-banachs-fixed-point-theorem" rel="nofollow">http://mathoverflow.net/questions/26119/converse-to-banachs-fixed-point-theorem</a> .</p> <p>Jacek Jachymski's article "A discrete fixed point theorem of Eilenberg as a particular case of the contraction principle" ( <a href="http://emis.impa.br/EMIS/journals/HOA/FPTA/2004/131.pdf" rel="nofollow">http://emis.impa.br/EMIS/journals/HOA/FPTA/2004/131.pdf</a> ) and the references it contains may be relevant. However, the non-Archimedean metric spaces that the article considers are bounded, which non-Archimedean ordered fields certainly are not. Also, my question is not about metric spaces, since my notion of distance lives in $R$ itself, not the real numbers.</p> http://mathoverflow.net/questions/65874/converse-to-banachs-fixed-point-theorem-for-ordered-fields/65915#65915 Answer by George Lowther for Converse to Banach’s fixed point theorem for ordered fields? George Lowther 2011-05-24T23:40:06Z 2011-05-25T21:18:38Z <p>Yes, it is true that $R$ must be the field of real numbers.</p> <p>As $R$ is an ordered field, it is naturally an extension $\mathbb{Q}\hookrightarrow R$. We can prove the following two properties, which characterize the reals among the ordered fields.</p> <blockquote> <p>1) $\mathbb{Q}$ has no upper bound in $R$ (i.e., $R$ is Archimedean).</p> </blockquote> <p><i>Proof:</i> Call element $x$ of $R$ <i>infinite</i> if $\vert x\vert$ is an upper bound for $\mathbb{Q}$, and <i>finite</i> otherwise. Then we can define $f\colon R\to R$ by $$f(x)=\begin{cases} \frac{x}{2}+\frac12\max(x,0)+(2+\max(x,0))^{-1},&amp;\textrm{if }x\textrm{ is finite},\\ x/2,&amp;\textrm{if }x\textrm{ is infinite}. \end{cases}$$ So,</p> <ul> <li>If $x,y$ are finite then they have an upper bound $a\ge0$ in $\mathbb{Q}$, and it can be seen that $\vert f(x)-f(y)\vert\le(1-(2+a)^{-2})\vert x-y\vert$.</li> <li>If $x,y$ are both infinite then $\vert f(x)-f(y)\vert=\frac12\vert x-y\vert$. </li> <li>If $x$ is infinite and $y$ is finite then $\vert f(x)-f(y)\vert\le \frac12\vert x\vert+\vert f(y)\vert\le\frac34\vert x-y\vert$.</li> </ul> <p>In any case, if $\mathbb{Q}$ had an upper bound $\kappa\in R$ then we have $\vert f(x)-f(y)\vert\le (1-\kappa^{-1})\vert x-y\vert$ so that, by hypothesis, $f$ has a fixed point. But it can be seen that $f(x) > x$ for finite $x$ and $f(x)=\frac x2\not=x$ for infinite $x$. So, it doesn't have a fixed point, giving a contradiction.</p> <blockquote> <p>2) Every Cauchy sequence $x_n$ in $R$ converges.</p> </blockquote> <p><i>Proof:</i> Passing to a subsequence<sup>1</sup>, it can be assumed that $x_n$ is monotonic, and replacing $x_n$ by $-x_n$ if necessary, we can suppose that it is increasing. If it is eventually constant then the result is immediate. Otherwise, by further passing to a subsequence<sup>2</sup>, we can suppose that $x_{n+2}-x_{n+1}\le\frac12(x_{n+1}-x_n)$ and that $x_{n+1}-x_n &lt; 2^{-n-1}$. Then, $y_n=x_n+2^{-n}$ is a strictly decreasing sequence with $0\le y_n-x_n\le 2^{-n}$. Again, passing to a subsequence, it can be assumed that $y_{n+1}-y_{n+2}\le\frac12(y_n-y_{n+1})$.</p> <p>We can define $f\colon R\to R$ linearly mapping $(-\infty,x_1]$ onto $(-\infty,x_2]$, $(x_n,x_{n+1}]$ onto $(x_{n+1},x_{n+2}]$, $[y_1,\infty)$ onto $[y_2,\infty)$, and $[y_{n+1},y_n)$ onto $[y_{n+2},y_{n+1})$ ($n\ge1$). This can be done such that $\vert f(x)-f(y)\vert\le\frac12\vert x-y\vert$ on each interval, in which case it does not have any fixed points in these intervals. Furthermore, if $x_n$ had no limit point, then the intervals cover<sup>3</sup> $R$ and this defines $f$ everywhere. But, then, $\vert f(x)-f(y)\vert\le\frac12\vert x-y\vert$ for all $x,y\in R$ implying that $f$ has a fixed point, giving a contradiction.</p> <hr> <p>I'll add a few more details that I passed over rather quickly above. A sequence $x_n$ is Cauchy if, for each $r > 0$ in $R$ then $\vert x_n - x_m\vert &lt; r$ for large enough $m,n$. Any subsequence of a Cauchy sequence is itself Cauchy and tends to a limit $x$ if and only if the orginal sequence tends to $x$.</p> <p><sup>1</sup> Any sequence in a linearly ordered set has a monotonic subsequence.</p> <p><sup>2</sup> If $x_n$ is an increasing Cauchy sequence, which is not eventually constant, then it is possible to choose a subsequence $x_{n_k}$ as follows. Once $x_{n_k}$ has been chosen, then there is an $m > n_k$ such that $x_m \not= x_{n_k}$. As it is Cauchy, $n_{k+1}\ge m$ can be chosen such that $\vert x_r-x_s\vert &lt; \min(2^{-k-2},(x_m-x_{n_k})/2)$ for all $r,s\ge n_{k+1}$. This ensures that $x_{n_{k+2}}-x_{n_{k+1}}$ is less than both $2^{-k-2}$ and $(x_{n_{k+1}}-x_{n_k})/2$ for all $k$.</p> <p><sup>3</sup> If $z\in R$ was not in any of the intervals $(-\infty,x_1]$, $(x_n,x_{n+1}]$, $[y_1,\infty)$, $[y_{n+1},y_n)$ then $x_n &lt; z &lt; y_n$ for all $n$. So, $\vert z-x_n\vert\le y_n-x_n\le 2^{-n}$. Given any $r > 0$ in $R$, the fact that we have already shown $R$ to be Archimedean in (1) implies that $2^n > r^{-1}$ for large $n$. So, $\vert z - x_n\vert &lt; r$ for large $n$, and $x_n\to z$.</p>