# Prove expansive function on a compact set is surjective.

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!

• 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. – GEdgar Apr 2 '16 at 15:44
• @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? – Amir Naseri Apr 2 '16 at 16:01
• It seems I was wrong when I said this one is easier than proving isometry. – 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.

• So many thanks to you and "ifk" from "Art of problem solving" community! – Amir Naseri Apr 5 '16 at 15:09
• When given a mathematical puzzle (at the undergraduate level or below), "Art of Problem Solving" is often a good place to find a solution. – GEdgar Apr 5 '16 at 15:13
• @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$? – Emolga Jun 3 '16 at 15:31
• @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. – GEdgar Jun 3 '16 at 20:36
• @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}$? – 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}$.

• 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? – Amir Naseri Apr 2 '16 at 17:49
• @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? – Amir Naseri Apr 4 '16 at 8:39
• @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$? – Amir Naseri Apr 4 '16 at 11:00
• edited:) I underlined surjectivess just to say that the image of $g$ is the whole $X$ – Tommaso Seneci Apr 4 '16 at 12:40
• 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. – GEdgar Apr 4 '16 at 12:49