Section 2.8 Compactness and diagonal subsequences
Compactness is one of the fundamental tools in analysis, and this unit is no exception. Recall the following definition.
Definition 2.36.
A subset \(K\) of a metric space \(X\) is called (sequentially) compact if every sequence \(x_n\) in \(K\) has a subsequence which converges to a limit in \(K\text{.}\)
Theorem 2.37.
A subset \(K\) of \(\R^N\) is (sequentially) compact if and only if it is closed and bounded, and relatively compact if and only if it is bounded.
Proof.
This is proved, for instance, in MA30252.
Often when using compactness or relative compactness, we begin with a sequence \(x_n\) and then pass to a subsequence \(x_{n_k}\text{.}\) Often we need to pass to further subsequences, however, at which point this notation with multiple subscripts quickly becomes unwieldy, as in the following example.
Example 2.38. Subscript nightmare.
Suppose that \(K_i \subseteq \R^{N_i}\) are compact sets for \(i=1,2,3\text{.}\) We will show directly that the Cartesian product \(K = K_1 \times K_2 \times K_3 \subseteq
\R^{N_1+N_2+N_3}\) is compact. Let \(x_n = (a_n,b_n,c_n)\) be a sequence in \(K\text{,}\) so that \(a_n\) is a sequence in \(K_1\text{,}\) \(b_n\) is a sequence in \(K_2\text{,}\) and \(c_n\) is a sequence in \(K_3\text{.}\)
Since \(K_1\) is compact, we can find a subsequence \(a_{n_k}\) of \(a_n\) which converges to some \(a_0 \in K_1\text{.}\) Then, since \(K_2\) is compact, \(b_{n_k}\) has a subsequence \(b_{n_{k_\ell}}\) which converges to \(b_0 \in K_2\text{.}\) Finally, since \(K_3\) is compact, \(c_{n_{k_\ell}}\) has a subsequence \(c_{n_{k_{\ell_m}}}\) which converges to \(c_0 \in K_3\text{.}\) Since subsequences of convergent sequences are convergent, we then have that \(b_{n_{k_{\ell_m}}}\) converges to \(b_0\) and \(a_{n_{k_{\ell_m}}}\) converges to \(a_0\text{.}\) Thus \(x_{n_{k_{\ell_m}}}\) converges to \(x_0=(a_0,b_0,c_0) \in K_1 \times K_2 \times K_3\text{.}\)
The notational unpleasantness above can be avoided if we make the following observation. Since our goal is to produce a subsequence of \(x_n\text{,}\) at any point in the argument we can simply replace \(x_n\) with one of its subsequences.
Example 2.39. Escaping the nightmare.
Let’s repeat Example 2.38, but without using so many subscripts.
Since \(K_1\) is compact, by replacing \(x_n\) with an appropriate subsequence we can assume that \(a_n\) converges to \(a_0 \in K_1\text{.}\) Then, since \(K_2\) is compact, we can again replace \(x_n\) with a subsequence to ensure that \(b_n\) converges to \(b_0 \in K_2\text{.}\) Finally, we replace \(x_n\) with yet another subsequence so that \(c_n\) converges to \(c_0 \in K_3\text{,}\) at which point the entire sequence \(x_n=(a_n,b_n,c_n)\) converges to \(x_0 =
(a_0,b_0,c_0)\text{.}\)
With this in mind, we next recall the following important result on the existence of maxima and minima.
Theorem 2.40. Existence of maxima and minima.
Let \(K \subseteq \R^N\) be compact, and let \(f \in C^0(K)\text{.}\) Then \(f\) achieves its maximum and minimum over \(K\) in the sense that there exist \(x_{\min},x_{\max} \in K\) such that
\begin{equation*}
\inf_K f = f(x_{\min}) = \min_K f
\qquad \text{and} \qquad
\sup_K f = f(x_{\max}) = \max_K f\text{.}
\end{equation*}
Proof.
Using Definition 2.33 we can find a sequence \(x_n\) in \(K\) such that \(f(x_n) \to \sup_K f\text{.}\) By compactness, we can replace \(x_n\) with a subsequence and assume that \(x_n \to x_{\max}\) for some \(x_{\max} \in K\text{.}\) Note that this does not alter the fact that \(f(x_n) \to
\sup_K f\text{.}\) Since \(f\) is sequentially continuous, we then have
\begin{equation*}
f(x_{\max}) = \lim_{n\to \infty} f(x_n) = \sup_K f
\end{equation*}
as desired. The argument for \(\inf_K f\) is similar.
Recall from MA30252 that Theorem 2.37 does necessarily not hold if \(\R^N\) is replaced by a more general metric space \(X\text{.}\) In particular, when we are interested in the uniform convergence of sequences of functions, boundedness must be supplemented by a condition called equicontinuity.
Definition 2.41.
Let \(A \subseteq \R^N\) be a set. We say a sequence \(f_n\) in \(C^0(A)\) is (uniformly) bounded if there exists a constant \(M\) independent of \(n\) such that \(\abs{f_n(x)} \le M\) for all \(x \in
A\text{.}\)
Definition 2.42.
Let \(A \subseteq \R^N\) be a set. A sequence \(f_n\) in \(C^0(A)\) is called equicontinuous at a point \(x \in A\) if for all \(\varepsilon \gt
0\) there exists \(\delta \gt 0\) independent of \(n\) such that \(|f_n(y)-f_n(x)| \lt \varepsilon\) for all \(y \in A\) with \(|y-x| \lt \delta\text{.}\) We say the sequence is equicontinuous if it is equicontinuous at all points \(x \in A\text{.}\)
Theorem 2.43. Arzelà–Ascoli.
Let \(K \subseteq \R^N\) be compact, and let be \(f_n\) a sequence in \(C^0(K)\) which is uniformly bounded and equicontinuous. Then \(f_n\) has a subsequence which converges uniformly on \(K\) to a function \(f \in
C^0(K)\text{.}\)
Proof.
A stronger version of this theorem is proved in MA30252.
The conclusion of Theorem 2.43 is in general false when the compact set \(K\) is replaced an open set \(\Omega\text{.}\) Thankfully, we can still make progress by ‘approximating’ \(\Omega\) by compact subsets and asking for something weaker than uniform convergence.
Lemma 2.44. Exhaustion by compact sets.
Let \(\Omega \subseteq \R^N\) be an open set. Then there exists a sequence of compact subsets \(K_m\) of \(\Omega\) with the following properties:
- \(K_m \subseteq (K_{m+1})^\circ\) for all \(m \in \N\text{,}\) where here \((K_{m+1})^\circ\) denotes the interior of the set \(K_{m+1}\text{;}\)
- \(\Omega = \bigcup_{m=1}^\infty K_m\text{;}\) and
- for any compact subset \(K\) of \(\Omega\text{,}\) there exists \(m \in \N\) such that \(K \subset K_m\text{.}\)
We say that the sequence \(K_m\) is an exhaustion of \(\Omega\) by compact sets.
Proof.
For any \(m \in \N\text{,}\) define \(K_m\) to be the set of \(x \in \Omega\) such that \(\abs x \le m\) and \(\abs{x-y} \ge 1/m\) for all \(y \in \R^N
\without \Omega\text{.}\) We leave the verification of the desired properties as Exercise 2.8.6.
Definition 2.45.
Let \(\Omega \subseteq \R^N\) be an open set, let \(f_n\) be a sequence in \(C^0(\Omega)\text{,}\) and let \(f \in C^0(\Omega)\text{.}\) We say that \(f_n\) converges to \(f\) uniformly on compact sets if, for any compact set \(K \subset
\Omega\text{,}\) the restrictions \(f_n|_K\) converge uniformly to \(f|_K\text{.}\)
We are now ready to state and prove our replacement for Theorem 2.43. The proof will involve sequences of sequences of functions, and what is sometimes called a diagonalisation argument.
Theorem 2.46.
Let \(\Omega \subseteq \R^N\) be an open set. If \(f_n\) is a sequence in \(C^0(\Omega)\) which is bounded and equicontinuous, then there exists a subsequence \(f_{n_k}\) which converges on compact subsets to a limit \(f \in
C^0(\Omega)\text{.}\)
Proof.
Applying Lemma 2.44, let \(K_m\) be an exhaustion of \(\Omega\) by compact sets. First, consider the sequence of functions \(f_n|_{K_1} \in C^0(K_1)\text{.}\) By assumption this sequence is bounded and equicontinuous, and so, since \(K_1\) is compact, by Theorem 2.43 it has a subsequence which converges uniformly to some \(C^0(K_1)\) function. Denote this subsequence by \(f_{n(1,k)}\) and the uniform limit by \(f^{(1)}\text{.}\)
Now consider the sequence of functions \(f_{n(1,k)}|_{K_2} \in
C^0(K_2)\text{.}\) Arguing as above we can apply Theorem 2.43 a second time to find a further subsequence, denoted \(f_{n(2,k)}\text{,}\) and a limit \(f^{(2)} \in C^0(K_2)\text{,}\) such that \(f_{n(2,k)}\) converges uniformly to \(f^{(2)}\) on \(K_2\text{.}\) Since \(K_2 \supset K_1\text{,}\) \(f_{n(2,k)}\) also converges uniformly on \(K_1\text{,}\) and so the uniqueness of (uniform) limits implies that \(f^{(2)}|_{K_1} = f^{(1)}\text{.}\)
Continuing in this way, we can define \(f_{n(m,k)}\) for all \(k,m \in
\N\text{.}\) Each sequence \((f_{n(m+1,k)})_{k \in \N}\) is a subsequence of the previous sequence \((f_{n(m,k)})_{k \in \N}\text{,}\) and \((f_{n(m,k)})_{k \in
\N}\) converges uniformly on \(K_m\) to some \(f^{(m)} \in C^0(K_m)\text{.}\) By the uniqueness argument above, the function \(f \maps \Omega \to \R\) defined by
\begin{equation*}
f(x) = f^{(m)}(x) \quad \text{for } x \in K_m
\end{equation*}
is well-defined, and moreover we can check that \(f \in C^0(\Omega)\text{.}\)
Arranging our family of nested subsequences in a grid
\begin{equation*}
\begin{array}{cccc}
f_{n(1,1)} \amp f_{n(1,2)} \amp f_{n(1,3)} \amp \cdots \\
f_{n(2,1)} \amp f_{n(2,2)} \amp f_{n(2,3)} \amp \cdots \\
f_{n(3,1)} \amp f_{n(3,2)} \amp f_{n(3,3)} \amp \cdots \\
\vdots \amp \vdots \amp \vdots \amp \ddots
\end{array}
\end{equation*}
we consider the diagonal subsequence \(f_{n_k} =
f_{n(k,k)}\text{.}\) Fix \(m \in \N\text{.}\) Since each row is a subsequence of all previous rows, we can check that \((f_{n(k,k)})_{k \ge m}\) is a subsequence of \((f_{n(m,k)})_{k \ge 1}\text{.}\) Thus \(f_{n(k,k)}\) converges to \(f\) uniformly on \(K_m\text{.}\)
Finally, let \(K \subseteq \Omega\) be compact. Then by Lemma 2.44, there exists \(m \in \N\) such that \(K \subseteq K_m\text{.}\) Since \(f_{n_k}\) converges to \(f\) uniformly on \(K_m\text{,}\) the same uniform convergence also holds on \(K\text{.}\)
Exercises Exercises
1. (PS3) Suprema, maxima, and closures.
Let \(\Omega\) be an open set and let \(f \in C^0(\overline \Omega)\text{.}\) Show that \(\sup_\Omega f = \sup_{\overline \Omega} f\text{.}\) If \(\Omega\) is bounded, conclude that \(\sup_\Omega f = \max_{\overline \Omega} f\text{.}\)
Hint.
Clearly \(\sup_{\overline \Omega} f \ge \sup_\Omega f\text{.}\) To see the reverse inequality, recall that for any \(x \in \overline\Omega\) there exists a sequence \(x_n\) in \(\Omega\) which converges to \(x\text{,}\) and use the sequential continuity of \(f\text{.}\)
Solution.
Since \(\overline\Omega \supset \Omega\text{,}\) we clearly have \(\sup_{\overline\Omega} f \ge
\sup_\Omega f\text{,}\) and so it suffices to prove the reverse inequality. For any \(x
\in \overline\Omega\text{,}\) there exists a sequence of points \(x_n \in \Omega\) with \(x_n \to x\text{.}\) Since \(x_n \in \Omega\text{,}\) we have \(f(x_n) \le \sup_\Omega f\) for each \(n\text{.}\) Passing to the limit using the sequential continuity of \(f\text{,}\) we find \(f(x) \le \sup_\Omega f\text{.}\) Since \(x \in \overline\Omega\) was arbitrary, we conclude that \(\sup_{\overline\Omega} f \le \sup_\Omega f\) as desired.
If \(\Omega\) is bounded, then \(\overline\Omega\) is compact, and so Theorem 2.40 guarantees that \(\sup_{\overline\Omega} f\) is achieved, i.e. \(\sup_{\overline\Omega} f = \max_{\overline \Omega} f\text{.}\) Combining with the previous part we have \(\sup_\Omega f = \max_{\overline\Omega} f\text{.}\)
2. (PS4) Sufficient condition for equicontinuity.
Let \(B = B_r(x_0) \subset \R^N\) be a ball, and let \(f_n\) be a sequence in \(C^1(\overline B)\) with the property that
\begin{equation*}
\sup_{B} \abs{\nabla f_n} \le M
\end{equation*}
for some constant \(M\) independent of \(n\text{.}\) Show that \(f_n\) is equicontinuous at \(x_0\text{.}\)
Hint.
Let \(x \in B\) and consider the single-variable function \(g(t) = f_n(tx_0+(1-t)x)\text{.}\) Express \(g(1)-g(0)\) using either the mean value theorem or the fundamental theorem of calculus, and then estimate the result in terms of \(M\) and \(\abs{x-x_0}\text{.}\)
Solution 1. Using the mean value theorem
Fix \(x \in B\) and \(n \in \N\text{,}\) and define \(g(t) = f(tx_0+(1-t)x)\text{.}\) Then \(g \in C^1([-1,1])\text{,}\) and hence the mean value theorem implies that there exists \(t \in (0,1)\) such that
\begin{align*}
f_n(x)-f_n(x_0)
\amp = \frac{g(1)-g(0)}{1-0} \\
\amp = g'(t)\\
\amp = \nabla f_n(tx_0+(1-t) x) \cdot (x_0-x)\text{.}
\end{align*}
Estimating the right hand side we find
\begin{equation*}
\abs{f_n(x)-f_n(x_0)} \le M \abs{x-x_0}\text{.}
\end{equation*}
Since the constant \(M\) on the right hand side is independent of both \(x \in B\) and \(n \in \N\text{,}\) the desired equicontinuity follows.
Solution 2. Using the fundamental theorem of calculus
For any \(x \in B\) and \(n \in \N\text{,}\) the fundamental theorem of calculus followed by the chain rule give
\begin{align*}
f_n(x)-f_n(x_0)
\amp =
\int_0^1 \frac d{dt} f_n(tx+(1-t)x_0)\, dt\\
\amp =
\int_0^1 \nabla f_n (tx+(1-t)x_0) \cdot (x-x_0)\, dt\\
\amp =
\left(\int_0^1 \nabla f_n(tx+(1-t)x_0)\, dt \right) \cdot (x-x_0)\text{.}
\end{align*}
Taking the norm of both sides, we then estimate
\begin{align*}
\abs{f_n(x)-f_n(x_0)}
\amp \le
\left(\int_0^1 \abs{\nabla f_n(tx+(1-t)x_0)}\, dt \right) \abs{x-x_0}\\
\amp \le
M\abs{x-x_0}\text{.}
\end{align*}
Since the constant \(M\) on the right hand side is independent of both \(x \in B\) and \(n \in \N\text{,}\) the desired equicontinuity follows.
Comment 1.
The solutions above establish, for any \(x \in B_r(x_0)\) and any \(n \in \N\text{,}\) the estimate \(\abs{f_n(x)-f_n(x_0)} \le
M\abs{x-x_0}\text{.}\) To see that this implies equicontinuity, let \(\varepsilon \gt 0\) and choose \(\delta = \varepsilon/M\text{.}\) Then for any \(x \in B_r(x_0)\) with \(\abs{x-x_0} \lt \delta\text{,}\) and for any \(n \in \N\text{,}\) our above estimate gives \(\abs{f_n(x)-f(x_0)} \lt M (\varepsilon/M) = \varepsilon\text{.}\)
Note that the definition of equicontinuity, like the definition of continuity, hands us an arbitrary \(\varepsilon \gt 0\) and asks us to produce an appropriate \(\delta \gt 0\text{.}\) We cannot choose our favourite \(\varepsilon \gt 0\) and only consider this value.
Comment 2.
Note that the domain of the function \(g\) in the first solution above is some appropriate closed interval \([-1,1]\text{,}\) and not the same ball \(B\) that \(f\) is defined on. Indeed, \(g\) is a function of a single real variable, and \(B \subset \R^N\) is a set in \(N\) dimensions.
3. Non-existence of maxima and minima.
Give counterexamples showing that the conclusion of Theorem 2.40 can fail
(a)
if \(K\) is not compact; or
(b)
if \(f \maps K \to \R\) is bounded but not continuous.
4. More diagonalisation.
Let \(f_n\) be a sequence of functions \(\N \to \R\text{,}\) and suppose that for some \(M \gt 0\) we have \(\abs{f_n(i)} \le M\) for all \(i,n \in
\N\text{.}\)
(a)
By imitating the proof of Theorem 2.46, show that there is a subsequence \(f_{n_k}\) and a function \(f \maps \N \to \R\) such that \(f_{n_k}\) converges to \(f\) uniformly on any finite subset \(K \subset \N\text{.}\)
(b)
Give a counterexample showing that the convergence in the previous part need not be uniform on \(\N\text{.}\)
5. Sequences of functions on \(\R\).
Let \(f_n \in C^1(\R)\) be a sequence of functions, and suppose that for some fixed \(M \gt 0\) we have \(\abs{f_n(x)} \le M\) and \(\abs{f_n'(x)} \le
M\) for all \(x \in \R\) and all \(n \in \N\text{.}\)
(a)
Show that there is a subsequence \(f_{n_k}\) and a function \(f \in
C^0(\R)\) such that \(f_{n_k} \to f\) uniformly on any compact set \(K
\subseteq \R\text{.}\)
Hint.
Use Exercise 2.8.2 and Theorem 2.46.
(b)
Give an example to show that the convergence in the previous part need not be uniform on all of \(\R\text{.}\)
Hint.
One option is to consider sequences of the form \(f_n(x)=g(x-n)\) for a fixed function \(g\) which vanishes outside of a fixed interval.
(c)
(Optional) Suppose that \(f_n \to f\) uniformly on all of \(\R\text{,}\) and that \(f_n(x) \to 0\) as \(x \to +\infty\) for all \(n\text{.}\) Show that \(f(x) \to 0\) as \(x \to \infty\text{.}\)
6. Exhaustion by compact sets.
Complete the proof of Lemma 2.44.
