7.4 Normed Linear Spaces and Spaces of Continuous Functions
Vector spaces with a length: $\ell^p$, $C[a,b]$ with $\|\cdot\|_\infty$ (complete) and $\|\cdot\|_1$ (not complete), why all norms on $\mathbb{R}^n$ are equivalent, bounded operators and their norms, and the two great theorems about $C(K)$ — Arzelà–Ascoli and Stone–Weierstrass.
In Chapter 5 we measured the distance between two functions by $\sup_x|f(x)-g(x)|$ and discovered that uniform convergence is just convergence in that distance. This is the starting point of functional analysis: a function is a point in a vector space, and the size of the point is measured by a norm. Once functions are points, the geometric language of Chapter 7 applies to them — open balls, Cauchy sequences, completeness, compactness — and familiar theorems become statements about these spaces: "a uniform limit of continuous functions is continuous" says that $C[a,b]$ is a closed subset of the bounded functions; the Weierstrass approximation theorem says that the polynomials are dense in $C[a,b]$.
The surprise is how different infinite-dimensional spaces are from $\mathbb{R}^n$. On $\mathbb{R}^n$ all norms are equivalent, every linear map is continuous, and closed bounded sets are compact. In $C[0,1]$ or $\ell^2$ every one of these statements fails, and the failures are exactly what CSIR NET tests: "is $(C[0,1],\|\cdot\|_1)$ complete?", "are these two norms equivalent?", "find the norm of this operator", "is the closed unit ball compact?", "which of these families has a uniformly convergent subsequence?". This section proves the positive results in full and builds the standard counterexamples alongside them.
Norms, Normed Spaces and Banach Spaces
Throughout, $\mathbb{F}$ denotes $\mathbb{R}$ or $\mathbb{C}$, and all vector spaces are over $\mathbb{F}$.
A norm on a vector space $X$ is a function $\|\cdot\|:X\to[0,\infty)$ such that for all $x,y\in X$ and $\lambda\in\mathbb{F}$:
A function satisfying the last two properties (but possibly $\|x\|=0$ for some $x\ne0$) is a seminorm. A normed linear space $(X,\|\cdot\|)$ is a vector space with a norm; it is a metric space with the induced metric $d(x,y)=\|x-y\|$. A normed space that is complete in this metric is a Banach space.
- $\big|\|x\|-\|y\|\big|\le\|x-y\|$; so the norm is a $1$-Lipschitz, hence continuous, function on $X$.
- Addition $X\times X\to X$ and scalar multiplication $\mathbb{F}\times X\to X$ are continuous: if $x_n\to x$, $y_n\to y$, $\lambda_n\to\lambda$, then $x_n+y_n\to x+y$ and $\lambda_nx_n\to\lambda x$.
- The induced metric is translation invariant, $d(x+z,y+z)=d(x,y)$, and homogeneous, $d(\lambda x,\lambda y)=|\lambda|\,d(x,y)$. Conversely, a metric on a vector space with these two properties is induced by the norm $\|x\|=d(x,0)$.
- Every ball is convex, $B(x,r)=x+rB(0,1)$, and if $X\ne\{0\}$ the closure of the open ball $B(x,r)$ is the closed ball $\{y:\|y-x\|\le r\}$. A metric induced by a norm on $X\ne\{0\}$ is unbounded.
Proof. (1) $\|x\|=\|(x-y)+y\|\le\|x-y\|+\|y\|$, so $\|x\|-\|y\|\le\|x-y\|$; exchange $x$ and $y$. (2) $\|(x_n+y_n)-(x+y)\|$ is at most $\|x_n-x\|+\|y_n-y\|\to0$, and $\|\lambda_nx_n-\lambda x\|$ is at most $|\lambda_n|\,\|x_n-x\|+|\lambda_n-\lambda|\,\|x\|\to0$, as $(\lambda_n)$ is bounded. (3) The two identities follow from $\|(x+z)-(y+z)\|=\|x-y\|$ and $\|\lambda x-\lambda y\|=|\lambda|\|x-y\|$. Conversely, given such a $d$, the function $\|x\|=d(x,0)$ is definite, $\|\lambda x\|=d(\lambda x,\lambda0)=|\lambda|\|x\|$, and $\|x+y\|=d(x+y,0)$ is at most $d(x+y,y)+d(y,0)=d(x,0)+d(y,0)$, while $d(x,y)=d(x-y,0)=\|x-y\|$. (4) If $\|y_1-x\|,\|y_2-x\|\lt r$ and $0\le t\le1$ then $\|(1-t)y_1+ty_2-x\|$ is at most $(1-t)\|y_1-x\|+t\|y_2-x\|\lt r$. If $\|y-x\|=r$, the points $x+(1-\tfrac1n)(y-x)$ lie in $B(x,r)$ and converge to $y$; the closed ball is closed by (1). Finally $d(tx,0)=|t|\,\|x\|\to\infty$ for $x\ne0$. ∎
Part (4) is often the quickest test: the discrete metric, and $\frac{|x-y|}{1+|x-y|}$ on $\mathbb{R}$, are bounded metrics, so they come from no norm. And in the discrete metric the closure of the open ball $B(x,1)=\{x\}$ is $\{x\}$, not the closed ball $X$ — a phenomenon that never happens in a normed space.
Proof. (a) $\|f\|_\infty$ is finite because a continuous function on a compact set is bounded (§7.2), and the norm axioms are those of the sup norm (§5.1). Let $(f_n)$ be Cauchy: for $\varepsilon\gt0$ there is $N$ with $|f_n(x)-f_m(x)|\le\|f_n-f_m\|_\infty\lt\varepsilon$ for all $m,n\ge N$ and all $x$. So $(f_n)$ is uniformly Cauchy; by the Cauchy criterion (§5.1) it converges uniformly to some $f$, and $f$ is continuous because uniform limits of continuous functions are continuous (§5.2; the $\varepsilon/3$ proof works verbatim on a metric space). Uniform convergence is $\|f_n-f\|_\infty\to0$.
(b) Let $x^{(k)}=(x^{(k)}_n)_n$ be Cauchy in $\ell^p$. For each fixed $n$, $|x^{(k)}_n-x^{(m)}_n|\le\|x^{(k)}-x^{(m)}\|_p$, so the $n$-th coordinates form a Cauchy sequence in $\mathbb{F}$ with a limit $x_n$. Given $\varepsilon\gt0$ choose $N$ with $\|x^{(k)}-x^{(m)}\|_p\lt\varepsilon$ for $k,m\ge N$. For every finite $M$, $$\sum_{n=1}^M|x^{(k)}_n-x^{(m)}_n|^p\lt\varepsilon^p\quad(k,m\ge N).$$ Let $m\to\infty$ (a finite sum of continuous functions): $\sum_{n\le M}|x^{(k)}_n-x_n|^p\le\varepsilon^p$; now let $M\to\infty$: $\|x^{(k)}-x\|_p\le\varepsilon$ for $k\ge N$. In particular $x^{(N)}-x\in\ell^p$, so $x=x^{(N)}-(x^{(N)}-x)\in\ell^p$ (Minkowski), and $x^{(k)}\to x$ in $\ell^p$. The same argument with $\sup_{n\le M}$ in place of the sum handles $\ell^\infty$. Finally, if $x^{(k)}\in c_0$ and $x^{(k)}\to x$ in $\ell^\infty$, then given $\varepsilon$ fix $k$ with $\|x^{(k)}-x\|_\infty\lt\varepsilon$; since $x^{(k)}_n\to0$, $|x_n|\lt2\varepsilon$ for large $n$. So $x\in c_0$: $c_0$ is closed, hence complete. ∎
Proof. ($\Rightarrow$) The partial sums $s_N=\sum_{n\le N}x_n$ satisfy $\|s_M-s_N\|\le\sum_{N\lt n\le M}\|x_n\|$, which is small for large $N\lt M$ because $\sum\|x_n\|$ converges. So $(s_N)$ is Cauchy and converges. The inequality follows from $\|s_N\|\le\sum_{n\le N}\|x_n\|$ and continuity of the norm.
($\Leftarrow$) Let $(y_n)$ be Cauchy. Choose $n_1\lt n_2\lt\cdots$ with $\|y_m-y_n\|\lt2^{-k}$ for $m,n\ge n_k$. The series $y_{n_1}+\sum_{k\ge1}(y_{n_{k+1}}-y_{n_k})$ is absolutely convergent ($\sum2^{-k}\lt\infty$), so it converges; its partial sums are $y_{n_{k+1}}$. Thus $(y_n)$ has a convergent subsequence, and a Cauchy sequence with a convergent subsequence converges to the same limit (§7.1). ∎
This criterion is the natural tool for $L^1$-type spaces (it is how the completeness of $L^1$ is proved, §4.5), and it gives the Weierstrass M-test a one-line proof: in the Banach space of bounded functions on $D$ with the sup norm, $\sum\|u_n\|_\infty\lt\infty$ implies that $\sum u_n$ converges in that norm, i.e. uniformly.
Proof. Let $f_n(x)=\min\big(1,\max(0,n(x-\tfrac12))\big)$: $0$ on $[0,\tfrac12]$, rising linearly to $1$ on $[\tfrac12,\tfrac12+\tfrac1n]$, then $1$. For $m\gt n$ the functions $f_n\le f_m$ differ only on $[\tfrac12,\tfrac12+\tfrac1n]$, and $$\|f_m-f_n\|_1=\tfrac12\Big(\tfrac1n-\tfrac1m\Big)\lt\tfrac1{2n},$$ so $(f_n)$ is Cauchy. Suppose $\|f_n-f\|_1\to0$ for some $f\in C[0,1]$. Then $\int_0^{1/2}|f|=\int_0^{1/2}|f_n-f|\le\|f_n-f\|_1\to0$, so $\int_0^{1/2}|f|=0$ and $f=0$ on $[0,\tfrac12]$. For $\delta\gt0$ and $n\gt1/\delta$, $f_n=1$ on $[\tfrac12+\delta,1]$, so $\int_{1/2+\delta}^1|1-f|\le\|f_n-f\|_1\to0$, and $f=1$ on $[\tfrac12+\delta,1]$. As $\delta$ is arbitrary, $f=1$ on $(\tfrac12,1]$, and $f$ is discontinuous at $\tfrac12$ — a contradiction. ∎
The same sequence is Cauchy in $\|\cdot\|_2$ (with $\|f_m-f_n\|_2^2\le\tfrac1n$), so $(C[0,1],\|\cdot\|_2)$ is not complete either. But it is not Cauchy in $\|\cdot\|_\infty$: $\|f_{2n}-f_n\|_\infty=\tfrac12$. One vector space, three norms, and completeness depends on the norm.
Equivalent Norms; Finite-Dimensional Spaces
Proof. (1)$\Rightarrow$(2): $B'(x,cr)\subseteq B(x,r)$ and $B(x,r/C)\subseteq B'(x,r)$, where $B'$ denotes $\|\cdot\|'$-balls; so every $\|\cdot\|$-open set is $\|\cdot\|'$-open and conversely. (2)$\Rightarrow$(3): convergence is defined by open sets ($x_n\to x$ iff every open set containing $x$ contains $x_n$ for large $n$). (3)$\Rightarrow$(4) is a special case. (4)$\Rightarrow$(1): suppose there is no $C$ with $\|x\|'\le C\|x\|$. Then for each $n$ there is $x_n$ with $\|x_n\|'\gt n\|x_n\|$; put $y_n=x_n/(\sqrt n\,\|x_n\|)$ (note $x_n\ne0$). Then $\|y_n\|=1/\sqrt n\to0$ but $\|y_n\|'\gt\sqrt n\to\infty$, contradicting (4). The lower bound is symmetric. The final statements follow because the inequalities in (1) transfer Cauchy sequences and bounded sets, and compactness depends only on convergent sequences. ∎
Proof. Fix a basis $e_1,\dots,e_n$ and write $x=\sum a_ie_i$. Then $\|x\|_*=\sum_i|a_i|$ is a norm on $X$. Since equivalence of norms is an equivalence relation (compose the inequalities), it suffices to show that an arbitrary norm $\|\cdot\|$ is equivalent to $\|\cdot\|_*$.
Upper bound. $\|x\|\le\sum|a_i|\,\|e_i\|\le M\|x\|_*$ with $M=\max_i\|e_i\|$.
Lower bound. Consider $g(a)=\big\|\sum a_ie_i\big\|$ on $\mathbb{F}^n$ (with the Euclidean metric, $\mathbb{F}^n=\mathbb{R}^n$ or $\mathbb{C}^n\cong\mathbb{R}^{2n}$). By the upper bound and Theorem 7.32(1), $|g(a)-g(b)|\le M\sum|a_i-b_i|$, so $g$ is continuous. The set $S=\{a:\sum|a_i|=1\}$ is closed and bounded in $\mathbb{F}^n$, hence compact (Heine–Borel, §7.2). So $g$ attains a minimum $m$ on $S$ (extreme value theorem, §7.2), and $m\gt0$ because $g(a)=0$ would mean $\sum a_ie_i=0$ with $a\ne0$, contradicting linear independence. For $x\ne0$, $a/\|x\|_*\in S$, so $\|x\|=\|x\|_*\,g(a/\|x\|_*)\ge m\|x\|_*$. ∎
- $X$ is complete (a Banach space).
- Every finite-dimensional subspace of any normed space is closed.
- (Heine–Borel) A subset of $X$ is compact iff it is closed and bounded.
- Every linear map $T$ from $X$ to any normed space $Y$ is continuous (indeed Lipschitz).
Proof. By Theorem 7.37 we may use $\|x\|_*=\sum|a_i|$ for the norm of $X$. (1) If $(x^{(k)})$ is Cauchy, each coordinate sequence $(a^{(k)}_i)_k$ is Cauchy in $\mathbb{F}$ (as $|a_i|\le\|x\|_*$), with limit $a_i$; then $x=\sum a_ie_i$ satisfies $\|x^{(k)}-x\|_*=\sum_i|a^{(k)}_i-a_i|\to0$. (2) A finite-dimensional subspace $Y$ of a normed space $Z$ is complete in the restricted norm by (1), and a complete subset of a metric space is closed. (3) The coordinate map $x\mapsto(a_1,\dots,a_n)$ is a bijection $X\to\mathbb{F}^n$ which, by Theorem 7.37, distorts distances by at most constant factors in both directions; so it preserves closedness, boundedness and compactness, and Heine–Borel in $\mathbb{F}^n$ applies. (4) $\|Tx\|=\|\sum a_iTe_i\|\le\big(\max_i\|Te_i\|\big)\|x\|_*$; apply Theorem 7.39 below. ∎
In infinite dimensions the theorem fails completely: Example 3(b) gives three pairwise non-equivalent norms on $C[0,1]$, and on any infinite-dimensional space one can construct a norm not equivalent to a given one. Correspondingly, Theorem 7.38(2)–(4) all fail: $c_{00}$ is a non-closed subspace of $\ell^\infty$, the closed unit ball of $\ell^2$ is closed and bounded but not compact (Theorem 7.43), and there are discontinuous linear maps (Example 5).
Bounded Linear Operators and the Operator Norm
Let $X,Y$ be normed spaces. A linear map $T:X\to Y$ is bounded if there is $M\ge0$ with $\|Tx\|\le M\|x\|$ for all $x\in X$. The operator norm of a bounded $T$ is $$\|T\|=\sup_{\|x\|\le1}\|Tx\|=\sup_{x\ne0}\frac{\|Tx\|}{\|x\|},$$ the smallest admissible $M$ (and, if $X\ne\{0\}$, also $\sup_{\|x\|=1}\|Tx\|$). The bounded operators form the space $B(X,Y)$; we write $B(X)=B(X,X)$. A bounded linear map $X\to\mathbb{F}$ is a bounded linear functional, and $X^*=B(X,\mathbb{F})$ is the dual space.
"Bounded" here does not mean that $T(X)$ is a bounded set (only $T=0$ has that property); it means that $T$ maps bounded sets to bounded sets.
Proof. (4)$\Rightarrow$(3): $\|Tx-Ty\|=\|T(x-y)\|\le\|T\|\,\|x-y\|$. (3)$\Rightarrow$(2)$\Rightarrow$(1) is clear. (1)$\Rightarrow$(4): with $\varepsilon=1$ there is $\delta\gt0$ such that $\|x\|\le\delta$ implies $\|Tx\|=\|Tx-T0\|\le1$. For $x\ne0$, the vector $\delta x/\|x\|$ has norm $\delta$, so $$\|Tx\|=\frac{\|x\|}{\delta}\Big\|T\Big(\frac{\delta x}{\|x\|}\Big)\Big\|\le\frac1\delta\|x\|.$$ So $T$ is bounded with $\|T\|\le1/\delta$. ∎
- The operator norm is a norm on $B(X,Y)$, and $\|ST\|\le\|S\|\,\|T\|$ for $T\in B(X,Y)$, $S\in B(Y,Z)$.
- If $Y$ is a Banach space, so is $B(X,Y)$. In particular the dual $X^*$ of every normed space is a Banach space.
- (Neumann series) If $X$ is a Banach space, $T\in B(X)$ and $\sum_n\|T^n\|\lt\infty$ (e.g. $\|T\|\lt1$), then $I-T$ is invertible in $B(X)$ with $(I-T)^{-1}=\sum_{n\ge0}T^n$; if $\|T\|\lt1$, then $\|(I-T)^{-1}\|\le\dfrac1{1-\|T\|}$.
Proof. (1) $\|(S+T)x\|\le\|Sx\|+\|Tx\|\le(\|S\|+\|T\|)\|x\|$ and $\|(\lambda T)x\|=|\lambda|\|Tx\|$ give the triangle inequality and homogeneity; $\|T\|=0$ forces $Tx=0$ for all $x$. Also $\|STx\|\le\|S\|\|Tx\|\le\|S\|\|T\|\|x\|$.
(2) Let $(T_n)$ be Cauchy in $B(X,Y)$. For each $x$, $\|T_nx-T_mx\|\le\|T_n-T_m\|\|x\|$, so $(T_nx)$ is Cauchy in $Y$; let $Tx=\lim T_nx$. $T$ is linear (limits respect sums and scalar multiples). Given $\varepsilon\gt0$ choose $N$ with $\|T_n-T_m\|\lt\varepsilon$ for $m,n\ge N$; then $\|T_nx-T_mx\|\le\varepsilon\|x\|$, and letting $m\to\infty$, $\|T_nx-Tx\|\le\varepsilon\|x\|$ for all $x$ and $n\ge N$. Hence $T_n-T$ is bounded, so $T=T_n-(T_n-T)$ is bounded, and $\|T_n-T\|\le\varepsilon$ for $n\ge N$. $\mathbb{F}$ is complete, so $X^*$ is a Banach space.
(3) $B(X)$ is a Banach space by (2), so the absolutely convergent series $S=\sum T^n$ converges (Theorem 7.34). With $S_N=\sum_{n\le N}T^n$ we have $(I-T)S_N=S_N(I-T)=I-T^{N+1}$, and $\|T^{N+1}\|\to0$ (terms of a convergent series). Letting $N\to\infty$ (multiplication is continuous by (1)): $(I-T)S=S(I-T)=I$. If $\|T\|\lt1$, $\|S\|\le\sum\|T\|^n=\frac1{1-\|T\|}$. ∎
- Let $A=(a_{ij})$ be an $m\times n$ matrix, viewed as a map $\mathbb{F}^n\to\mathbb{F}^m$. Then the largest column sum $$\|A\|_{1\to1}=\max_j\sum_i|a_{ij}|,$$ the largest row sum $$\|A\|_{\infty\to\infty}=\max_i\sum_j|a_{ij}|,$$ and the largest singular value $$\|A\|_{2\to2}=\sqrt{\lambda_{\max}(A^*A)}.$$ Every eigenvalue $\lambda$ of a square $A$ satisfies $|\lambda|\le\|A\|$ for each of these norms.
- Let $K:[0,1]^2\to\mathbb{R}$ be continuous and $(\mathcal{K}f)(x)=\int_0^1K(x,t)f(t)\,dt$. Then $\mathcal{K}$ maps $C[0,1]$ into itself and, with the sup norm, $$\|\mathcal{K}\|\le\kappa:=\max_{x\in[0,1]}\int_0^1|K(x,t)|\,dt,$$ with equality when $K\ge0$ (or $K\le0$). (Equality holds for every continuous kernel; see Exercise III.8.)
Proof. (1) Let $c_j=\sum_i|a_{ij}|$ and $r_i=\sum_j|a_{ij}|$. Then $\|Ax\|_1=\sum_i\big|\sum_ja_{ij}x_j\big|$ is at most $\sum_j|x_j|c_j\le(\max_jc_j)\|x\|_1$, with equality at $x=e_{j_0}$ for a column $j_0$ of largest sum. Next $|(Ax)_i|\le\sum_j|a_{ij}||x_j|\le r_i\|x\|_\infty$, with equality in row $i_0$ of largest sum for $x_j=\overline{\operatorname{sgn}a_{i_0j}}$ (a vector with $\|x\|_\infty\le1$). For the $2$-norm, $A^*A$ is Hermitian and positive semidefinite, so by the spectral theorem (§10.2) it has an orthonormal eigenbasis $v_k$ with eigenvalues $\mu_k\ge0$; for $x=\sum c_kv_k$, $\|Ax\|_2^2=\langle A^*Ax,x\rangle=\sum\mu_k|c_k|^2\le\mu_{\max}\|x\|_2^2$, with equality at an eigenvector for $\mu_{\max}$. If $Av=\lambda v$ with $v\ne0$, then $|\lambda|\|v\|=\|Av\|\le\|A\|\|v\|$.
(2) $K$ is uniformly continuous on the compact square (§7.2), so $|\mathcal{K}f(x)-\mathcal{K}f(y)|$ is at most $\|f\|_\infty\max_t|K(x,t)-K(y,t)|$, which tends to $0$ as $y\to x$: $\mathcal{K}f$ is continuous. For every $x$, $|\mathcal{K}f(x)|\le\int_0^1|K(x,t)|\,|f(t)|\,dt\le\kappa\|f\|_\infty$, so $\|\mathcal{K}\|\le\kappa$. If $K\ge0$, take $f\equiv1$: $\mathcal{K}1(x)=\int_0^1K(x,t)\,dt$, whose maximum is $\kappa$; so $\|\mathcal{K}\|\ge\kappa$. ∎
Infinite Dimensions: Riesz's Lemma and the Unit Ball
In $\mathbb{R}^n$ the closed unit ball is compact. The next two results show that this single property characterises finite-dimensional spaces.
Proof. Pick $x_0\in X\setminus Y$ and let $d=\inf_{y\in Y}\|x_0-y\|$. Then $d\gt0$: otherwise $x_0$ would be a limit of points of $Y$, and $Y$ is closed. Since $d/\theta\gt d$, there is $y_0\in Y$ with $\|x_0-y_0\|\le d/\theta$. Put $x=\dfrac{x_0-y_0}{\|x_0-y_0\|}$, so $\|x\|=1$. For $y\in Y$, the vector $y_0+\|x_0-y_0\|\,y$ lies in $Y$, hence $$\|x-y\|=\frac{\big\|x_0-\big(y_0+\|x_0-y_0\|y\big)\big\|}{\|x_0-y_0\|}\ge\frac{d}{d/\theta}=\theta.$$ (For finite-dimensional $Y$ the infimum $d$ is attained by compactness, and $\theta=1$ works.) ∎
Proof. (1)$\Rightarrow$(3) is Theorem 7.38(3), and (3)$\Rightarrow$(2) is clear. (2)$\Rightarrow$(1): suppose $\dim X=\infty$. Choose $x_1$ with $\|x_1\|=1$. Having chosen unit vectors $x_1,\dots,x_n$, the subspace $Y_n=\operatorname{span}\{x_1,\dots,x_n\}$ is finite-dimensional, hence closed (Theorem 7.38(2)), and proper. Riesz's lemma with $\theta=\tfrac12$ gives a unit vector $x_{n+1}$ with $\|x_{n+1}-y\|\ge\tfrac12$ for all $y\in Y_n$, in particular $\|x_{n+1}-x_k\|\ge\frac12$ for $k\le n$. The sequence $(x_n)$ in $\overline B$ has no Cauchy subsequence, hence no convergent subsequence, so $\overline B$ is not (sequentially) compact (§7.2). Finally, if a compact $K$ contained a ball $B(x,r)$, then $\overline B(x,r/2)$, a closed subset of $K$, would be compact, and so would its image $\overline B$ under the homeomorphism $y\mapsto(2/r)(y-x)$. ∎
In concrete spaces one does not need Riesz: in $\ell^p$ the unit vectors $e_n$ satisfy $\|e_n-e_m\|_p=2^{1/p}$ ($\|e_n-e_m\|_\infty=1$ in $\ell^\infty$ and $c_0$), and in $C[0,1]$ tents of height $1$ with disjoint supports are at mutual distance $1$. Each of these is a sequence in the closed unit ball with no convergent subsequence.
Spaces of Continuous Functions: Arzelà–Ascoli and Stone–Weierstrass
Since the closed bounded subsets of $C(K)$ are not compact in general, which ones are? The answer — the Arzelà–Ascoli theorem — is one of the most used compactness criteria in analysis (existence theorems for ODEs, compact operators, calculus of variations). It needs one new notion.
Let $(K,d)$ be a metric space and $\mathcal{F}$ a family of functions $K\to\mathbb{F}$. $\mathcal{F}$ is equicontinuous at $x_0$ if for every $\varepsilon\gt0$ there is $\delta\gt0$ such that $$d(x,x_0)\lt\delta\ \Longrightarrow\ |f(x)-f(x_0)|\lt\varepsilon$$ for all $f\in\mathcal{F}$; it is equicontinuous if it is equicontinuous at every point, and uniformly equicontinuous if one $\delta$ works for all points and all $f$: $d(x,y)\lt\delta\Rightarrow|f(x)-f(y)|\lt\varepsilon$ for all $x,y\in K$ and $f\in\mathcal{F}$.
$\mathcal{F}$ is pointwise bounded if $\sup_{f\in\mathcal{F}}|f(x)|\lt\infty$ for each $x$, and uniformly bounded if $\sup_{f\in\mathcal{F}}\|f\|_\infty\lt\infty$. A subset of a metric space is relatively compact if its closure is compact; in a complete metric space this holds iff every sequence in it has a Cauchy (hence convergent) subsequence.
The key word is "for all $f$": one $\delta$ must serve every member of the family. A uniformly Lipschitz family ($|f(x)-f(y)|\le L\,d(x,y)$ for all $f\in\mathcal{F}$) is uniformly equicontinuous with $\delta=\varepsilon/L$; so is, by the mean value theorem, any family of $C^1$ functions on an interval with $\sup_{\mathcal{F}}\|f'\|_\infty\lt\infty$. On a compact $K$, equicontinuity implies uniform equicontinuity (the proof of the Heine–Cantor theorem, §3.2, goes through word for word — Exercise IV.3). The family $\{x^n\}$ on $[0,1]$ is not equicontinuous at $1$: for any $\delta$, $1-(1-\tfrac\delta2)^n\to1$.
Proof sketch. ($\Leftarrow$) Step 1: a countable dense set. A compact metric space is totally bounded (§7.2), so for each $k$ it is covered by finitely many balls of radius $\frac1k$; the centres of all these balls form a countable dense set $D=\{d_1,d_2,\dots\}$. Step 2: the diagonal argument. Let $(f_n)$ be a sequence in $\mathcal{F}$. The numbers $f_n(d_1)$ are bounded, so by Bolzano–Weierstrass some subsequence converges at $d_1$; from it extract a further subsequence converging at $d_2$; and so on. The diagonal sequence $g_k$ ($k$-th term of the $k$-th subsequence) converges at every point of $D$. Step 3: uniformly Cauchy. Let $\varepsilon\gt0$ and take $\delta$ from uniform equicontinuity (compact $K$) for $\varepsilon/3$. Finitely many points $d_{i_1},\dots,d_{i_r}$ of $D$ are $\delta$-dense in $K$ (cover $K$ by $\delta$-balls around points of $D$ and use compactness). Choose $N$ with $|g_k(d_{i_s})-g_l(d_{i_s})|\lt\varepsilon/3$ for $k,l\ge N$ and all $s$. Every $x$ is within $\delta$ of some $d_{i_s}$, so $$\begin{aligned}|g_k(x)-g_l(x)|&\le|g_k(x)-g_k(d_{i_s})|\\&\quad+|g_k(d_{i_s})-g_l(d_{i_s})|\\&\quad+|g_l(d_{i_s})-g_l(x)|\lt\varepsilon .\end{aligned}$$ So $(g_k)$ is uniformly Cauchy, and converges in the Banach space $C(K)$ (Theorem 7.33).
($\Rightarrow$) A relatively compact set is totally bounded: for $\varepsilon\gt0$ there are $f_1,\dots,f_m\in\mathcal{F}$ with every $f\in\mathcal{F}$ within $\varepsilon/3$ of some $f_i$. In particular $\|f\|_\infty\le\max_i\|f_i\|_\infty+\varepsilon/3$ — uniformly bounded. Each $f_i$ is uniformly continuous on $K$; take $\delta$ working for all $m$ of them with $\varepsilon/3$. Then for $d(x,y)\lt\delta$ and $f$ within $\varepsilon/3$ of $f_i$: $|f(x)-f(y)|\le\frac\varepsilon3+|f_i(x)-f_i(y)|+\frac\varepsilon3\lt\varepsilon$. So $\mathcal{F}$ is (uniformly) equicontinuous. ∎
The second great theorem about $C(K)$ tells us when a family of "simple" functions is rich enough to approximate everything. It generalises the Weierstrass approximation theorem (§5.2) from polynomials on $[a,b]$ to any algebra of functions on any compact metric space.
- $\mathcal{A}$ contains the constant functions, and
- $\mathcal{A}$ separates points: for $x\ne y$ in $K$ there is $f\in\mathcal{A}$ with $f(x)\ne f(y)$.
Idea of the proof. The closure $\overline{\mathcal{A}}$ is again an algebra. Since $|t|$ is a uniform limit of polynomials on any bounded interval (Weierstrass), $f\in\overline{\mathcal{A}}$ implies $|f|\in\overline{\mathcal{A}}$, hence $\max(f,g)=\frac{f+g+|f-g|}2$ and $\min(f,g)$ lie in $\overline{\mathcal{A}}$. Point separation and constants give, for any $x\ne y$ and any target values $a,b$, a function $h\in\mathcal{A}$ with $h(x)=a$, $h(y)=b$. Given $F\in C(K)$ and $\varepsilon\gt0$, a compactness argument then builds, from finitely many such two-point interpolants, first $\max$'s that are $\gt F-\varepsilon$ everywhere and agree with $F$ at a point, and then a $\min$ of finitely many of those that lies within $\varepsilon$ of $F$ everywhere. In the complex case, conjugation-closure ensures that $\operatorname{Re}f=\frac{f+\bar f}2$ and $\operatorname{Im}f$ lie in $\mathcal{A}$, reducing to the real case. ∎
Proof. (a) Polynomials in $x_1,\dots,x_n$ form an algebra containing the constants and separating points (the coordinate functions do), so they are dense by Stone–Weierstrass; polynomials with rational coefficients are a countable set, and any polynomial on the bounded set $K$ is uniformly approximated by one with rational coefficients. (b) Given $x\in\ell^p$ and $\varepsilon\gt0$, choose $N$ with $\sum_{n\gt N}|x_n|^p\lt\varepsilon^p/2$ and rationals (or Gaussian rationals) $q_n$ with $\sum_{n\le N}|x_n-q_n|^p\lt\varepsilon^p/2$; then $q=(q_1,\dots,q_N,0,\dots)$ satisfies $\|x-q\|_p\lt\varepsilon$, and the finitely supported rational sequences are countable. (c) The $0$–$1$ sequences form an uncountable subset of $\ell^\infty$ (§1.1) whose points are at mutual distance $1$. The balls of radius $\frac12$ around them are pairwise disjoint, and a dense set must meet each of them — so it is uncountable. ∎
- Is it a norm? Check definiteness first (seminorms such as $\sup|f'|$ or $|f(0)|$ fail it), then the triangle inequality on simple vectors like $e_1,e_2$; a bounded metric never comes from a norm.
- Complete? Finite-dimensional: always. Otherwise, is the space a closed subspace of a known Banach space ($\ell^p$, $C(K)$, $C^1$ with the $C^1$ norm)? To disprove, build a Cauchy sequence whose limit leaves the space: ramps in $\|\cdot\|_1$, truncations in $c_{00}$, Taylor polynomials in $\mathcal{P}$, $\sqrt{x^2+1/n^2}$ in $C^1$ with the sup norm.
- Equivalent norms? Finite dimension: yes. Otherwise test a sequence like $x^n$, tents of shrinking width, or $(1,\dots,1,0,\dots)$, and compare the ratio of the two norms.
- Operator norm: find an upper bound $M$ by estimating $\|Tx\|$, then a vector (or a sequence of vectors) showing $\|Tx\|/\|x\|$ reaches (or approaches) $M$. Matrices: column sums ($\|\cdot\|_1$), row sums ($\|\cdot\|_\infty$), singular values ($\|\cdot\|_2$). Positive kernels: test $f\equiv1$.
- Uniformly convergent subsequence? Check boundedness and equicontinuity (a uniform Lipschitz or derivative bound is the usual certificate). To disprove, show the pointwise limit is discontinuous, or that sup-distances stay bounded below.
- Dense? For an algebra, check constants, point separation, and (complex case) conjugation; otherwise look for a continuous linear functional (an integral against a weight, an evaluation) that vanishes on the set but not on the target.
- Completeness depends on the norm. $C[0,1]$ is complete in $\|\cdot\|_\infty$ but not in $\|\cdot\|_1$ or $\|\cdot\|_2$ (Theorem 7.35).
- Norms in infinite dimensions need not be equivalent ($\|\cdot\|_1$, $\|\cdot\|_2$, $\|\cdot\|_\infty$ on $C[0,1]$ via $x^n$). On a finite-dimensional space they always are.
- Closed and bounded $\not\Rightarrow$ compact. The closed unit balls of $\ell^2$ and $C[0,1]$; the set $\{e_n\}$ in $\ell^2$ is closed, bounded and discrete.
- Linear does not mean continuous. $D=d/dx$ in the sup norm, $f\mapsto f(0)$ in $\|\cdot\|_1$, $\sum x_n$ on $(c_{00},\|\cdot\|_\infty)$.
- Subspaces need not be closed. $c_{00}\subset\ell^2$, polynomials $\subset C[0,1]$ — both dense and proper. Finite-dimensional subspaces are always closed.
- The operator norm need not be attained (Example 5(c)); in finite dimensions it always is.
- $\|\cdot\|_p$ for $0\lt p\lt1$ is not a norm: $\|e_1+e_2\|_p=2^{1/p}\gt2$; its unit ball is not convex.
- Spectral radius is not a norm. $\begin{pmatrix}0&1\\0&0\end{pmatrix}$ has all eigenvalues $0$ but norm $1$; in general $\max|\lambda|\le\|A\|$, often strictly.
- Arzelà–Ascoli needs a compact domain. The bumps $f_n(x)=e^{-(x-n)^2}$ on $\mathbb{R}$ are bounded and uniformly equicontinuous, converge pointwise to $0$, but $\|f_n\|_\infty=1$: no uniformly convergent subsequence.
- Pointwise convergence plus boundedness is not enough ($x^n$, $nxe^{-nx}$): equicontinuity is the missing ingredient.
- Stone–Weierstrass needs every hypothesis. No constants: polynomials vanishing at $0$. No separation: even polynomials on $[-1,1]$. No conjugation (complex): polynomials in $z$ on the circle.
- Isometries need not be onto. The right shift $(x_1,x_2,\dots)\mapsto(0,x_1,x_2,\dots)$ on $\ell^2$ preserves norms but is not surjective — impossible for a linear map of $\mathbb{F}^n$ into itself.
- Bigger is not less separable. $C[0,1]$ is separable; $\ell^\infty$, which looks "smaller", is not.
Exercises
- 1 For which real $a,b$ is $N(x,y)=\max(|x+ay|,|by|)$ a norm on $\mathbb{R}^2$?
- 2 Prove that $N(f)=|f(0)|+\int_0^1|f'|$ is a norm on $C^1[0,1]$ and that $\|f\|_\infty\le N(f)$.
- 3 Show that $\|x\|_p=(|x_1|^p+|x_2|^p)^{1/p}$ is not a norm on $\mathbb{R}^2$ when $0\lt p\lt1$.
- 4 Show that the discrete metric on $\mathbb{R}$ is not induced by any norm, in two ways.
- 5 Prove that $c_0$ is a Banach space and that $c_{00}$ is dense in it.
- 6 Show that $f_n(x)=x^n$ is Cauchy in $(C[0,1],\|\cdot\|_1)$. Does it converge there? Is it Cauchy in $\|\cdot\|_\infty$?
- 7 In $(C[0,1],\|\cdot\|_\infty)$ find the distance from $f(x)=x$ to the subspace of constant functions, and from $g(x)=x^2$ to the subspace $\operatorname{span}\{1,x\}$.
- 8 Prove that a normed space $X$ is a Banach space if its closed unit ball is complete. Is a normed space in which every closed ball is compact necessarily finite-dimensional?
- 1 Find the best constants $c,C$ in $c\|x\|_\infty\le\|x\|_1\le C\|x\|_\infty$ on $\mathbb{R}^n$.
- 2 Show that on $C[0,1]$ the norms $\|f\|_\infty$ and $\|f\|'=\|f\|_\infty+|f(0)|$ are equivalent, but $\|f\|_\infty$ and $\|f\|_\infty+|f'(0)|$ cannot be compared on $C^1[0,1]$ in this way.
- 3 Show that on $C^1[0,1]$ the norms $\|f\|_\infty$ and $\|f\|_{C^1}=\|f\|_\infty+\|f'\|_\infty$ are not equivalent.
- 4 Let $p_k$ be polynomials of degree at most $5$ converging uniformly on $[0,1]$ to $f$. Prove that $f$ is a polynomial of degree at most $5$ and that the coefficients of $p_k$ converge.
- 5 Prove that $\lim_{p\to\infty}\|x\|_p=\|x\|_\infty$ for $x\in\mathbb{R}^n$, and that $p\mapsto\|x\|_p$ is non-increasing.
- 6 Let $\|\cdot\|$ be any norm on $\mathbb{R}^2$. Show that its closed unit ball is compact, convex, symmetric ($x\in B\Rightarrow-x\in B$) and contains a Euclidean disc around $0$.
- 7 Prove that every linear functional on $\mathbb{R}^n$ is continuous, and compute the norm of $\varphi(x)=x_1-2x_2+3x_3$ on $(\mathbb{R}^3,\|\cdot\|_1)$, $(\mathbb{R}^3,\|\cdot\|_2)$ and $(\mathbb{R}^3,\|\cdot\|_\infty)$.
- 1 Compute $\|A\|_{1\to1}$, $\|A\|_{\infty\to\infty}$, $\|A\|_{2\to2}$ for $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$.
- 2 Show that $\|A\|_{2\to2}=\frac{1+\sqrt5}{2}$ for $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$, although both eigenvalues equal $1$.
- 3 On $(C[0,1],\|\cdot\|_\infty)$ let $(Tf)(x)=xf(x)$. Find $\|T\|$ and show that $T$ is injective but not surjective.
- 4 Find the norm of $\psi(f)=\int_0^1tf(t)\,dt$ on $(C[0,1],\|\cdot\|_\infty)$ and on $(C[0,1],\|\cdot\|_1)$. Is it attained?
- 5 Let $S(x_1,x_2,\dots)=(0,x_1,x_2,\dots)$ and $L(x_1,x_2,\dots)=(x_2,x_3,\dots)$ on $\ell^2$. Find $\|S\|$, $\|L\|$, $LS$ and $SL$.
- 6 Find the norm of $(\mathcal{K}f)(x)=\int_0^1e^{x-t}f(t)\,dt$ on $(C[0,1],\|\cdot\|_\infty)$.
- 7 Prove that a linear functional $\varphi$ on a normed space is continuous if and only if $\ker\varphi$ is closed.
- 8 Show that for every continuous kernel $K$ the integral operator of Theorem 7.41(2) has $\|\mathcal{K}\|=\max_x\int_0^1|K(x,t)|\,dt$.
- 1 Show that $\{e_n\}$ has no convergent subsequence in $\ell^2$, but that the "Hilbert cube" $Q=\{x\in\ell^2:|x_n|\le\frac1n\text{ for all }n\}$ is compact.
- 2 Construct a sequence in the closed unit ball of $C[0,1]$ with $\|f_n-f_m\|_\infty=1$ for all $n\ne m$.
- 3 Prove that an equicontinuous family on a compact metric space is uniformly equicontinuous.
- 4 Decide whether each sequence is equicontinuous on $[0,1]$: (a) $\frac{\sin nx}{\sqrt n}$; (b) $\arctan(nx)$; (c) $\sqrt{x+\frac1n}$; (d) $x^n(1-x)$.
- 5 Let $\mathcal{L}$ be the set of $f\in C[0,1]$ with $f(0)=0$ and $|f(x)-f(y)|\le|x-y|$ for all $x,y$. Prove that $\mathcal{L}$ is compact in $(C[0,1],\|\cdot\|_\infty)$, and find $\max_{f\in\mathcal{L}}\int_0^1f$.
- 6 Show that functions of the form $\sum_{i=1}^kg_i(x)h_i(y)$, with $g_i,h_i\in C[0,1]$, are dense in $C([0,1]^2)$.
- 7 Prove that $\ell^1$ is separable and $\ell^\infty$ is not.
- 8 Let $f\in C[0,1]$ satisfy $\int_0^1f(x)e^{nx}\,dx=0$ for all $n=0,1,2,\dots$. Prove that $f\equiv0$.
E1. CSIR Part B GATE MA On the vector space $C[0,1]$ consider the norms (A) $\|f\|_1=\int_0^1|f|$; (B) $\|f\|_2=\big(\int_0^1|f|^2\big)^{1/2}$; (C) $\|f\|_\infty=\max|f|$; (D) $\|f\|=|f(0)|+\int_0^1|f|$. With which of them is $C[0,1]$ a Banach space?
E2. CSIR Part B Let $T:(C[0,1],\|\cdot\|_\infty)\to(C[0,1],\|\cdot\|_\infty)$, $(Tf)(x)=\int_0^1\min(x,t)\,f(t)\,dt$. Then $\|T\|$ equals (A) $\frac14$; (B) $\frac12$; (C) $1$; (D) $2$.
E3. CSIR Part B Let $A=\begin{pmatrix}0&2\\1&0\end{pmatrix}$ act on $\mathbb{R}^2$ with the Euclidean norm. The operator norm of $A$ is (A) $1$; (B) $\sqrt2$; (C) $2$; (D) $3$.
E4. CSIR Part C Let $X$ be an infinite-dimensional normed linear space. Which of the following statements are true? (A) The closed unit ball of $X$ is not compact. (B) Every linear functional on $X$ is continuous. (C) Every finite-dimensional subspace of $X$ is closed. (D) Any two norms on $X$ are equivalent.
E5. CSIR Part C Which of the following subsets of $(C[0,1],\|\cdot\|_\infty)$ have compact closure? (A) $\{x^n:n\in\mathbb{N}\}$; (B) $\{\frac{\sin(nx)}{n}:n\in\mathbb{N}\}$; (C) $\{f:\|f\|_\infty\le1\}$; (D) $\{f\in C^1[0,1]:\|f\|_\infty\le1,\ \|f'\|_\infty\le5\}$.
E6. CSIR Part C Which of the following sets are dense in $(C[0,1],\|\cdot\|_\infty)$? (A) The polynomials with rational coefficients. (B) $\{p\text{ polynomial}:p(0)=0\}$. (C) $\operatorname{span}\{1,x^3,x^6,x^9,\dots\}$. (D) $\operatorname{span}\{\sin(n\pi x):n\in\mathbb{N}\}$.
Suggested plan — 3 lectures × 60 min.
- Norms and completeness. Definition 7.21 and Theorem 7.32; Example 1(b) as a class poll. Theorem 7.33 (do the $\ell^p$ proof — it is the template for every "this space is complete" argument), Theorem 7.34, and Theorem 7.35 with a picture of the ramps. Example 2 as a rapid-fire round; end with the principle "complete = closed in a Banach space".
- Finite dimension and operators. Theorems 7.36–7.38 with the compactness proof of 7.37; Example 3 and Interactive 1 (start at $p=2$, slide to $p=1$, $p=\infty$, then below $1$). Theorems 7.39–7.41; Example 4 on the board (the Volterra computation and the Neumann series solving an integral equation are worth the time), Example 5 as "prove or disprove".
- Infinite dimensions and $C(K)$. Riesz's lemma and Theorem 7.43 with the explicit $e_n$ and tent sequences. Definition 7.24, Arzelà–Ascoli with the diagonal argument; Example 6 with Interactive 2 projected (families 1, 3, 2, then 4 and 5). Stone–Weierstrass (statement and idea), Theorem 7.46, Example 7. Close with E4 and E6.
Discussion questions. (1) Why is the sup norm the "right" norm on $C[a,b]$, and when would an engineer prefer $\|\cdot\|_2$? (2) The proof of Theorem 7.37 uses compactness of the unit sphere of $\mathbb{F}^n$. Which step breaks for $c_{00}$ with $\|\cdot\|_\infty$? (3) Arzelà–Ascoli and Bolzano–Weierstrass both say "bounded + something ⇒ convergent subsequence". What plays the role of "something" in $\mathbb{R}^n$, and why is nothing extra needed there?
Misconceptions to watch for. Assuming every norm on $C[0,1]$ is complete; "bounded operator" meaning bounded range; confusing spectral radius with operator norm; thinking closed and bounded implies compact in every normed space; believing every linear map is continuous; forgetting the constants (or conjugation) in Stone–Weierstrass; thinking pointwise convergence plus boundedness yields a uniformly convergent subsequence.
Suggested homework. I(1, 4, 6, 7), II(1, 3, 4, 7), III(1, 2, 4, 5, 7), IV(1, 4, 5, 8); Exam corner E2, E4, E5.
Research question. How well can a polynomial of degree $n$ approximate the function $|x|$ on $[-1,1]$ in the sup norm, and is the error of the best polynomial much smaller than that of the Bernstein polynomials used to prove the Weierstrass theorem?
Why it matters. Every time a calculator, a graphics card or an embedded controller evaluates $\sqrt x$, $e^x$ or $\sin x$, it actually evaluates a polynomial (or rational function) chosen to minimise the maximum error over an interval — a best approximation in $(C[a,b],\|\cdot\|_\infty)$. The same minimax problem designs the digital filters in mobile phones and hearing aids. The kink of $|x|$ is the hardest case, and the rate at which its best error decays was a famous problem solved by S. N. Bernstein in 1914.
What to do.
- Write the best-approximation problem "minimise $t$ subject to $|p(x_j)-|x_j||\le t$ at many points $x_j$" as a linear programme in the coefficients of $p$ (use Chebyshev polynomials as the basis for numerical stability) and solve it for even degrees $n=2,4,6,10,20,40$.
- Tabulate the best error $E_n$ and the product $nE_n$. Check $E_2$ by hand: the best quadratic is $x^2+\frac18$.
- For the same $n$, compute the sup-norm error of the Bernstein polynomial of $|x|$ (after mapping $[-1,1]$ to $[0,1]$); it is largest at the kink.
- Plot the error curve $|x|-p^*(x)$ for $n=10$ and count its equioscillation points — compare with Chebyshev's alternation theorem.
Tools: Python with numpy and scipy.optimize.linprog (or any LP solver); a plotting library.
Hand in: The table of $E_n$, $nE_n$ and the Bernstein errors, a log–log plot of both errors against $n$, and two sentences on what the slopes tell you.
Going further. Read about Bernstein's constant $\beta=\lim_{n\to\infty}2nE_{2n}(|x|)$ and the high-precision computation by Varga and Carpenter that disproved Bernstein's guess $\beta=\frac1{2\sqrt\pi}$; try the Remez exchange algorithm instead of linear programming.
🧪 Self-check quiz
Q1. Which of these normed spaces is not complete?
Q2. Which statement about norms on $\mathbb{R}^n$ is correct?
Q3. The closed unit ball of a normed space $X$ is compact if and only if
Q4. For $A=\begin{pmatrix}1&-3\\2&1\end{pmatrix}$ acting on $(\mathbb{R}^2,\|\cdot\|_\infty)$, the operator norm is
Q5. The sequence $f_n(x)=x^n$ in $(C[0,1],\|\cdot\|_\infty)$