Let $M$ be a compact set and $(M,d)$ be a metric space, define function $f:M\to M$ such that for all $\,p,q\in M$ $$d(f(p),f(q))\ge d(p,q)$$ Prove $f$ is surjective.

I observed that compactness of $M$ is crucial, supposing $M$ being only closed or bounded would have counterexamples of $f$.

Also I found another problem which might be related somehow, I couldn't help this but guessing we have to prove $f$ is isometric.

@TommasoSeneci Thank you very much for the efforts, but as we see problem is not completely solved, so any clarification of showing $Y$(discussed in the below answer) is closed or other ways maybe, would be so appreciated!

  • $\begingroup$ No, this one is much easier than proving $f$ is an isometry. What make it a little tricky is: we do not assume $f$ is continuous. $\endgroup$ – GEdgar Apr 2 '16 at 15:44
  • $\begingroup$ @GEdgar I was just able to realize $f^{-1}$ is continuous when its domain is $f(M)$, have you found a solution? If so, would you please explain more? $\endgroup$ – Amir Naseri Apr 2 '16 at 16:01
  • 1
    $\begingroup$ It seems I was wrong when I said this one is easier than proving isometry. $\endgroup$ – GEdgar Apr 5 '16 at 14:49

Solution by "ifk" at http://www.artofproblemsolving.com/community/c7h360582p1972843 . There, $(X,d)$ is the metric space, and we are to prove $f$ is both surjective and isometric.

Let $x\in X$. Define $x_{0} = x, \ x_{n+1} = f(x_{n})$. By compactness $\{x_{n}\}_{n}$ has convergent (in particular Cauchy) subsequence $\{x_{n_{k}}\}_{k}$. W.l.o.g. $\{n_{k+1} - n_{k}\}_{k}$ is increasing.

We will show that the sequence $\{x_{n_{k+1} - n_{k}}\}_{k}$ converges to $x$. Let $\varepsilon > 0$. Since $\{x_{n_{k}}\}_{k}$ is Cauchy sequence, then for sufficiently large $k$ we've got $d(x_{n_{k}}, x_{n_{k+1}}) < \varepsilon$. Now $d(x_{n_{k}}, x_{n_{k+1}}) \ge d(x_{n_{k+1} - n_{k}}, x)$.

Since $\{x_{n}\}_{n\ge 1} \subset f(X)$ it follows that $f(X)$ is dense in $X$.

Now suppose that $d(f(x), f(y)) > d(x,y)$ for some $x,y\in X$. Define $\{x_{n}\}_{n}$ as before and similarly $y_{0} = y, \ y_{n+1} = f(y_{n})$ By the preceding argument there exist sequence $\{n_{j}\}_{j}\subset \mathbb{N}$ s.t. $x_{n_{j}}\to x, \ y_{n_{j}}\to y$ as $j\to \infty$. Then $$ d(f(x), f(y)) = d(x_{1},y_{1}) \le d(x_{n_{j}},y_{n_{j}})\to d(x,y) $$ so $d(x,y) < d(f(x),f(y) \le d(x,y)$, contradiction.

Therefore $f$ is isometry, in particular continuous mapping. Hence $f(X)$ is compact, in particular complete, in particular $f(X) = \text{cl}(f(X)) = X$. Q.E.D.

  • $\begingroup$ So many thanks to you and "ifk" from "Art of problem solving" community! $\endgroup$ – Amir Naseri Apr 5 '16 at 15:09
  • 1
    $\begingroup$ When given a mathematical puzzle (at the undergraduate level or below), "Art of Problem Solving" is often a good place to find a solution. $\endgroup$ – GEdgar Apr 5 '16 at 15:13
  • $\begingroup$ @GEdgar We know that we can find a sequence $x_{n_j} \to x$ and a sequence $y_{m_j} \to y$, but why can we find a single sequence that works for both $x$ and $y$? $\endgroup$ – Emolga Jun 3 '16 at 15:31
  • 1
    $\begingroup$ @Leullame ... we have $x_n$ and $y_n$. We take a subsequence (a subset of the indices $n$) so that one converges. Then a further subsequence (a subset of the first subset of indices) so that the other converges. $\endgroup$ – GEdgar Jun 3 '16 at 20:36
  • $\begingroup$ @GEdgar Let's say $x_{n_k} $ converges to $x$. Then we have a sequence $y_{n_{k_{j+1}}-n_{k_j}}$ converging to $y$, but it seems $x_{n_{k_{j+1}}-n_{k_j}}$ does not converge to $x$, since it is not a subsequence of $x_{n_k}$. So how do we keep a sub-sequence of $x_{n_k}$ while doing the trick of $n_{k_{j+1}}-n_{k_j}$? $\endgroup$ – Emolga Jun 6 '16 at 18:45

Firstly we see that $f$ is injective since $x \neq y \Rightarrow d(f(x),f(y)) \geq d(x,y) > 0$ so $f(x) \neq f(y)$. Moreover the inverse, namely $g := f^{-1}$, is continuous on its domain, denoted by $Y := f(X)$, because $x,y \in Y \Rightarrow d(g(x),g(y)) \leq d(x,y)$ the function $g$ is non-expansive. So we have a continuos map $g : Y \rightarrow X$ and we assume not surjectiveness for $f$, i.e. $\exists x_0\in X\setminus Y$. $Y=f(X)=g^{-1}(X)\subset X$ is closed because it is the preimage through the continuous function $g$ of the compact set $X$, and compact set are closed in Hausdorff topologies such as metric induced ones. So since it cannot exists any sequence converging to $x_0$ we conclude $\exists \varepsilon >0 \; B_{\varepsilon}(x_0)\subset X\setminus Y$. Thus $\min_{Y} d(x_0,y)=d(x_0,\tilde{y}) > \varepsilon$. We are done because consider the sequence $\{ f^n(x_0) \}_n \subset Y$ by compactness $\exists f^{n_k}(x_0)\rightarrow \tilde{x}$ and then it is Cauchy, so for $\delta = \frac{\varepsilon}{2} \; \exists \, n_k \; d(f^{n_k}(x_0),f^{n_{k+1}}(x_0))<\delta$ which implies $ d(x_0,f^{n_k}(x_0)) \leq d(f^{n_{k}}(x_0),f^{n_{k+1}}(x_0)) < \delta = \frac{\varepsilon}{2}$.

  • $\begingroup$ Great, thank you! I understood the whole solution except as @GEdgar mentioned, how can we conclude from surjectiveness and continuity of $g$ that $Y$ is closed? $\endgroup$ – Amir Naseri Apr 2 '16 at 17:49
  • 1
    $\begingroup$ @Tommaso Seneci I have faced a wrong conclusion, $Y=f(X)$ is closed as a subset of $Y$, but not $X$ generally, so we can not say it's compact, am I right? $\endgroup$ – Amir Naseri Apr 4 '16 at 8:39
  • 1
    $\begingroup$ @GEdgar Excuse me sir, if you see this comment and the one I wrote above, would you please clarify how could we be sure $Y$ is closed and compact in $X$? $\endgroup$ – Amir Naseri Apr 4 '16 at 11:00
  • $\begingroup$ edited:) I underlined surjectivess just to say that the image of $g$ is the whole $X$ $\endgroup$ – Tommaso Seneci Apr 4 '16 at 12:40
  • $\begingroup$ I now do not understand. Note: this is not true... if $X$ compact metric, $Y \subseteq Y$, $g : Y \to X$ continuous and surjective, then $Y$ is closed in $X$. So we need to use more than that to show $Y$ is closed in $X$ in this case. $\endgroup$ – GEdgar Apr 4 '16 at 12:49

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.