2
$\begingroup$

Here is Prob. 7, Sec. 28, in the book Topology by James R. Munkres, 2nd edition:

Let $(X, d)$ be a metric space. If $f$ satisfies the condition $$ d\big( f(x), f(y) \big) < d(x, y) $$ for all $x, y \in X$ with $x \neq y$, then $f$ is called a shrinking map. If there is a number $\alpha < 1$ such that $$ d \big( f(x), f(y) \big) \leq \alpha d(x, y) $$ for all $x, y \in X$, then $f$ is called a contraction. A fixed point of $f$ is a point $x$ such that $f(x) = x$.

(a) If $f$ is a contraction and $X$ is compact, show $f$ has a unique fixed point. [Hint: Define $f^1 = f$ and $f^{n+1} = f \circ f^n$. Consider the intersection $A$ of the sets $A_n = f^n(X)$.]

(b) Show more generally that if $f$ is a shrinking map and $X$ is compact, then $f$ has a unique fixed point. [Hint: Let $A$ be as before. Given $x \in A$, choose $x_n$ so that $x = f^{n+1}\left(x_n\right)$. If $a$ is the limit of some subsequence of the sequence $y_n = f^n \left( x_n \right)$, show that $a \in A$ and $f(a) = x$. Conclude that $A = f(A)$, so that $\mathrm{diam}\, A = 0$.]

(c) Let $X = [0, 1]$. Show that $f(x) = x - x^2/2$ maps $X$ into $X$ and is a shrinking map that is not a contraction. [Hint: Use the mean-value theorem of calculus.]

(d) The result in (a) holds if $X$ is a complete metric space, such as $\mathbb{R}$; see the exercises of \Sec. 43. The result in (b) does not: Show that the map $f \colon \mathbb{R} \to \mathbb{R}$ given by $f(x) = \left[ x + \left( x^2 + 1 \right)^{1/2} \right]/2$ is a shrinking map that is not a contraction and has no fixed point.

Here is my MSE post on Prob. 7 (a).

Here I'll only be attempting a solution to Prob. 7 (b).

My Attempt

Prob. 7 (b):

Here is another Math SE post on this very problem. However, here I'll attempt a proof using the hint offered by Munkres.

We first show that the shrinking map $f$ is uniformly continuous on $X$. Given a real number $\varepsilon > 0$, let us choose a real number $\delta$ so that $0 < \delta \leq \varepsilon$. Then for all $x, y \in X$ for which $d(x, y) < \delta$, we would obtain $$ d \big( f(x), f(y) \big) \leq d( x, y) < \delta \leq \varepsilon.$$ Since $\varepsilon > 0$ was arbitrary, it follows that $f$ is uniformly continuous on $X$.

Let $i_X \colon X \to X$ denote the identity map on $X$, defined by $$ i_X (x) \colon= x \ \mbox{ for all } \ x \in X. \tag{Def. 0} $$ Now let us put $$ f^n \colon= \begin{cases} i_X \ & \mbox{ if } n = 0, \\ f \circ f^{n-1} \ & \mbox{ if } n = 1, 2, 3, \ldots. \end{cases} \tag{Def. 1} $$ Next, let us put $$ A_n \colon= \begin{cases} X \ & \mbox{ if } n = 0, \\ f^n(X) \ & \mbox{ if } n = 1, 2, 3, \ldots. \end{cases} \tag{Def. 2} $$ Then we find that, for each natural number $n$, $$ A_n = f \left( A_{n-1} \right). \tag{0} $$

Now as the maps $i_X$ and $f$ are both continuous mappings of the compact space $X$ into itself, so are all the maps $f^n$ in (Def. 1) above, and thus all the sets $A_n$ in (Def. 2) above are all compact subspaces of $X$; moreover since $X$, being a metric space, is a Hausdorff space and since each set $A_n$ is a compact subspace of $X$, each set $A_n$ is also closed in $X$. And, as each set $A_n$ is closed in $X$, so is the intersection of these sets. Let us put $$ A \colon= \bigcap_{n=0}^\infty A_n. \tag{Def. 3}$$ Then as $A$ is a closed set in the compact space $X$, so $A$ is also compact (as a subspace of $X$).

As $f$ is a mapping of set $X$ into itself, so we have $f(X) \subset X$, that is, $$A_1 \subset A_0.$$ Now suppose that, for some natural number $k$, we have $$ A_k \subset A_{k-1}. $$ Then using (0) above we find that $$ A_{k+1} = f \left( A_k \right) \subset f \left( A_{k-1} \right) = A_k.$$ Therefore by induction we can conclude that $$ A_n \subset A_{n-1} \ \mbox{ for } n = 1, 2, 3, \ldots. \tag{1} $$

Thus $\left\{ \ A_n \ \colon \ n = 0, 1, 2, \ldots \ \right\}$ is a nested sequence of non-empty closed sets in the compact space $X$; therefore their intersection is non-empty, that is, set $A$ in (Def. 3) above is non-empty.

We now show that $\mathrm{diam}\, X$ is finite. Let $p$ be any point of $X$. Then the collection $$ \left\{ \ B_d \left(p, N \right) \ \colon \ N \in \mathbb{N} \ \right\},$$ where $$ B_d \left( p; N \right) \colon= \{ \ x \in X \ \colon \ d(x, p) < N \ \},$$ forms an open covering of the compact space $X$; so some finite sub-collection of this collection also covers $X$; that is, there exist finitely many natural numbers $N_1, \ldots, N_n$ such that the collection $$ \left\{ \ B_d \left(p, N_1 \right), \ldots, B_d \left(p, N_n \right) \ \right\}$$ of open balls covers $X$. Let $$ M \colon= \max\left\{ \ N_1, \ldots, N_n \ \right\}. $$ Then we obtain $$ X = B_d (p, M).$$ Thus for any points $x, y \in X$, we have $$ d(x, y) \leq d(x, p) + d(p, y) < M + M = 2M.$$ So $$ \mathrm{diam}\, X \leq 2M < +\infty. $$ Thus we have shown that $$ \mathrm{diam}\, X < +\infty. \tag{2} $$ Hence from (Def. 3) above and from (1) we can also conclude that $$ \mathrm{diam}\, A \leq \mathrm{diam}\, A_n \leq \mathrm{diam}\, A_{n-1} < +\infty \ \mbox{ for } n = 1, 2, 3, \ldots. \tag{3} $$

Now suppose $x \in A$. Then $x$ is in each set $A_n = f^n(X)$, and so there exists a point $x_n \in X$ such that $x = f^{n+1}\left(x_n\right)$ for each $n = 1, 2, 3, \ldots$; let us put $$ y_n \colon= f^n\left(x_n\right) \ \mbox{ for each } n = 1, 2, 3, \ldots. \tag{Def. 4} $$ Then $\left( y_n \right)_{n \in \mathbb{N}}$ being a sequence in the compact metric space $(X, d)$ has a convergent subsequence, by virtue of Theorem 28.2 in Munkres; let $\left( y_{\varphi(n)} \right)_{n \in \mathbb{N}}$ be this subsequence for some strictly increasing function $\varphi \colon \mathbb{N} \to \mathbb{N}$, and let $a$ be the limit of this sequence.

What next? How to proceed from here?

PS:

Thus, for each $n \in \mathbb{N}$, we have $$ y_n = f^n \left( x_n \right)$$ and also $$ x = f^{n+1} \left( x_n \right) = f \left( f^n \left( x_n \right) \right) = f\left( y_n \right). $$ and so $$ f \left( y_n \right) = x. $$ Therefore we can conclude that, for each $n \in \mathbb{N}$, we have $$ f \left( y_{\varphi(n)} \right) = x, $$ and therefore we obtain $$ \lim_{n \to \infty} f \left( y_{\varphi(n)} \right) = x. \tag{4*} $$ But as $f$ is continuous and as $$ \lim_{n \to \infty} y_{\varphi(n)} = a, $$ so we must also have $$ \lim_{n \to \infty} f \left( y_{\varphi(n)} \right) = f(a). \tag{4**} $$ But the limit of a sequence in any metric space is unique. Therefore from (4*) and (4**) we obtain $$ f(a) = x, \tag{4} $$ and as $x \in A$ and $a \in X$, so from (4) we obtain $x \in f(A)$, which implies that $$ A \subset f(A). \tag{5*} $$

On the other hand, if $p \in f(A)$, then we have $p = f(q)$ for some point $q \in A$. But as $$ A = \cap_{n = 0}^\infty A_n, $$ and as $q \in A$, so $q \in A_n$ and hence $p = f(q) \in f \left( A_n \right) = A_{n+1}$ for each $n = 0, 1, 2, 3, \ldots$. That is, $p \in A_n$ for each $n = 1, 2, 3, \ldots$. But $p \in X = A_0$ of course. Therefore we can conclude that $p \in \cap_{n=0}^\infty A_n = A$, from which it follows that $$ f(A) \subset A. \tag{5**} $$ From (5*) and (5**) we obtain $$ f(A) = A. \tag{5} $$

We note that $$ \mathrm{diam}\, A = \sup \big\{ \, d(x, y) \, \colon \, x, y\in A \, \big\}. \tag{Def. 4} $$ Moreover from (3) we obtain $$ 0 \leq \mathrm{diam}\, A < +\infty. $$

Now suppose that $\mathrm{diam}\, A > 0$. Then in view of (Def. 4) we can conclude that, for any real number $\varepsilon > 0$, we can find points $x_\varepsilon, y_\varepsilon \in A$ such that $$ \mathrm{diam}\, A \geq d \left( x_\varepsilon, y_\varepsilon \right) > \mathrm{diam}\, A - \varepsilon. $$ So for each $n \in \mathbb{N}$, we can find points $a_n, b_n \in A$ such that $$ \mathrm{diam}\, A \geq d \left( a_n, b_n \right) > \mathrm{diam}\, A - \frac1n. \tag{6} $$ Thus we obtain sequences $\left( a_n \right)_{n \in \mathbb{N}}$ and $\left( b_n \right)_{n \in \mathbb{N}}$ in set $A$.

Now as $A$ is compact and as $\left( a_n \right)_{n \in \mathbb{N}}$ is a sequence in $A$, so there exists a subsequence $\left( a_{\phi(n)} \right)_{n \in \mathbb{N}}$ of this sequence, where $\phi \colon \mathbb{N} \to \mathbb{N}$ is a strictly increasing function, such that $\left( a_{\phi(n)} \right)_{n \in \mathbb{N}}$ converges to some point $a$ in $A$.

And, as $\left( b_{\phi(n)} \right)_{n \in \mathbb{N}}$ is a sequence in $A$ and as $A$ is compact, so there exists a subsequence $\left( b_{\psi(n)} \right)_{n \in \mathbb{N}}$ of this sequence that converges to some point $b$ in $A$. Here $\psi \colon \mathbb{N} \to \mathbb{N}$ is a strictly increasing function such that $$ \mathrm{range}\, \psi \subset \mathrm{range}\, \phi. $$ Then $\left( a_{\psi(n)} \right)_{n \in \mathbb{N} }$ is a subsequence of $\left( a_{\phi(n)} \right)_{n \in \mathbb{N} }$, and as the latter converges to point $a \in A$, so the former also converges to $a$.

Now as $$ \lim_{n \to \infty} a_{\psi(n)} = a \ \mbox{ and } \ \lim_{n \to \infty} b_{\psi(n)} = b, $$ so we can conclude that $$ \lim_{n \to \infty} d \left( a_{\psi(n)}, b_{\psi(n)} \right) = d(a, b). $$ But from (6) we obtain $$ \mathrm{diam}\, A \geq d \left( a_{\psi(n)}, b_{\psi(n)} \right) > \mathrm{diam}\, A - \frac{1}{\psi(n)} \geq \mathrm{diam}\, A - \frac{1}{n}, $$ and upon taking the limit as $n \to \infty$ we obtain $$ \mathrm{diam}\, A \geq d(a, b) \geq \mathrm{diam}\, A, $$ and so $$ d(a, b) = \mathrm{diam}\, A > 0 \tag{7} $$

Another way to show that (7) holds is as follows:

Suppose $\mathrm{diam} \, A > 0$.

As $A$ is compact, so too is the Cartesian product $A \times A$, by Theorem 26.7 in Munkres.

As the metric function $d \colon X \to X \to \mathbb{R}$ is a continuous map, so too is the restriction $d|_{A\times A}$, and as $A \times A$ is compact, so the map $d|_{A\times A}$ has a largest element, namely $\mathrm{diam}\, A$ of course. That is, there exist points $a, b \in A$ such that $$ d(a, b) = \mathrm{\diam}\, A > 0. \tag{7} $$ Therefore $$ a \neq b. \tag{8} . $$

However, as $A = f(A)$ by (5) above and as $a, b \in A$, so we can conclude that $a, b \in f(A)$ also, which implies that $$ a = f\left( a^* \right) \ \mbox{ and } \ b = f\left( b^* \right) $$ for some points $a^*, b^* \in A$, and as $a \neq b$ by (8) above, so we also have $a^* \neq b^*$, and since $f$ is a shrinking map, this together with (7) above implies that $$ \mathrm{diam}\, A = d(a, b) = d \big( f \left( a^* \right), f \left( b^* \right) \big) < d \left( a^*, b^* \right). $$ But on the other hand, as $a^*, b^* \in A$, so we must have $$ d \left( a^*, b^* \right) \leq \mathrm{diam}\, A. $$ Thus we have a contradiction. Therefore our supposition that $\mathrm{diam}\, A > 0$ is wrong. Hence $$ \mathrm{diam}\, A = 0. \tag{9} $$ Thus $A$ has only one point in it; let $p$ be that point. Then as $p \in A$, so $f(p) \in f(A)$. But by (5) we have $f(A) = A$. So we must have $f(p) \in A$ also, and since $A$ has only one element $p$, therefore we can conclude that $$ f(p) = p. $$ Thus $f$ has a fixed point $p \in A \subset X$.

Finally if $p$ and $q$ were any two distinct fixed points of the shrinking map $f$, then we would obtain $$ d(p, q) = d \big( f(p), f(q) \big) < d(p, q), $$ a contradiction. Hence $f$ has a unique fixed point in $X$.

Is my proof correct now? Is it complete and clear in all respects? Or, are there any gaps in it of logic or clarity?

$\endgroup$
3
  • $\begingroup$ Isn't a shrinking map also a contraction? $\endgroup$ – Aniruddha Deshmukh Mar 8 '19 at 3:56
  • 3
    $\begingroup$ @AniruddhaDeshmukh No, not necessarily. $\endgroup$ – Henno Brandsma Mar 8 '19 at 6:46
  • $\begingroup$ @HennoBrandsma can you please take time reviewing my post once again? I've completed the proof in a PS, based on the answer by Paul Frost. Hope you'd like my proof. $\endgroup$ – Saaqib Mahmood Apr 1 '20 at 15:08
1
$\begingroup$

We have $y_{\varphi(n)} \in A_{\varphi(n)} \subset A_{\varphi(m)}$ for $n \ge m$. Hence $a = \lim y_{\varphi(n)} \in A_{\varphi(m)}$ because $A_{\varphi(m)}$ is closed. This implies that $a \in \bigcap_m A_{\varphi(m)} = A$. Since $f$ is continuous and $y_{\varphi(n)} \to a$, we get $f(y_{\varphi(n)}) \to f(a)$. But the sequence $f(y_{\varphi(n)}) = f^{\varphi(n)+1}(x_{\varphi(n)}) = x$ is constant and we conclude $f(a) = x$.

This shows $A \subset f(A)$.

Assume that $d = \text{diam} A > 0$. Then we find sequences $(x_n), (y_n)$ in $A$ such that $d(x_n,y_n) \to d$. Since $A$ is compact, we may w.l.o.g. assume that both sequence converge to points $x, y \in A$. We get $d(x,y) = d$. Choose $a, b \in A$ such that $f(a) = x, f(b) = y$. Then $d = d(x,y) = d(f(a),f(b)) < d(a,b)$, which contradicts the definition of $d$.

Therefore $\text{diam} A = 0$ which is possible only when $A$ contains a single point $a$. This is a fixed point of $f$. Since $A$ trivially contains all fixed points of $f$, we are done.

$\endgroup$
6
  • $\begingroup$ can you please review my post once again? I've just added a PS. $\endgroup$ – Saaqib Mahmood Apr 1 '20 at 15:06
  • $\begingroup$ @SaaqibMahmood Your PS is correct and does not have gaps. $\endgroup$ – Paul Frost Apr 5 '20 at 15:40
  • $\begingroup$ @PaulFrost I don't understand why $a \in A$. Could you give me an explanation of this fact? $\endgroup$ – John Mars Dec 24 '20 at 14:31
  • $\begingroup$ @JohnMars Please explain where precisely you want an explanation. Is it why $a \in A_{\varphi(m)}$? Or why $\bigcap_m A_{\varphi(m)} = A$? $\endgroup$ – Paul Frost Dec 25 '20 at 9:00
  • $\begingroup$ @PaulFrost I don't see why $a \in A_{\varphi(m)}$. $\endgroup$ – John Mars Dec 25 '20 at 14:41

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.