Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose $R$ is an ordered field. Call a continuous map $f: R \rightarrow R$ a contraction if there exists $r < 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?

For a related question, see Converse to Banach's fixed point theorem? .

Jacek Jachymski's article "A discrete fixed point theorem of Eilenberg as a particular case of the contraction principle" ( http://emis.impa.br/EMIS/journals/HOA/FPTA/2004/131.pdf ) 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.

share|improve this question
2  
Nice question. Just a comment: the standard proof works in an ordered field $R$ such that (i) Cauchy sequences converge and (ii) For all $0 < r < 1$, $r^n \rightarrow 0$. But the point is that these properties force $R$ to be complete Archimedean, i.e., $R \cong \mathbb{R}$. –  Pete L. Clark May 24 '11 at 18:16
add comment

1 Answer

up vote 12 down vote accepted

Yes, it is true that $R$ must be the field of real numbers.

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.

1) $\mathbb{Q}$ has no upper bound in $R$ (i.e., $R$ is Archimedean).

Proof: Call element $x$ of $R$ infinite if $\vert x\vert$ is an upper bound for $\mathbb{Q}$, and finite 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},&\textrm{if }x\textrm{ is finite},\\\\ x/2,&\textrm{if }x\textrm{ is infinite}. \end{cases} $$ So,

  • 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$.
  • If $x,y$ are both infinite then $\vert f(x)-f(y)\vert=\frac12\vert x-y\vert$.
  • 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$.

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.

2) Every Cauchy sequence $x_n$ in $R$ converges.

Proof: Passing to a subsequence1, 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 subsequence2, we can suppose that $x_{n+2}-x_{n+1}\le\frac12(x_{n+1}-x_n)$ and that $x_{n+1}-x_n < 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})$.

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 cover3 $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.


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 < 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$.

1 Any sequence in a linearly ordered set has a monotonic subsequence.

2 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 < \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$.

3 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 < z < 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 < r$ for large $n$, and $x_n\to z$.

share|improve this answer
    
Thanks! I follow most of this, but I don't get the part about "by further passing to a subsequence, we can suppose that $x_{n+2}−x_{n+1} \leq \frac12 (x_{n+1}−x_n)$" (from the third sentence of the first paragraph of the proof of (2)). I know how I'd extract such a subsequence if I were working in the real numbers, by using the existence (and the value) of $\lim x_n$. But I can't use my method here, and trying to do an approximate version leads me into a swamp. Is there an easy way to see why your assertion is true in any ordered ring? –  James Propp May 25 '11 at 14:38
    
That's true for any increasing Cauchy sequence in an ordered field. I'll add some clarifications when I log on later. –  George Lowther May 25 '11 at 16:46
    
Thanks, George! I'm marking this question as closed (though if anyone finds a different solution please post that as well). I'll take this opportunity to repeat my request from mathoverflow.net/questions/62340/… : Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of calculus are equivalent to the completeness axiom of the reals and which ones aren't? I'm writing something of my own on this subject and I feel that there must be authors I should acknowledge. –  James Propp May 26 '11 at 14:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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