# Prob. 7 (b), Sec. 28, in Munkres' TOPOLOGY, 2nd ed: A shrinking self-map of a compact metric space has a unique fixed point

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?

• Isn't a shrinking map also a contraction? – Aniruddha Deshmukh Mar 8 '19 at 3:56
• @AniruddhaDeshmukh No, not necessarily. – Henno Brandsma Mar 8 '19 at 6:46
• @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. – Saaqib Mahmood Apr 1 '20 at 15:08

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.

• can you please review my post once again? I've just added a PS. – Saaqib Mahmood Apr 1 '20 at 15:06
• @SaaqibMahmood Your PS is correct and does not have gaps. – Paul Frost Apr 5 '20 at 15:40
• @PaulFrost I don't understand why $a \in A$. Could you give me an explanation of this fact? – John Mars Dec 24 '20 at 14:31
• @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$? – Paul Frost Dec 25 '20 at 9:00
• @PaulFrost I don't see why $a \in A_{\varphi(m)}$. – John Mars Dec 25 '20 at 14:41