Helly's selection theorem

In mathematics, Helly's selection theorem (also called the Helly selection principle) states that a uniformly bounded sequence of monotone real functions admits a convergent subsequence. In other words, it is a sequential compactness theorem for the space of uniformly bounded monotone functions. It is named for the Austrian mathematician Eduard Helly. A more general version of the theorem asserts compactness of the space BVloc of functions locally of bounded total variation that are uniformly bounded at a point.

The theorem has applications throughout mathematical analysis. In probability theory, the result implies compactness of a tight family of measures.

Statement of the theorem

Let (fn)n ∈ N be a sequence of increasing functions mapping a real interval I into the real line R, and suppose that it is uniformly bounded: there are a,b ∈ R such that a ≤ fn ≤ b for every n ∈ N. Then the sequence (fn)n ∈ N admits a pointwise convergent subsequence.

Proof

The proof requires the basic facts about monotonic functions: An increasing function f on an interval I has at most countably many points of discontinuity.

Step 1. Inductive Construction of a subsequence converging at discontinuities and rationals (diagonal process).

Let A n = { x ∈ I ; f n ( y ) ↛ f n ( x ) as y → x } {\displaystyle A_{n}=\{x\in I;f_{n}(y)\not \rightarrow f_{n}(x){\text{ as }}y\to x\}} be the set of discontinuities of f n {\displaystyle f_{n}}; each of these sets are countable by the above basic fact. The set A := ( ⋃ n ∈ N A n ) ∪ ( I ∩ Q ) {\displaystyle A:=\left(\textstyle \bigcup _{n\in \mathbb {N} }A_{n}\right)\cup (I\cap \mathbb {Q} )} is countable, and it can be denoted as { a n } n = 1 ∞ {\displaystyle \{a_{n}\}_{n=1}^{\infty }}.

By the uniform boundedness of { f n } n = 1 ∞ {\displaystyle \{f_{n}\}_{n=1}^{\infty }} and the Bolzano–Weierstrass theorem, there is a subsequence { f n ( 1 ) } n = 1 ∞ {\displaystyle \{f_{n}^{(1)}\}_{n=1}^{\infty }} such that { f n ( 1 ) ( a 1 ) } n = 1 ∞ {\displaystyle \{f_{n}^{(1)}(a_{1})\}_{n=1}^{\infty }} converges. Suppose { f n ( k ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k)}\}_{n=1}^{\infty }} has been chosen such that { f n ( k ) ( a i ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k)}(a_{i})\}_{n=1}^{\infty }} converges for i = 1 , … , k {\displaystyle i=1,\dots ,k}, then by uniform boundedness and Bolzano–Weierstrass, there is a subsequence { f n ( k + 1 ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k+1)}\}_{n=1}^{\infty }} of { f n ( k ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k)}\}_{n=1}^{\infty }} such that { f n ( k ) ( a k + 1 ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k)}(a_{k+1})\}_{n=1}^{\infty }} converges, thus { f n ( k + 1 ) ( a i ) } n = 1 ∞ {\displaystyle \{f_{n}^{(k+1)}(a_{i})\}_{n=1}^{\infty }} converges for i = 1 , … , k + 1 {\displaystyle i=1,\dots ,k+1}.

Let g k = f k ( k ) {\displaystyle g_{k}=f_{k}^{(k)}}, then { g k } k = 1 ∞ {\displaystyle \{g_{k}\}_{k=1}^{\infty }} is a subsequence of { f n } n = 1 ∞ {\displaystyle \{f_{n}\}_{n=1}^{\infty }} that converges pointwise everywhere in A {\displaystyle A}.

Step 2. g k converges in I except possibly in an at most countable set.

Let h k ( x ) = sup a ≤ x , a ∈ A g k ( a ) {\displaystyle h_{k}(x)=\sup _{a\leq x,a\in A}g_{k}(a)}, then, hk(a)=gk(a) for a∈A, hk is increasing, let h ( x ) = lim sup k → ∞ h k ( x ) {\displaystyle h(x)=\limsup \limits _{k\rightarrow \infty }h_{k}(x)}, then h is increasing, since supremes and limits of increasing functions are increasing, and h ( a ) = lim k → ∞ g k ( a ) {\displaystyle h(a)=\lim \limits _{k\rightarrow \infty }g_{k}(a)} for a∈ A by Step 1. Moreover, h has at most countably many discontinuities.

We will show that gk converges at all continuities of h. Let x be a continuity of h, q,r∈ A, q<x<r, then g k ( q ) − h ( r ) ≤ g k ( x ) − h ( x ) ≤ g k ( r ) − h ( q ) {\displaystyle g_{k}(q)-h(r)\leq g_{k}(x)-h(x)\leq g_{k}(r)-h(q)},hence

lim sup k → ∞ ( g k ( x ) − h ( x ) ) ≤ lim sup k → ∞ ( g k ( r ) − h ( q ) ) = h ( r ) − h ( q ) {\displaystyle \limsup \limits _{k\rightarrow \infty }{\bigl (}g_{k}(x)-h(x){\bigr )}\leq \limsup \limits _{k\rightarrow \infty }{\bigl (}g_{k}(r)-h(q){\bigr )}=h(r)-h(q)}

h ( q ) − h ( r ) = lim inf k → ∞ ( g k ( q ) − h ( r ) ) ≤ lim inf k → ∞ ( g k ( x ) − h ( x ) ) {\displaystyle h(q)-h(r)=\liminf \limits _{k\rightarrow \infty }{\bigl (}g_{k}(q)-h(r){\bigr )}\leq \liminf \limits _{k\rightarrow \infty }{\bigl (}g_{k}(x)-h(x){\bigr )}}

Thus,

h ( q ) − h ( r ) ≤ lim inf k → ∞ ( g k ( x ) − h ( x ) ) ≤ lim sup k → ∞ ( g k ( x ) − h ( x ) ) ≤ h ( r ) − h ( q ) {\displaystyle h(q)-h(r)\leq \liminf \limits _{k\rightarrow \infty }{\bigl (}g_{k}(x)-h(x){\bigr )}\leq \limsup \limits _{k\rightarrow \infty }{\bigl (}g_{k}(x)-h(x){\bigr )}\leq h(r)-h(q)}

Since h is continuous at x, by taking the limits q ↑ x , r ↓ x {\displaystyle q\uparrow x,r\downarrow x}, we have h ( q ) , h ( r ) → h ( x ) {\displaystyle h(q),h(r)\rightarrow h(x)}, thus lim k → ∞ g k ( x ) = h ( x ) {\displaystyle \lim \limits _{k\rightarrow \infty }g_{k}(x)=h(x)}

Step 3. Choosing a subsequence of g k that converges pointwise in I

This can be done with a diagonal process similar to Step 1.

With the above steps we have constructed a subsequence of (fn)n ∈ N that converges pointwise in I.

Generalisation to BV loc

Let U be an open subset of the real line and let fn : U → R, n ∈ N, be a sequence of functions. Suppose that (fn) has uniformly bounded total variation on any W that is compactly embedded in U. That is, for all sets W ⊆ U with compact closure W̄ ⊆ U,

sup n ∈ N ( ‖ f n ‖ L 1 ( W ) + ‖ d f n d t ‖ L 1 ( W ) ) < + ∞ , {\displaystyle \sup _{n\in \mathbf {N} }\left(\|f_{n}\|_{L^{1}(W)}+\|{\frac {\mathrm {d} f_{n}}{\mathrm {d} t}}\|_{L^{1}(W)}\right)<+\infty ,}

where the derivative is taken in the sense of tempered distributions.

Then, there exists a subsequence fnk, k ∈ N, of fn and a function f : U → R, locally of bounded variation, such that

fnk converges to f pointwise almost everywhere;
and fnk converges to f locally in L1 (see locally integrable function), i.e., for all W compactly embedded in U,

lim k → ∞ ∫ W | f n k ( x ) − f ( x ) | d x = 0 ; {\displaystyle \lim _{k\to \infty }\int _{W}{\big |}f_{n_{k}}(x)-f(x){\big |}\,\mathrm {d} x=0;}

and, for W compactly embedded in U,

‖ d f d t ‖ L 1 ( W ) ≤ lim inf k → ∞ ‖ d f n k d t ‖ L 1 ( W ) . {\displaystyle \left\|{\frac {\mathrm {d} f}{\mathrm {d} t}}\right\|_{L^{1}(W)}\leq \liminf _{k\to \infty }\left\|{\frac {\mathrm {d} f_{n_{k}}}{\mathrm {d} t}}\right\|_{L^{1}(W)}.}

Further generalizations

There are many generalizations and refinements of Helly's theorem. The following theorem, for BV functions taking values in Banach spaces, is due to Barbu and Precupanu:

Let X be a reflexive, separable Hilbert space and let E be a closed, convex subset of X. Let Δ : X → [0, +∞) be positive-definite and homogeneous of degree one. Suppose that zn is a uniformly bounded sequence in BV([0, T]; X) with zn(t) ∈ E for all n ∈ N and t ∈ [0, T]. Then there exists a subsequence znk and functions δ, z ∈ BV([0, T]; X) such that

for all t ∈ [0, T],

∫ [ 0 , t ) Δ ( d z n k ) → δ ( t ) ; {\displaystyle \int _{[0,t)}\Delta (\mathrm {d} z_{n_{k}})\to \delta (t);}

and, for all t ∈ [0, T],

z n k ( t ) ⇀ z ( t ) ∈ E ; {\displaystyle z_{n_{k}}(t)\rightharpoonup z(t)\in E;}

and, for all 0 ≤ s < t ≤ T,

∫ [ s , t ) Δ ( d z ) ≤ δ ( t ) − δ ( s ) . {\displaystyle \int _{[s,t)}\Delta (\mathrm {d} z)\leq \delta (t)-\delta (s).}