# Prob. 7 (a), Sec. 28, in Munkres' TOPOLOGY, 2nd ed: A contraction 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 I'll only be attempting Part (a).

My Attempt

Prob. 7 (a):

There is a more common, I think, method of proving this assertion using the sequence of the so-called Picard's iterates together with the fact that every compact metric space is also complete.

Am I right?

However, in what follows, I'll be attempting a proof using the hint given by Munkres.

If there is a number $$\alpha < 1$$ such that the inequality $$d \big( f(x), f(y) \big) \leq \alpha d(x, y)$$ holds for any points $$x, y \in X$$, then since the value of the metric function $$d$$ is non-negative, we must also have $$0 \leq \alpha < 1. \tag{0}$$ We now show that if $$f$$ is a contraction, then $$f$$ is continuous.

Let $$\varepsilon$$ be an arbitrary positive real number. Choose a real number $$\delta$$ so that $$0 < \delta < \frac{\varepsilon}{1+\alpha}.$$ Then for any points $$x, y \in X$$ for which $$d(x, y) < \delta$$, we have $$d \big( f(x), f(y) \big) \leq \alpha d(x, y) \leq \alpha \frac{\varepsilon}{1+\alpha} = \frac{ \alpha }{1 + \alpha } \varepsilon < \varepsilon.$$ Thus $$f$$ is continuous (in fact uniformly continuous) on $$X$$.

Now for each $$n \in \mathbb{N}$$, let us put $$f^1 \colon= f, \ \mbox{ and } \ f^{n+1} \colon= f\circ f^n. \tag{Def. 0}$$ Then the map $$f^n$$, which is the composite of $$f$$ with itself a finite number of times, is also continuous on $$X$$.

For each $$n \in \mathbb{N}$$, let us put $$A_n \colon= f^n(X), \tag{Def. 1}$$ and let $$A_0 \colon= X$$. Then as $$X$$ is compact and $$f^n$$ is a continuous map of $$X$$ into itself, so the set $$A_n = f^n(X)$$ is a compact subspace of $$X$$, by Theorem 26.5 in Munkres; and furthermore as $$X$$, being a metric space is also Hausdorff, and as the set $$f^n(X)$$ is a compact subspace of $$X$$, so the set $$f^n(X)$$ is also closed in $$X$$, by Theorem 26.3 in Munkres.

We also note that, for each $$n \in \mathbb{N}$$, if $$p \in A_{n+1}$$, then $$p = f^{n+1}(q)$$ for some point $$q \in X$$; but then $$p = f^n\big(f(q)\big)$$ and $$f(q)$$ is also a point of $$X$$, which implies that $$p \in f^n(X)$$, that is, $$p \in A_n$$, showing that $$A_{n+1} \subset A_n$$ or $$A_n \supset A_{n+1}$$.

Thus the collection $$\left\{ \ A_n \colon \ n \in \mathbb{N} \ \right\}$$ is a nested sequence of non-empty closed sets in the compact space $$X$$; therefore the intersection $$\bigcap_{n \in \mathbb{N} } A_n$$ is non-empty, by (a corollary of) Theorem 26.9 in Munkres. Let us put $$A \colon= \bigcap_{n \in \mathbb{N} } A_n. \tag{Def. 2}$$ Now since each of the sets $$A_n$$ is closed, by Theorem 17.1 in Munkres their intersection $$A$$ is a non-empty closed set in $$X$$, and since $$X$$ is compact, the set $$A$$ is also compact, by Theorem 26.2 in Munkres.

For each $$n \in \mathbb{N}$$, we find that if $$x, y$$ are any points in $$A_{n+1} = f^{n+1}(X)= f \left( f^n(X) \right)$$, then we have $$x = f\left(x^\prime \right)$$ and $$y = f\left( y^\prime\right)$$ for some points $$x^\prime, y^\prime$$ in $$A_n = f^n(X)$$, and so $$d (x, y) = d \big( f \left( x^\prime \right), f \left( y^\prime \right) \big) \leq \alpha d \left( x^\prime, y^\prime \right),$$ thus showing that $$\mathrm{diam}\, A_{n+1} \leq \alpha \ \mathrm{diam}\, A_n. \tag{1'}$$

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{1''}$$

Moreover, for any points $$x, y \in X$$, we have $$d\big( f(x), f(y) \big) \leq \alpha\, d(x, y) \leq \alpha\ \mathrm{diam}\, X,$$ and hence $$\mathrm{diam}\, f(X) \leq \alpha \ \mathrm{diam}\, X,$$ or $$\mathrm{diam}\, A_1 \leq \alpha \ \mathrm{diam}\, A_0,$$ Refer to (Def. 0) above. This inequality together with (1') yields $$\mathrm{diam}\, A_n \leq \alpha \ \mathrm{diam}\, A_{n-1} \tag{1}$$ for all $$n \in \mathbb{N}$$.

Also for each $$n \in \mathbb{N}$$, as $$A_n \subset X$$, so we must have $$\mathrm{diam}\, A_n \leq \mathrm{diam}\, X < +\infty,$$ by virtue of (1'') above. In particular, we have $$\mathrm{diam}\, A_1 \leq \mathrm{diam}\, X < +\infty,$$

Now using (1) we find that, for each $$n \in \mathbb{N}$$, we have $$\mathrm{diam}\, A_n \leq \alpha \ \mathrm{diam}\, A_{n-1} \leq \cdots \leq \alpha^{n-1} \ \mathrm{diam}\, A_1 \leq \alpha^n \ \mathrm{diam}\, A_0 = \alpha^n\ \mathrm{diam}\, X,$$ [Refer to (Def. 0) above.] and so $$\mathrm{diam}\, A_n \leq \alpha^n\ \mathrm{diam}\, X. \tag{2}$$

From (Def. 2) above, we note that, for each $$n \in \mathbb{N}$$, as $$A \subset A_n$$, so $$\mathrm{diam}\, A \leq \mathrm{diam}\, A_n$$ and hence (2) implies that $$0 \leq \mathrm{diam}\, A \leq \alpha^n \ \mathrm{diam}\, X; \tag{3}$$ but from (0) above we also find that $$\lim_{n \to \infty} \alpha^n = 0,$$ and this together with (1'') above yields $$\lim_{n \to \infty} \alpha^n \ \mathrm{diam}\, X = 0$$ also, and this in conjunction with (3) implies that $$\mathrm{diam}\, A = 0. \tag{4}$$

We now show that the set $$A$$ has only one point in it. Suppose that $$p$$ and $$q$$ are any two distinct points of $$A$$. Then $$\mathrm{diam}\, A \geq d(p, q) > 0,$$ which contradicts (4). So set $$A$$ can have at most one point. But as has been shown above, set $$A$$ is non-empty. Hence set $$A$$ has a single point. Let $$p$$ be this point. We show that this point $$p$$ is the unique fixed point of $$f$$.

We first show that the single point $$p$$ in set $$A$$ is a fixed point of $$f$$.

If $$f(p) \in A$$, then as set $$A$$ has only one point, so we must have $$f(p) = p$$.

So let us suppose, if possible, that $$f(p) \not\in A$$. Then there exists a natural number $$n$$ such that $$f(p) \not\in A_n$$; [Refer to (Def. 2) above.] let $$m$$ be the smallest such natural number; then by our choice of $$m$$ we can conclude that $$f(p) \not\in A_m$$ but $$f(p) \in A_{m-1}$$. [Refer to (Def. 1) above.] Thus $$f(p) \in A_{m-1} \setminus A_m. \tag{5}$$ Also refer to (1) above.

Now using (Def. 1) above, we see that $$A_m = f^m(X) = f\left( f^{m-1}(X) \right) = f\left(A_{m-1}\right). \tag{6}$$ And as $$f(p) \not\in A_m$$, so $$p$$ cannot be in $$A_{m-1}$$, because of (6). But as $$p \in A$$ and $$A \subset A_{m-1}$$, so we must have $$p \in A_{m-1}$$ as well, [Refer to (Def. 2) above.] which in turn would imply that $$f(p) \in A_m$$, contrary to our choice of $$m$$. Hence we must have $$f(p) \in A$$ and therefore $$p$$ is a fixed point of $$f$$.

Finally, we show that $$f$$ can have at most one fixed point.

If $$q \in X$$ is any fixed point of $$f$$, then we have $$q = f(q)$$, and this in turn implies that, for each $$n \in \mathbb{N}$$, we have $$q = f^n(q)$$, showing that $$q \in A_n$$ [Refer to (Def. 1) above.] for each $$n\in \mathbb{N}$$, and hence $$q \in A$$. [Refer to (Def. 2) above.] Thus every fixed point of $$f$$ is an element of $$A$$. But, as we have shown in one of the preceding paragraphs, since set $$A$$ has only a single point, the map $$f$$ can have at most one fixed point.

Is each and every step in my proof correct? If so, are all these steps properly sequenced? Is my presentation clear enough too?

Or else, where is (are) the issue(s) in terms of accuracy and clarity of logic and presentation in my attempt?

• $diam X$ is a supremum - it's possible that it isn't attained anywhere. How do you conclude that $diam f(X) \leq \alpha diam X$? – enedil Mar 6 at 19:34
• @enedil it is because of the fact that $f$ is a contraction. So if $a, b \in f(X)$, then $a = f(x)$, $b=f(y)$ for some $x, y \in X$, and so $$d(a,b)=d\big(f(x),f(y)\big)\leq\alpha\ d(x,y)\leq\alpha\ \mathrm{diam}\, X,$$ which implies that $$\mathrm{diam}\, f(X)\leq \alpha\ \mathrm{diam}\, X.$$ Is it clear now? – Saaqib Mahmood Mar 6 at 20:08
• No, it doesn't (necessarily). First line is true, indeed $d(a, b) \leq \alpha \diam X$. But you have $d(a, b) \leq \diam f(X)$. How do you conclude this final inequality? Because if $d(a, b) \not = \diam f(X)$, it's not obvious that the inequality is true at all (and by "not clear", I mean I don't see a proof right now). – enedil Mar 6 at 20:11
• @enedil this follows from the following result about sets of real numbers: Let $S, T$ be nonempty subsets of $\mathbb{R}$ such that, for every element $s\in S$ there exists an element $t_s\in T$ such that $s\leq t_s$. If $T$ is bounded, then so is $S$, and we have the inequality $$\sup \, S \leq \sup \, T.$$ – Saaqib Mahmood Mar 7 at 18:05

Your proof seems to be overly complicated. I couldn't get through it, I apologize. Here's an alternative:

Let $$\alpha$$ be the contraction constant. Fix $$a_0\in X$$ and let $$a_n=f(a_{n-1})$$, i.e. $$a_n=f^n(a_0)$$.

Lemma 1. The sequence $$(a_n)$$ is convergent.

Proof. If $$n then

$$d(a_n, a_m)\leq\alpha^n d(a_0, a_{m-n})<\alpha^n M$$

where $$M$$ is some constant independent of $$n,m$$ (which exists since $$X$$ is compact and so the metric $$d:X\times X\to\mathbb{R}$$ is bounded). This clearly means that $$(a_n)$$ is Cauchy. And since $$X$$ is compact then every Cauchy sequence is convergent. $$\Box$$

Lemma 2. $$f$$ has a fixed point.

Proof. Let $$b\in X$$ be the limit of $$(a_n)$$. Since $$a_n\to b$$ then $$f(a_n)\to f(b)$$ by continuity of $$f$$. Now $$f(a_n)=a_{n+1}$$ and so $$a_{n+1}\to f(b)$$ meaning $$a_n\to f(b)$$. By the uniqueness of the limit $$f(b)=b$$. $$\Box$$

Lemma 3. The fixed point of $$f$$ is unique.

Proof. Assume that $$f(b)=b$$ and $$f(c)=c$$ for some $$b,c\in X$$. Then

$$d(b,c)=d(f(b), f(c))\leq\alpha d(b,c)$$

and since $$0\leq\alpha <1$$ then this can only hold for $$d(b,c)=0$$ meaning $$b=c$$. $$\Box$$

Note that the only place I use the fact that $$X$$ is compact is in the proof of Lemma 1. So in order to show that $$f$$ has the unique fixed point over a complete space all you have to do is to prove Lemma 1. For full details see here.

• yes, your proof is the one most commonly given; this is the proof I've mentioned before giving my attempt; in fact the terms of the sequence you've defined is just what is called the Picard's iterates. – Saaqib Mahmood Mar 7 at 18:03