View source for Coordinate rotations and reflections

The '''Arzelà–Ascoli theorem''' is a fundamental result of [[mathematical analysis]] giving [[necessary and sufficient conditions]] to decide whether every sequence of a given family of [[real number|real]]-valued [[continuous function]]s defined on a [[closed set|closed]] and [[bounded set|bounded]] [[interval (mathematics)|interval]] has a [[uniform convergence|uniformly convergent]] [[subsequence]].  The main condition is the [[equicontinuity]] of the family of functions. The theorem is the basis of many proofs in mathematics, including that of the [[Peano existence theorem]] in the theory of [[ordinary differential equations]], [[Montel's theorem]] in [[complex analysis]], and the [[Peter-Weyl theorem]] in [[harmonic analysis]].

The notion of equicontinuity was introduced at around the same time by {{harvtxt|Ascoli|1883–1884}} and {{harvtxt|Arzelà|1882–1883}}. A weak form of the theorem was proven by {{harvtxt|Ascoli|1883–1884}}, who established the sufficient condition for compactness, and by {{harvtxt|Arzelà|1895}}, who established the necessary condition and gave the first clear presentation of the result.  A further generalization of the theorem was proven by {{harvtxt|Fréchet|1906}}, to sets of real-valued continuous functions with domain a [[compact set|compact]] [[metric space]] {{harv|Dunford|Schwartz|1958|p=382}}.  Modern formulations of the theorem allow for the domain to be compact [[hausdorff space|Hausdorff]] and for the range to be an arbitrary metric space.  More general formulations of the theorem exist that give necessary and sufficient conditions for a family of functions from a [[Compactly generated space|compactly generated]] Hausdorff space into a [[uniform space]] to be compact in the [[compact-open topology]]. {{harvtxt|Kelley|1991|loc=page 234}}.

== Statement and first consequences ==
A sequence {''&fnof;''<sub>''n''</sub>}<sub>''n''∈'''N'''</sup> of [[continuous function]]s on an interval ''I''&nbsp;=&nbsp;[''a'',''b''] is uniformly  bounded if there is a number ''M'' such that
:<math>|f_n(x)| \le M</math>
for every function ''&fnof;''<sub>''n''</sub> belonging to the sequence, and every ''x''&nbsp;∈&nbsp;[''a'',''b''].  The sequence is ''uniformly equicontinuous'' if, for every ε&nbsp;>&nbsp;0, there exists a δ&nbsp;>&nbsp;0 such that
:<math>|f_n(x)-f_n(y)| < \varepsilon\,</math> whenever <math>|x-y|<\delta\,</math>
for every ''&fnof;''<sub>''n''</sub> belonging to the sequence. Succinctly, a sequence is uniformly equicontinuous if and only if all of its elements admit ''the same'' [[modulus of continuity]].  In simplest terms, the theorem can be stated as follows:

:Consider a [[sequence]] of real-valued continuous functions (''&fnof;''<sub>''n''</sub>)<sub>''n''&isin;'''N'''</sub> defined on a closed and bounded [[interval (mathematics)|interval]] [''a'',&nbsp;''b''] of the [[real line]]. If this sequence is [[uniformly bounded]] and [[equicontinuous]], then there exists a [[subsequence]] (''&fnof;''<sub>''n''<sub>''k''</sub></sub>) that [[uniform convergence|converges uniformly]].

The converse is also true, in the sense that if every subsequence of (''&fnof;''<sub>''n''</sub>) itself has a uniformly convergent subsequence, then (''&fnof;''<sub>''n''</sub>) is uniformly bounded and equicontinuous.  (See [[#Necessity|below]] for a proof.) 

===Examples===
;Differentiable functions
The hypotheses of the theorem are satisfied by a uniformly bounded sequence {''&fnof;''<sub>''n''</sub>} of [[derivative|differentiable]] functions with uniformly bounded derivatives.  Indeed, uniform boundedness of the derivatives implies by the [[mean value theorem]] that for all ''x'' and ''y'',
:<math>|f_n(x) - f_n(y)| \le K |x-y|,</math>
where ''K'' is the [[supremum]] of the derivatives of functions in the sequence and is independent of ''n''.  So, given ε&nbsp;>&nbsp;0, let δ&nbsp;=&nbsp;ε/2''K'' to verify the definition of equicontinuity of the sequence.  This proves the following corollary:

* Let {''&fnof;''<sub>''n''</sub>} be a uniformly bounded sequence of real-valued differentiable functions on [''a'',''b''] such that the derivatives {''&fnof;''<sub>''n''</sub>&prime;} are uniformly bounded.  Then there exists a subsequence {''&fnof;''<sub>''n''<sub>''k''</sub></sub>} that converges uniformly on [''a'',''b''].

If, in addition, the sequence of second derivatives is also uniformly bounded, then the derivatives also converge uniformly (up to a subsequence), and so on.  Another generalization holds for [[continuously differentiable function]]s.  Suppose that the functions ''&fnof;''<sub>''n''</sub> are continuously differentiable with derivatives ''&fnof;''<sub>''n''</sub>&prime;.  Suppose that ''&fnof;''<sub>''n''</sub>&prime; are uniformly equicontinuous and uniformly bounded, and that the sequence ''&fnof;''<sub>''n''</sub> is pointwise bounded (or just bounded at a single point).  Then there is a subsequence of the ''&fnof;''<sub>''n''</sub> converging uniformly to a continuously differentiable function.

;Lipschitz and Hölder continuous functions
The argument given above proves slightly more, specifically

* If {''&fnof;''<sub>''n''</sub>} is a uniformly bounded sequence of real valued functions on [''a'',''b''] such that each ''&fnof;'' is [[Lipschitz continuous]] with the same Lipschitz constant ''K'':
::<math>|f_n(x) - f_n(y)| \le K|x-y|</math>
:for all ''x'', ''y''&nbsp;&isin;&nbsp;[''a'',''b''] and all ''&fnof;''<sub>''n''</sub>, then there is a subsequence that converges uniformly on [''a'',''b''].

The limit function is also Lipschitz continuous with the same value ''K'' for the Lipschitz constant.  A slight refinement is

* A set '''F''' of functions ''&fnof;'' on [''a'',&nbsp;''b''] that is uniformly bounded and satisfies a [[Hölder condition]] of order ''α'', 0&nbsp;<&nbsp;''&alpha;''&nbsp;≤&nbsp;1, with a fixed constant&nbsp;''M'',

::<math> |f(x) - f(y)| \le M \, |x - y|^\alpha, \quad x, y \in [a, b]</math>

:is relatively compact in ''C''([''a'',&nbsp;''b'']).  In particular, the unit ball of the [[Hölder condition|Hölder space]]&thinsp; ''C''<sup>&nbsp;0,&nbsp;''&alpha;''</sup>([''a'',&nbsp;''b'']) is compact in ''C''([''a'',&nbsp;''b'']).

This holds more generally for scalar functions on a compact metric space ''X'' satisfying a Hölder condition with respect to the metric on&nbsp;''X''. 

;Euclidean spaces
The Arzelà–Ascoli theorem holds, more generally, if the functions ''&fnof;''<sub>''n''</sub> take values in ''d''-dimensional [[Euclidean space]] '''R'''<sup>''d''</sup>, and the proof is very simple:  just apply the '''R'''-valued version of the Arzelà–Ascoli theorem ''d'' times to extract a subsequence that converges uniformly in the first coordinate, then a sub-subsequence that converges uniformly in the first two coordinates, and so on.  The above examples generalize easily to the case of functions with values in Euclidean space.

== Proof ==
The proof is essentially based on a [[diagonalization argument]].  The simplest case is of real-valued functions on a closed and bounded interval:

* Let {{nowrap|1=''I'' = [''a'', ''b''] &sub; '''R'''}} be a closed and bounded interval.  If '''F''' is an infinite set of functions ƒ&nbsp;:&nbsp;''I''&nbsp;→&nbsp;'''R''' which is uniformly bounded and equicontinuous, then there is a sequence ƒ<sub>''n''</sub> of elements of '''F''' such that ƒ<sub>''n''</sub> converges uniformly on ''I''.

Fix an enumeration {''x''<sub>''i''</sub>}<sub>''i''=1,2,3,...</sub> of [[rational numbers]] in ''I''.  Since '''F''' is uniformly bounded, the set of points {ƒ(''x''<sub>1</sub>)}<sub>ƒ∈'''F'''</sub> is bounded, and hence by the [[Bolzano-Weierstrass theorem]], there is a sequence {ƒ<sub>''n''<sub>1</sub></sub>} of distinct functions in '''F''' such that {ƒ<sub>''n''<sub>1</sub></sub>(''x''<sub>1</sub>)} converges.  Repeating the same argument for the sequence of points {ƒ<sub>''n''<sub>1</sub></sub>(''x''<sub>2</sub>)}, there is a subsequence {ƒ<sub>''n''<sub>2</sub></sub>} of {ƒ<sub>''n''<sub>1</sub></sub>} such that {ƒ<sub>''n''<sub>2</sub></sub>(''x''<sub>2</sub>)} converges.

By induction this process can be continued forever, and so there is a chain of subsequences 

:<math>\{f_{n_1}\}\supseteq \{f_{n_2}\}\supseteq \cdots</math>

such that, for each ''k'' = 1, 2, 3, …, the subsequence {ƒ<sub>''n''<sub>''k''</sub></sub>} converges at ''x''<sub>1</sub>,...,''x''<sub>''k''</sub>.  Now form the diagonal subsequence {''&fnof;<sub>''</sub>} whose ''m''th term ''&fnof;''<sub>''m''</sub> is the ''m''th term in the ''m''th subsequence {ƒ<sub>''n''<sub>''m''</sub></sub>}. By construction, ƒ<sub>''m''</sub> converges at every [[rational point]] of ''I''.

Therefore, given any ''&epsilon;''&nbsp;>&nbsp;0 and rational ''x''<sub>''k''</sub> in ''I'', there is an integer {{nowrap|1=''N'' = ''N''(''&epsilon;'',''x''<sub>''k''</sub>)}} such that

:<math>|f_n(x_k) - f_m(x_k)| < \varepsilon/3,\quad n,m \ge N.\,</math>

Since the family '''F''' is equicontinuous, for this fixed ''&epsilon;'' and for every ''x'' in ''I'', there is an open interval ''U<sub>x</sub>'' containing ''x'' such that

:<math>|f(s)-f(t)| < \varepsilon/3\,</math>

for all ƒ&nbsp;∈&nbsp;'''F''' and all ''s'',&nbsp;''t'' in ''I'' such that ''s'',&nbsp;''t''&nbsp;∈&nbsp;''U<sub>x</sub>''.

The collection of intervals ''U<sub>x</sub>'', ''x''&nbsp;∈ ''I'',  forms an [[open cover]] of ''I''.  Since ''I''&thinsp; is [[compact set|compact]], this covering admits a finite subcover ''U''<sub>1</sub>,&nbsp;...,&nbsp;''U''<sub>''J''</sub>.  There exists an integer ''K'' such that each open interval ''U<sub>j</sub>'', 1&nbsp;≤&nbsp;''j''&nbsp;≤&nbsp;''J'', contains a rational ''x''<sub>''k''</sub> with 1&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;''K''.  Finally, for any ''t''&nbsp;∈&nbsp;''I'', there are ''j'' and ''k'' so that ''t'' and ''x<sub>k</sub>'' belong to the same interval ''U''<sub>''j''</sub>.  For this choice of ''k'',

:<math>
\begin{align}
|f_n(t)-f_m(t)| & {} \le |f_n(t) - f_n(x_k)| + |f_n(x_k) - f_m(x_k)| + |f_m(x_k) - f_m(t)| \\
& {} < \varepsilon/3 + \varepsilon/3 +\varepsilon/3
\end{align}
</math>

for all ''n'', ''m'' > ''N'' = max{''N''(''&epsilon;'',''x''<sub>1</sub>),&nbsp;...,&nbsp;''N''(''&epsilon;'',''x''<sub>''K''</sub>)}.  Consequently, the sequence {ƒ<sub>''n''</sub>} is [[uniformly Cauchy]], and therefore converges to a continuous function, as claimed.  This completes the proof.

==Generalizations==

=== Compact metric spaces and compact Hausdorff spaces ===

The definitions of boundedness and equicontinuity can be generalized to the setting of arbitrary compact [[metric space]]s and, more generally still, [[compact set|compact]] [[Hausdorff space]]s.  Let ''X'' be a compact Hausdorff space, and let ''C''(''X'') be the space of real-valued [[continuous function]]s on ''X''. A subset&thinsp; {{nowrap|'''F''' &sub; ''C''(''X'')}}&thinsp; is said to be ''equicontinuous'' if for every ''x''&nbsp;∈ ''X'' and every ''ε''&nbsp;>&nbsp;0, ''x'' has a neighborhood ''U''<sub>''x''</sub> such that

:<math>|f(y) - f(x)| < \varepsilon\,</math>

for all ''y''&nbsp;∈&nbsp;''U''<sub>''x''</sub> and ''&fnof;''&nbsp;∈&nbsp;''F''.

A set&thinsp; {{nowrap|'''F''' &sub; ''C''(''X'','''R''')}}&thinsp; is said to be ''pointwise bounded'' if for every ''x''&nbsp;∈ ''X'',

:<math>\sup \{ | f(x) | : f \in \mathbf{F} \} < \infty.</math>

A version of this holds also in the space ''C''(''X'') of real-valued continuous functions on a [[compact set|compact]] [[Hausdorff space]] ''X'' {{harv|Dunford|Schwartz|1958|loc=§IV.6.7}}:

:Let ''X'' be a compact Hausdorff space. Then a subset '''F''' of ''C''(''X'') is [[relatively compact]] in the topology induced by the [[uniform norm]] if and only if it is [[equicontinuous]] and pointwise bounded.

The Arzelà–Ascoli theorem is thus a fundamental result in the study of the algebra of [[continuous functions on a compact Hausdorff space]].

Various generalizations of the above quoted result are possible.  For instance, the functions can assume values in a metric space or (Hausdorff) [[topological vector space]] with only minimal changes to the statement (see, for instance, {{harvtxt|Kelley|Namioka|1982|loc=§8}}, {{harvtxt|Kelley|1991|loc=Chapter 7}}):

:Let ''X'' be a compact Hausdorff space and <math>Y </math> a metric space. Then a subset '''F''' of ''C''(''X'',''Y'') is compact in the [[compact-open topology]] if and only if it is [[equicontinuous]], pointwise [[relatively compact]] and closed.

Here pointwise relatively compact means that for each ''x''&nbsp;∈&nbsp;''X'', the set {{nowrap|1='''F'''<sub>''x''</sub> = { ''&fnof;''(''x'') : ''&fnof;'' &isin; '''F'''}}} is relatively compact in ''Y''.

The proof given can be generalized in a way that does not rely on the [[separable metric space|separability]] of the domain.  On a [[compact Hausdorff space]] ''X'', for instance, the equicontinuity is used to extract, for each ε&nbsp;=&nbsp;1/''n'', a finite open covering of ''X'' such that the [[oscillation (mathematics)|oscillation]] of any function in the family is less than ε on each open set in the cover.  The role of the rationals can then be played by a set of points drawn from each open set in each of the countably many covers obtained in this way, and the main part of the proof proceeds exactly as above.

==Necessity==
Whereas most formulations of the Arzelà–Ascoli theorem assert sufficient conditions for a family of functions to be (relatively) compact in some topology, these conditions are typically also necessary.  For instance, if a set '''F''' is compact in ''C''(''X''), the Banach space of real-valued continuous functions on a compact Hausdorff space with respect to its uniform norm, then it is bounded in the uniform norm on ''C''(''X'') and in particular is pointwise bounded. Let ''N''(ε,''U'') be the set of all functions in '''F''' whose [[oscillation (mathematics)|oscillation]] over an open subset ''U''&sub;''X'' is less than ε:
:<math>N(\varepsilon, U) = \{f | \operatorname{osc}_U f < \varepsilon\}.</math>
For a fixed ''x''&isin;''X'' and ε, the sets ''N''(ε,''U'') form an open covering of '''F''' as ''U'' varies over all open neighborhoods of ''x''.  Choosing a finite subcover then gives equicontinuity.

== Examples ==

* To every function ''g'' that is [[Lp space#Lp spaces|''p''-integrable]] on [0,&nbsp;1], 1&nbsp;< ''p''&nbsp;≤ ∞, associate the function ''G'' defined on [0,&nbsp;1] by

::<math>G(x) = \int_0^x g(t) \, \mathrm{d}t.</math>

:Let ''F'' be the set of functions ''G'' corresponding to functions ''g'' in the unit ball of the space [[Lp space|''L<sup>p</sup>''([0,&nbsp;1])]]. If ''q'' is the Hölder conjugate of ''p'', defined by 1/''p''&nbsp;+ 1/''q''&nbsp;= 1, then [[Hölder inequality|Hölder's inequality]] implies that all functions in ''F'' satisfy a Hölder condition with ''&alpha;''&nbsp;= 1/''q'' and constant ''M''&nbsp;=&nbsp;1.

:It follows that ''F'' is compact in ''C''([0,&nbsp;1]). This means that the correspondence ''g''&nbsp;&rarr; ''G'' defines a [[Compact operator|compact]] [[Linear map|linear operator]] ''T''&thinsp; between the [[Banach space]]s ''L<sup>p</sup>''([0,&nbsp;1]) and ''C''([0,&nbsp;1]).  Composing with the injection of ''C''([0,&nbsp;1]) into ''L<sup>p</sup>''([0,&nbsp;1]), one sees that ''T'' acts compactly from ''L<sup>p</sup>''([0,&nbsp;1]) to itself.  The case ''p''&nbsp;= 2 can be seen as a simple instance of the fact that the injection from the [[Sobolev space]] <math>H^1_0(\Omega)</math> into ''L''<sup>2</sup>(''&Omega;''), for ''&Omega;'' a bounded open set in '''R'''<sup>''d''</sup>, is compact.

*When ''T'' is a compact linear operator from a Banach space ''X''&thinsp; to a Banach space ''Y'', its [[Dual space#Transpose of a continuous linear map|transpose]] ''T''<sup>∗</sup> is compact from the (continuous) [[Dual space#Continuous dual space|dual]] ''Y''<sup>∗</sup> to ''X''<sup>∗</sup>. This can be checked by the Arzelà&ndash;Ascoli theorem.

:Indeed, the image ''T''(''B'') of the closed unit ball ''B'' of ''X'' is contained in a compact subset ''K'' of ''Y''. The unit ball ''B''<sup>&lowast;</sup> of ''Y''<sup>&lowast;</sup> defines, by restricting from ''Y'' to ''K'', a set ''F''&thinsp; of (linear) continuous functions on ''K''&thinsp; that is bounded and equicontinuous.  By Arzelà&ndash;Ascoli, for every sequence {''y''<sup>&lowast;</sup><sub>''n''</sub>} in ''B''<sup>&lowast;</sup>, there is a subsequence that converges uniformly on ''K'', and this implies that the image <math>T^*(y^*_{n_k})</math>&thinsp;  of that subsequence is Cauchy in&nbsp;''X''<sup>&lowast;</sup>.

*When  ''&fnof;'' is [[Holomorphic function|holomorphic]] in an open disk ''D<sub>1</sub>''&nbsp;= ''B''(''z''<sub>0</sub>,&nbsp;''r''), with modulus bounded by ''M'', then (for example by [[Cauchy's integral formula|Cauchy's formula]]) its derivative ''&fnof;''&prime; has modulus bounded by 4''M''&nbsp;⁄&nbsp;''r'' in the smaller disk ''D<sub>2</sub>''&nbsp;= ''B''(''z''<sub>0</sub>,&nbsp;''r''&nbsp;⁄&nbsp;2). If a family of holomorphic functions on ''D<sub>1</sub>'' is bounded by ''M'' on ''D<sub>1</sub>'', it follows that the family ''F'' of restrictions to ''D<sub>2</sub>'' is equicontinuous on ''D<sub>2</sub>''.  Therefore, a sequence converging uniformly on ''D''<sub>2</sub> can be extracted.  This is a first step in the direction of  [[Montel's theorem]].

== See also ==
*[[Helly's selection theorem]]
*[[Fréchet-Kolmogorov theorem]]

== References ==
* {{citation|first=Cesare|last=Arzelà|authorlink=Cesare Arzelà|title=Sulle funzioni di linee|journal=Mem. Accad. Sci. Ist. Bologna Cl. Sci. Fis. Mat.|volume=5|issue=5|pages=55–74|year=1895}}.
* {{citation|first=Cesare|last=Arzelà|authorlink=Cesare Arzelà|title=Un'osservazione intorno alle serie di funzioni|journal=Rend. Dell' Accad. R. Delle Sci. Dell'Istituto di Bologna|pages=142–159|year=1882–1883}}.
* {{citation|first=G.|last=Ascoli|authorlink=Giulio Ascoli|title=Le curve limiti di una varietà data di curve|journal=Atti della R. Accad. Dei Lincei Memorie della Cl. Sci. Fis. Mat. Nat.|volume=18|issue=3|pages=521–586|year=1883–1884}}.
* {{Citation | last1=Bourbaki | first1=Nicolas | author1-link=Nicolas Bourbaki | title=General topology. Chapters 5&ndash;10 | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Elements of Mathematics | isbn=978-3-540-64563-4 | mr=1726872 | year=1998}}.
* {{citation|first=Jean|last=Dieudonné|authorlink=Jean Dieudonné|title=Foundations of modern analysis|isbn=978-0-12-215507-9|publisher=Academic Press|year=1988}}
* {{citation|first1=Nelson|last1=Dunford|first2=Jacob T.|last2=Schwartz|title=Linear operators, volume 1|publisher=Wiley-Interscience|year=1958}}.
* {{citation|first=Maurice|last=Fréchet|authorlink=Maurice Fréchet|title=Sur quelques points du calcul fonctionnel|journal=Rend. Circ. Mat. Palermo|volume=22|pages=1–74|year=1906|doi=10.1007/BF03018603}}.
* [http://www.encyclopediaofmath.org/index.php/Arzel%C3%A0-Ascoli_theorem ''Arzelà-Ascoli theorem'' at Encyclopaedia of Mathematics]
*{{citation|first1=J. L.|last1=Kelley|title=General topology|isbn=978-0-387-90125-1|year=1991|publisher=Springer-Verlag}}
*{{citation|first1=J. L.|last1=Kelley|first2=I.|last2=Namioka|title=Linear Topological Spaces|publisher=Springer-Verlag|year=1982|isbn=978-0-387-90169-5}}
* {{citation|first=Walter|last=Rudin|authorlink=Walter Rudin|title=Principles of mathematical analysis|isbn=978-0-07-054235-8|year=1976|publisher=McGraw-Hill}}

{{PlanetMath attribution|id=2961|title=Ascoli–Arzelà theorem}}

{{DEFAULTSORT:Arzela-Ascoli theorem}}
[[Category:Continuous mappings]]
[[Category:Topology of function spaces]]
[[Category:Articles containing proofs]]
[[Category:Compactness theorems]]
[[Category:Theorems in functional analysis]]