## Tuesday, January 19, 2016

### Cayley-Hamilton Theorem II: The Arzela-Ascoli Theorem

In the previous post, we gave ourselves an incredibly useful measuring stick for vectors and linear operators. We now look at some general results regarding the convergence of sequences of functions, in order to build towards the Cayley-Hamilton Theorem.
Let $$\{f_i\}$$ be a sequence of functions which map one metric space into another, say $$\mathbb{R}\to \mathbb{R}$$ (the following definitions can be easily extended). Suppose that there is some function $$f\colon \mathbb{R}\to \mathbb{R}$$ such that for each $$x\in \mathbb{R}$$ we have $$f_i(x)\to f(x)$$ then we say that $$\{f_i\}$$ converges to $$f$$ pointwise.
Now if given any $$\varepsilon>0$$ there exists some integer $$N$$ such that for all $$n\geq N$$ we have $$|f(x)-f_n(x)|$$ regardless of $$x$$ then we say that $$\{f_i\}$$ converges to $$f$$ uniformly.

If the range of the functions is a complete metric space, then there is a useful criterion for determining if a sequence converges uniformly. Suppose that given any $$\varepsilon\gt 0$$ there is some $$N\in \mathbb{N}$$ for which if $$n\gt m\gt N$$ we have $$|f_m(x)-f_n(x)|\lt \varepsilon$$ for all $$x$$. Then this sequence converges uniformly. We see this as follows. At each $$x$$ we have a Cauchy sequence, which must converge to some value which we define as $$f(x)$$. Now, given an $$\varepsilon\gt0$$, we choose $$N$$ large enough that $$|f_n(x)-f_m(x)|\lt \varepsilon/2$$ for all $$n,m\gt N$$. We then take $$N'\gt N$$ such that we have $$|f(x)-f_{N'}|\lt \varepsilon/2$$. Then for all $$n\gt N$$ we have $$|f(x)-f_n(x)|\lt |f(x)-f_{N'}(x)|+|f_{N'}(x)-f_n(x)|\lt \varepsilon.$$ The distinction between types of convergence is important, as there are several properties of uniformly convergent functions which which do not necessarily hold for merely pointwise convergent ones. One such example is that a sequence of continuous, uniformly convergent functions will converge to a continuous function, while pointwise convergent functions may not.
Fix $$\varepsilon\gt0$$ and take $$N$$ large enough that $$|f(x)-f_N(x)|\lt\varepsilon/3$$ for all $$x$$. Take $$\delta\gt 0$$ such that if $$|x-a|\lt\delta$$ then $$|f_N(a)-f_N(x)|\lt\varepsilon/3$$. It follows that $$|f(a)-f(x)|\leq |f(a)-f_N(a)|+|f_N(a)-f_N(x)|+|f(x)-f_N(x)|\lt\varepsilon,$$ so $$f$$ is continuous at $$a$$.
The classic counterexample for pointwise convergent functions is to consider the sequence $$f_n(x)=x^n$$ on $$[0,1]$$which will converge to $$f(x)=\begin{cases}0 \text{ for }x\in [0,1)\\ 1\text{ for } x=1\end{cases}.$$
Because of this property, it can be useful to obtain conditions as to when a collection of functions will have a subset which converges uniformly. The Arzela-Ascoli theorem gives us such conditions. To begin, we introduce a few more definitions.
Let $$\mathcal{F}$$ be a collection of functions. We say that it is an equicontinuous family if the following holds: given any $$\varepsilon\gt 0$$ there exists some $$\delta\gt 0$$ such that for any $$f\in \mathcal{F}$$ we have that $$|f(x)-f(y)|\lt \varepsilon$$ whenever $$|x-y|\lt \delta$$
We say that $$\mathcal{F}$$ is pointwise bounded if there is some function $$g$$ such that for all $$f\in \mathcal{F}$$ we have $$|f(x)|\lt g(x)$$. We say that $$\mathcal{F}$$ is uniformly bounded if there is some real number $$M$$ such that $$|f(x)|\lt M$$ for all $$f\in \mathcal{F}$$
Proposition: Let $$\{f_i\}$$ be a sequence of uniformly bounded functions on some countable set $$X$$. Then there is some subsequence $$\{f_{i_k}\}$$ which converges (pointwise) on all $$x\in X$$.
Proof: We order the elements of $$X$$ as $$x_1,x_2,\cdots$$. We note that $$\{f_i(x_1)$$ is a bounded sequence and so there is some subsequence which we denote $$\{f_{1,n}$$ for which $$f_{1,n}(x_1)$$. Now inductively repeat a process where we take a subsequence of $$f_{k-1,n}$$ which we denote $$f_{k,n}$$, such that $$f_{k,n}(x_k)$$ converges. We now write out the functions as follows $$\begin{matrix}f_{1,1}&f_{1,2}&f_{1,3}&\cdots\\f_{2,1}&f_{2,2}&f_{2,3}&\cdots\\f_{3,1}&f_{3,2}&f_{3,3}&\cdots\\\vdots&\vdots&\vdots&\ddots\end{matrix}$$ Since each following row is a subsequence of the previous rows, every function in preceeding rows appears in the row above, either directly above or to the right. It then follows that by taking the diagonal elements we see that $$\{f_{i,i}\}$$ is a subsequence of each row after a finite number of terms, and therefore converges for all $$x_n$$.∎
We have one more simple topology result, and then we are ready for the Ascoli-Azela theorem.
Lemma: Let $$K$$ be a compact set. Then there exists an at most countable set which is dense in $$K$$.
Proof: For each $$n\in \mathbb{N}$$ we know that the set of all open balls of radius $$1/n$$ must cover $$K$$, and so there is a finite subset which will cover $$K$$. Let $$A_n$$ be the collection of the centers of such open balls. Then if we define $$A=\bigcup A_n$$ we have that $$A$$ is at most countable as it is the countable union of finite sets, and will be dense in $$K$$ as given any $$x\in K$$ we can find a point in $$A$$ within any distance $$x$$.∎
Theorem [Arzela-Ascoli]: Let $$\mathcal{F}$$ be a family of equicontinuous functions on a compact set $$K$$. Furthermore, suppose that $$\mathcal{F}$$ is pointwise bounded. Then $$\mathcal{F}$$ is uniformly bounded, and has a subsequence $$\{f_{i_k}\}$$ which is uniformly bounded.
Proof: Take $$\varepsilon\gt 0$$ and select $$\delta$$ such that if $$|x-y|\lt \delta$$ then $$|f_j(x)-f_j(y)|\lt \varepsilon$$ for all $$f_j\in \mathcal{F}$$. Consider the set of all open balls of radius $$\delta$$, and consider the finite subcover of $$K$$. Let $$x_1,x_2,\cdots,x_n$$ be the centers of these balls. Then we know that there are numbers $$M_1,M_2,\cdots,M_n$$ such that $$|fjn(x_i)|\lt M_i$$. Now for any $$x\in K$$ we know that there is some $$x_i$$ with $$|x_i-x|\lt \delta$$. Thus we know that $$|f_j(x)|\lt M_i+\varepsilon$$ for all $$f_j\in \mathcal{F}$$. We then see that $$\mathcal{F}$$ is uniformly bounded by $$\max M_i +\varepsilon$$.
We now let $$A\subset K$$ be a countable dense subset of $$K$$, and take $$\{f_{i_k}\}$$ to be a subsequence of $$\mathcal{F}$$ which converges pointwise over all of $$A$$. Now fix $$\varepsilon\gt 0$$ and consider the same $$\delta$$ as before, but such that $$|f_{i_k}(x)-f_{i_k}(y)|\lt \varepsilon/3$$. If we consider the set of balls of radius $$\delta$$ about centers which are elements of $$A$$, we see that this covers $$K$$. We now let $$\{x_1,x_2,\cdots,x_n\}=B\subset A$$ be the centers of the finite subcover.
For any $$x\in K$$ there is some $$x_i\in B$$ with $$|x_i-x|\lt \delta$$. Now take $$N$$ large enough that for all $$x_i\in B$$ and $$m,n\gt N$$ we have $$|f_{i_n}(x_i)-f_{i_m}(x_i)|\lt\varepsilon/3$$. It follows that $$|f_{i_n}(x)-f_{i_m}(x)|\leq |f_{i_n}(x)-f_{i_n}(x_i)|+|f_{i_n}(x_i)-f_{i_m}(x_i)|+|f_{i_m}(x_i)-f_{i_m}(x)|\lt \varepsilon$$ and so $$\{f_{i_k}\}$$ converges uniformly.∎
We conclude this section by noting simply that on a compact set uniform convergence implies equicontinuity, and so equicontinuity is a necessary condition to show uniform convergence.