Advanced Analysis

Arzelà-Ascoli Theorem

Video. Arzelà-Ascoli Theorem
Question
Suppose \(\mathcal F\) is a collection of continuous, real-valued functions on a compact interval \(I\). When is \(\mathcal F\) compact with respect to the uniform metric?
Theorem (Arzelà-Ascoli Theorem)
Suppose \(\{f_n\}\) is a sequence of continuous functions on a compact interval \(I\). Then \(\{f_n\}\) has a uniformly convergent subsequence if and only if the functions are
  • uniformly bounded: there exists \(M < \infty\) such that \(|f_n(x)| \leq M\) for all \(n\) and all \(x \in I\), and
  • uniformly equicontinuous: for all \(\epsilon > 0\), there exists \(\delta > 0\) such that \(|x-y| < \delta\) implies \(|f_n(x) - f_n(y)| < \epsilon\) for each \(n\).
In other words, a set of continuous functions on \(I\) is sequentially compact if and only if the set is uniformly bounded and equicontinuous. (c.f. Bolzano-Weierstrass).

Proof of the Forward Direction
  • Let \(\{x_k\}_{k=1}^\infty\) be an enumeration of the rational numbers inside the interval \(I\).
  • Let \(f_{n_{11}}, f_{n_{12}}, f_{n_{13}}, \ldots\) be a subsequence of the original sequence such that \(f_{n_{1j}}(x_1)\) converges.
  • For each \(k > 1\), let \(f_{n_{k1}},f_{n_{k2}},\ldots\) be a subsequence of \(\{f_{n_{(k-1) j}} \}_{j=1}^\infty\) which converges at the point \(x_k\).
  • Let \(m_1 := n_{11}\) (first term of first sequence) and \(m_j := n_{jj}\) (j'th term of \(j\)-th sequence).
Claim
\(f_{m_j}(x)\) converges pointwise at each \(x_k\).
Proof
For \(j' \geq k\), the terms \(m_{j'}\) belong to the sequence of indices \(\{n_{kj}\}_{j=1}^\infty\). It must also be the case that the \(m_{j'}\) are strictly increasing (because, e.g., the \((j'+1)\)-st term of a subsequence must be at least as far along in the original sequence as the \((j'+1)\)-st term of that sequence). Thus \(f_{m_j}\) is, after dropping a finite number of initial terms, a subsequence of \(f_{n_{kj}}\) for every \(k\).
Proposition
If \(f_{m_j}\) is a sequence of uniformly equicontinuous functions on the compact interval \(I\) which converge pointwise on a dense subset, then they converge uniformly.
Proof
We will show it's a uniform Cauchy sequence. Pick your favorite \(\epsilon\).
  • Let \(\delta\) be taken so that \(|f_n(x) - f_n(y)| < \epsilon/3\) for every \(n\) and every \(x,y\) satisfying \(|x-y| < \delta\).
  • Let \(K\) be chosen so that every \(x \in I\) is distance less than \(\delta\) to one of the points \(x_1,\ldots,x_K\). (Must exist by compactness.)
  • Let \(J\) be chosen so that \(|f_{m_{j_1}}(x_k) - f_{m_{j_2}}(x_k)| < \epsilon/3\) for all \(j_1,j_2 \geq J\) and all \(k = 1,\ldots,K\).
  • For \(j_1,j_2 \geq J\), Pick any \(x\), let \(x_k\) be within distance \(\delta\) for \(k \leq K\).
    \[{}| f_{m_{j_1}}(x) - f_{m_{j_2}}(x)| {}\]
    \[{}= \Big| \left(f_{m_{j_1}}(x) - f_{m_{j_1}}(x_k) \right){}\]
    \[{}+\left( f_{m_{j_1}}(x_k) - f_{m_{j_2}}(x_k) \right){}\]
    \[{}+ \left( f_{m_{j_2}}(x_k) - f_{m_{j_2}}(x) \right) \Big| {}\]
  • Apply triangle inequality to the three grouped terms on the RHS. First term \(< \epsilon / 3\) by equicontinuity. Second term \(< \epsilon / 3\) because \(j_1,j_2\) are large enough according to Cauchy criterion at the point \(x_k\). Third term \(< \epsilon / 3\) by equicontinuity again.
Converse Direction Suppose \(\mathcal F\) is a collection of functions such that every sequence of functions in \(\mathcal F\) has a uniformly convergent subsequence.
  • If \(\mathcal F\) is not uniformly bounded, for each \(n \in \mathbb{N}\), let \(f_n \in {\mathcal F}\) be such that \(|f_n(x)| \geq n\) at some point \(x \in I\). If \(f_{n_j} \rightarrow f\) uniformly, then for all \(j \geq J_0\), \(||f_{n_j} - f|| < 1\) where \(||\cdot||\) is uniform norm. Thus
    \[ ||f_{n_j}|| \leq ||f_{n_j} - f|| + ||f|| \leq ||f|| + 1. \]
However, by construction \(|f_{n_j}(x)| > n_j\) at some point, so \(||f_{n_j}|| \geq n_j \rightarrow \infty\).
  • If \(\mathcal F\) is not equicontinuous, There must be some \(\epsilon\) and a sequence \(\delta_j \rightarrow 0\) and functions \(f_{n_j}\) such that at points \(x_j, y_j\) at distance \(|x_j - y_j| < \delta_j\), \(|f_{n_j} (x_j) - f_{n_j}(y_j)| \geq \epsilon\). Take a convergent subsequence (WLOG we can just relabel the index \(j\) and assume that \(f_{n_j}\) is itself a uniformly convergent sequence in \(j\)). By taking another subsequence, we can assume \(x_j \rightarrow x\) and \(y_j \rightarrow y\) as \(j \rightarrow \infty\). Because \(x_j - y_j \rightarrow 0\), \(x = y\).
  • We have a sequence of functions \(f_{n_j}\) which converge uniformly to some \(f\).
  • We have sequences \(x_j,y_j\) both converging to \(x\).
  • We have \(|f_{n_j}(x_j) - f_{n_j}(y_j)| \geq \epsilon\) for all \(j\).
  • Thus we have
    \[{}\lim_{j \rightarrow \infty} f_{n_j} (x_j) = f(x) {}\]
    \[{}= f(y) = \lim_{j \rightarrow \infty} f_{n_j}(y_j){}\]
    (exercise: prove it!). But
    \[ \lim_{j \rightarrow \infty} \left( f_{n_j}(x_j) - f_{n_j}(y_j) \right) \neq 0 \]
    because the terms always have magnitude at least \(\epsilon > 0\).