The Hahn–Banach theorem

In a Hilbert space the Riesz theorem hands us as many continuous functionals as there are vectors. In a general normed space it is not even clear that there is a single nonzero continuous linear functional. The Hahn–Banach theorem guarantees that there are plenty: any bounded functional on a subspace extends to the whole space without increasing its norm. From this one extension theorem flow the facts that functionals separate points, that norms can be computed by testing against functionals, that closed convex sets can be separated by hyperplanes, and that every normed space sits isometrically inside its second dual. The theorem is due to Hans Hahn in 1927 and, independently and in the form we use, to Stefan Banach in 1929; the extension to complex scalars came in 1938.

Sublinear functionals and the one-step extension

Definition 7.1. A function \(p : X \to \mathbb{R}\) on a real vector space is sublinear if \(p(x + y) \le p(x) + p(y)\) and \(p(tx) = t p(x)\) for all \(x, y \in X\) and \(t \ge 0\). Every seminorm is sublinear, and so is every linear functional. A typical example that is neither is \(p(x) = \limsup_n x_n\) on the space of bounded real sequences.

Lemma 7.2. Let \(X\) be a real vector space, \(p\) sublinear, \(M\) a subspace and \(f : M \to \mathbb{R}\) linear with \(f \le p\) on \(M\). If \(x_0 \notin M\), then \(f\) extends to a linear functional \(g\) on \(M_1 = M + \mathbb{R} x_0\) with \(g \le p\) on \(M_1\).

Proof. Any linear extension has the form \(g(m + t x_0) = f(m) + tc\) for a constant \(c = g(x_0)\), and we must choose \(c\) so that \(f(m) + tc \le p(m + t x_0)\) for all \(m \in M\) and real \(t\). For \(t = 0\) this is the hypothesis. Dividing by \(|t|\) and using positive homogeneity, the condition for \(t > 0\) becomes \(c \le p(m + x_0) - f(m)\) for all \(m \in M\), and for \(t < 0\) it becomes \(c \ge f(m^{\prime}) - p(m^{\prime} - x_0)\) for all \(m^{\prime} \in M\). A suitable \(c\) exists if and only if \[\sup_{m^{\prime} \in M} \big(f(m^{\prime}) - p(m^{\prime} - x_0)\big) \le \inf_{m \in M} \big(p(m + x_0) - f(m)\big).\] For any \(m, m^{\prime} \in M\), \(f(m^{\prime}) + f(m) = f(m^{\prime} + m) \le p(m^{\prime} + m) \le p(m^{\prime} - x_0) + p(m + x_0)\), which rearranges to exactly this inequality term by term. \(\blacksquare\)

The proof gives an interval of admissible values for \(c\), which may be a single point or a whole segment; the extension is usually not unique. In a space with a countable algebraic spanning set we could now extend one dimension at a time. In general we need a transfinite argument.

The theorem

Theorem 7.3 (Hahn–Banach, real version). Let \(X\) be a real vector space, \(p\) a sublinear functional, \(M\) a subspace and \(f\) a linear functional on \(M\) with \(f \le p\) on \(M\). Then there is a linear functional \(F\) on \(X\) extending \(f\) with \(F \le p\) on \(X\).

Proof. Let \(\mathcal{E}\) be the set of pairs \((N, g)\) where \(N \supseteq M\) is a subspace and \(g\) is a linear extension of \(f\) to \(N\) with \(g \le p\). Order \(\mathcal{E}\) by extension: \((N, g) \preceq (N^{\prime}, g^{\prime})\) if \(N \subseteq N^{\prime}\) and \(g^{\prime}\) restricts to \(g\). The set is nonempty since it contains \((M, f)\). Every chain \((N_i, g_i)\) has an upper bound: \(N = \bigcup N_i\) is a subspace because the chain is totally ordered, and \(g(x) = g_i(x)\) for \(x \in N_i\) is well defined, linear and bounded by \(p\). By Zorn's lemma there is a maximal element \((N, F)\). If \(N \ne X\), Lemma 7.2 would extend \(F\) to a strictly larger subspace, contradicting maximality. So \(N = X\). \(\blacksquare\)

Theorem 7.4 (complex version; Bohnenblust and Sobczyk, and Soukhomlinov, 1938). Let \(X\) be a complex vector space, \(p\) a seminorm, \(M\) a subspace and \(f\) a complex linear functional on \(M\) with \(|f| \le p\) on \(M\). Then \(f\) has a complex linear extension \(F\) to \(X\) with \(|F| \le p\).

Proof. Let \(u = \operatorname{Re} f\), a real linear functional on \(M\) regarded as a real space. Since \(\operatorname{Im} f(x) = -\operatorname{Re}(i f(x)) = -u(ix)\), we have \(f(x) = u(x) - i u(ix)\). By Theorem 7.3, \(u\) extends to a real linear \(U\) on \(X\) with \(U \le p\). Define \(F(x) = U(x) - i U(ix)\). It is real linear, and \(F(ix) = U(ix) - iU(-x) = U(ix) + iU(x) = iF(x)\), so it is complex linear, and it extends \(f\). Given \(x\), write \(F(x) = e^{i\theta} |F(x)|\). Then \(|F(x)| = F(e^{-i\theta} x)\) is real, so it equals \(U(e^{-i\theta} x) \le p(e^{-i\theta} x) = p(x)\). \(\blacksquare\)

Consequences for normed spaces

Corollary 7.5. Let \(M\) be a subspace of a normed space \(X\) and \(f \in M^*\). Then \(f\) has an extension \(F \in X^*\) with \(\|F\| = \|f\|\). Proof: apply the theorem with the seminorm \(p(x) = \|f\| \, \|x\|\). The extension has norm at most \(\|f\|\) and at least \(\|f\|\) since it extends \(f\). \(\blacksquare\)

Corollary 7.6. For every \(x_0 \ne 0\) in a normed space \(X\) there is \(F \in X^*\) with \(\|F\| = 1\) and \(F(x_0) = \|x_0\|\). Consequently \(\|x\| = \max_{\|F\| \le 1} |F(x)|\) for every \(x\), and \(X^*\) separates the points of \(X\). Proof: on \(M = \mathbb{K} x_0\) define \(f(t x_0) = t \|x_0\|\), which has norm \(1\), and extend. The formula for the norm follows since \(|F(x)| \le \|x\|\) for \(\|F\| \le 1\), with equality for the functional just constructed. \(\blacksquare\)

This is a dual formula for the norm. Compare the definition \(\|F\| = \sup_{\|x\| \le 1} |F(x)|\): the norm of a functional is a supremum that need not be attained, whereas the norm of a vector is a maximum over functionals that is always attained.

Corollary 7.7. Let \(M\) be a closed subspace of \(X\) and \(x_0 \notin M\), with \(d = \operatorname{dist}(x_0, M) > 0\). There is \(F \in X^*\) with \(F = 0\) on \(M\), \(\|F\| = 1\) and \(F(x_0) = d\). Proof: on \(M + \mathbb{K} x_0\) define \(f(m + t x_0) = t d\). Since \(\|m + t x_0\| = |t| \, \|x_0 + m/t\| \ge |t| d\) for \(t \ne 0\), \(\|f\| \le 1\); and choosing \(m_n \in M\) with \(\|x_0 - m_n\| \to d\) shows \(\|f\| = 1\). Extend by Corollary 7.5. \(\blacksquare\) Hence a vector lies in the closed linear span of a set \(A\) if and only if every continuous functional that vanishes on \(A\) also vanishes at it. This criterion is the Banach space substitute for orthogonal complements, and it proves density results by duality.

Corollary 7.8. If \(X^*\) is separable, then \(X\) is separable. Proof: let \((f_n)\) be dense in the unit sphere of \(X^*\), and choose unit vectors \(x_n\) with \(|f_n(x_n)| > \frac{1}{2}\). Let \(M\) be the closed linear span of the \(x_n\), a separable space. If \(M \ne X\), Corollary 7.7 gives \(f\) with \(\|f\| = 1\) vanishing on \(M\). Choose \(f_n\) with \(\|f - f_n\| < \frac{1}{4}\); then \(\frac{1}{2} < |f_n(x_n)| \le |f(x_n)| + \frac{1}{4} = \frac{1}{4}\), a contradiction. \(\blacksquare\) Since \(\ell^\infty\) is not separable while \(\ell^1\) is, it follows again that \((\ell^\infty)^* \ne \ell^1\).

The second dual

Each \(x \in X\) defines a functional on \(X^*\) by evaluation, \(Jx(f) = f(x)\). Clearly \(|Jx(f)| \le \|f\| \, \|x\|\), so \(\|Jx\| \le \|x\|\), and Corollary 7.6 gives equality. Thus \(J : X \to X^{**}\) is a linear isometry, the canonical embedding. Since \(X^{**}\) is a Banach space by Theorem 3.4, the closure of \(J(X)\) in \(X^{**}\) is a completion of \(X\), which gives the promised short construction of completions. When \(J\) is onto, \(X\) is called reflexive; lesson 9 studies this property.

Separating convex sets

The geometric form of the theorem is about hyperplanes. For a convex set \(C\) containing a ball around \(0\), the Minkowski functional \(p_C(x) = \inf\{t > 0 : x \in tC\}\) is finite, sublinear, satisfies \(p_C(x) \le \|x\| / r\) if \(C\) contains the ball of radius \(r\), and \(\{p_C < 1\} \subseteq C \subseteq \{p_C \le 1\}\), with \(C = \{p_C < 1\}\) when \(C\) is open. Sublinearity: if \(x \in sC\) and \(y \in tC\), convexity gives \(x + y = (s + t)(\frac{s}{s + t} \frac{x}{s} + \frac{t}{s + t} \frac{y}{t}) \in (s + t) C\).

Theorem 7.9 (separation). Let \(C\) be an open convex subset of a real normed space and \(x_0 \notin C\). There is \(F \in X^*\) with \(F(x) < F(x_0)\) for all \(x \in C\). More generally, if \(A\) and \(B\) are disjoint convex sets with \(A\) open, there are \(F \in X^*\) and \(\gamma \in \mathbb{R}\) with \(F(a) < \gamma \le F(b)\) for all \(a \in A\), \(b \in B\).

Proof. Translating, assume \(0 \in C\). Let \(p = p_C\), so \(C = \{p < 1\}\) and \(p(x_0) \ge 1\). Define \(f(t x_0) = t\) on \(\mathbb{R} x_0\). For \(t > 0\), \(f(t x_0) = t \le t p(x_0) = p(t x_0)\); for \(t \le 0\), \(f(t x_0) \le 0 \le p(t x_0)\). Extend to \(F \le p\) on \(X\). Then \(F(x) \le p(x) \le \|x\| / r\), so \(F\) is continuous, and for \(x \in C\), \(F(x) \le p(x) < 1 = F(x_0)\). For the general statement, apply the first part to the open convex set \(A - B = \{a - b\}\), which does not contain \(0\): there is \(F\) with \(F(a - b) < 0\), so \(\sup_A F \le \inf_B F\); since \(F(A)\) is an open interval when \(F \ne 0\), the supremum is not attained, and \(\gamma = \inf_B F\) works. \(\blacksquare\)

Separation is the foundation of convex optimization and duality. A closed convex set is the intersection of the closed half-spaces containing it, because any point outside can be separated from it, after shrinking the point to a small open ball. This gives Mazur's theorem, used in lesson 9: a closed convex set is closed in the weak topology. In linear programming, separation of convex polyhedra yields Farkas' lemma and the duality theorem of MATH-372.

Banach limits

Here is a functional that no formula can describe. On the real space \(\ell^\infty\), let \(p(x) = \limsup_n \frac{1}{n} (x_1 + \cdots + x_n)\), which is sublinear. On the subspace \(c\) of convergent sequences, \(f(x) = \lim x_n\) satisfies \(f = p\), since Cesàro means of a convergent sequence converge to the same limit. Extend \(f\) to \(L \le p\) on \(\ell^\infty\). Let \(T\) be the left shift. Then \(Tx - x\) has Cesàro means \(\frac{x_{n+1} - x_1}{n} \to 0\), so \(L(Tx - x) \le p(Tx - x) = 0\), and the same with \(-x\) gives \(L(Tx) = L(x)\). Also \(-p(-x) \le L(x) \le p(x)\), which gives \(\liminf x_n \le L(x) \le \limsup x_n\), so \(L\) is positive and \(\|L\| = 1\). Such an \(L\) is a Banach limit: a shift-invariant extension of the limit to all bounded sequences. It assigns the value \(\frac{1}{2}\) to \((1, 0, 1, 0, \ldots)\), since \(x + Tx = \mathbf{1}\). It vanishes on every \(e_n\) but is not zero, so it is not of the form \(x \mapsto \sum y_n x_n\) for any \(y \in \ell^1\).

The existence of Banach limits depends on Zorn's lemma, or at least on a weak form of the axiom of choice. One cannot write down a specific Banach limit, and there are models of set theory without the full axiom of choice in which every functional on \(\ell^\infty\) comes from \(\ell^1\). The Hahn–Banach theorem in general requires some choice: it follows from the ultrafilter lemma, which is weaker than the axiom of choice.

# The interval of admissible values in the one-step extension, and Cesaro means behind Banach limits.
import itertools

# X = R^3 with p = the 1-norm; M = span{(1, 1, 0)}, f(t(1,1,0)) = 2t (so f <= p on M, with |f| = p there).
# Extending to x0 = (0, 0, 1) requires sup_m [f(m) - p(m - x0)] <= c <= inf_m [p(m + x0) - f(m)].
p = lambda v: sum(abs(t) for t in v)
ts = [k / 100 for k in range(-500, 501)]
lo = max(2 * t - p((t, t, -1)) for t in ts)
hi = min(p((t, t, 1)) - 2 * t for t in ts)
print(f"admissible values of F(0, 0, 1): [{lo:.2f}, {hi:.2f}]")
# every c in that interval works: check F = x1 + x2 + c x3 against p on an integer grid
for c in (lo, 0.0, hi):
    worst = max((a + b) + c * z - p((a, b, z)) for a, b, z in itertools.product(range(-3, 4), repeat=3))
    print(f"c = {c:5.2f}: max over grid of F(x) - p(x) with F = x1 + x2 + c x3 is {worst}")

# Cesaro means: the sequence 1, 0, 1, 0, ... has means tending to 1/2.
x = [1 - k % 2 for k in range(1, 2001)]
s = 0
for n, t in enumerate(x, 1):
    s += t
    if n in (10, 100, 2000):
        print(f"Cesaro mean of (1,0,1,0,...) after {n:4d} terms: {s / n:.4f}")
# Blocks of ones and zeros of doubling length: Cesaro means oscillate between about 1/3 and 2/3.
y, val, length = [], 1, 1
while len(y) < 2 ** 16:
    y += [val] * length; val, length = 1 - val, 2 * length
s, means = 0, []
for n, t in enumerate(y, 1):
    s += t; means.append(s / n)
print("liminf and limsup of Cesaro means for doubling blocks, late range:",
      round(min(means[2 ** 12:]), 3), round(max(means[2 ** 12:]), 3))

admissible values of F(0, 0, 1): [-1.00, 1.00]
c = -1.00: max over grid of F(x) - p(x) with F = x1 + x2 + c x3 is 0.0
c =  0.00: max over grid of F(x) - p(x) with F = x1 + x2 + c x3 is 0.0
c =  1.00: max over grid of F(x) - p(x) with F = x1 + x2 + c x3 is 0.0
Cesaro mean of (1,0,1,0,...) after   10 terms: 0.5000
Cesaro mean of (1,0,1,0,...) after  100 terms: 0.5000
Cesaro mean of (1,0,1,0,...) after 2000 terms: 0.5000
liminf and limsup of Cesaro means for doubling blocks, late range: 0.333 0.667

In the first computation the extension \(F(x) = x_1 + x_2 + c x_3\) satisfies \(F \le \|\cdot\|_1\) exactly when \(|c| \le 1\), and the grid check confirms that the endpoints work. In the second, a Banach limit must give \(\frac{1}{2}\) to the alternating sequence. For the sequence of blocks of doubling length, the Cesàro means oscillate between about \(\frac{1}{3}\) and \(\frac{2}{3}\), and different Banach limits can assign it different values in that range, because the defining inequality \(L \le p\) only bounds \(L\) by the upper limit of the means.