From Hahn-Banach to Separating Theorems

Definition 1 (Positive sublinear functional). Let \(X\) be a vector space. A \(p:X\to{\rm I\!R}\) is called a positive sublinear functional (PSLF) if the following conditions are satisfied

1. \(p\) is nonnegative valued on \(X\)
2. \(p\) is positively homogeneous on \(X\), that is, \(p(\lambda x) = \lambda p(x)\) for all \(\lambda\geq 0\) and \(x\in X\)
3. \(p\) is sublinear, that is, \(p(x+y) \leq p(x) + p(y)\)

Proposition 2 (Continuity of PSLFs). Let \(X\) be a topological vector space (TVS) and \(p:X\to{\rm I\!R}\) is an PSLF. Then, the following are equivalent

1. \(p\) is continuous
2. \(p\) is continuous at \(0\)
3. \(p\) is bounded in a neighbourhood of \(0\)

Proof. It is obvious that 1 implies 2, which implies 3. We shall prove that 3 implies 2. Let \(V\) be a neighbourhood of \(0\) and \(p(V)\) is bounded, i.e., \(p(V) \subseteq (-M, M)\) for some \(M>0\). For \(x\in V\) we have that

$$p\left(\tfrac{\epsilon}{M}x\right){}={}\tfrac{\epsilon}{M} p(x) \in (-\epsilon, \epsilon),$$

which implies that

$$p\left(\tfrac{\epsilon}{M}V\right) \subseteq (-\epsilon, \epsilon),$$

so, \(p\) is continuous at \(0\).

Let us now show that 2 implies 1. Let \(p\) be continuous at \(0\) and \(x_0 \in X\). Let \(\epsilon > 0\). Then, there is \(V\), balanced neighbourhood of \(0\) such that \(p(V) \subseteq (-\epsilon, \epsilon)\). We will show that \(p(x_0 + V) \subseteq (p(x_0)-\epsilon, p(x_0) + \epsilon)\).

By taking \(v\in V\) we see that \(p(x_0 + v) \leq p(x_0) + p(v) < p(x_0) + \epsilon\). Likewise, \(p(x_0+v) = p(x_0 - (-v)) \geq p(x_0) - p(-v) > p(x_0) - \epsilon\). This completes the proof. \(\blacksquare\)

Proposition 3 (PSLFs have convex sublevel sets). Let \(X\) be a TVS and \(p:X\to{\rm I\!R}\) is an PSLF. Then, its sublevel sets, \(\{x: p(x) \leq a\}\), are convex.

Proposition 4 (Continuity of linear functionals). Let \(X\) be a TVS, \(p:X\to{\rm I\!R}\) is an PSLF, \(A: X\to{\rm I\!R}\) is linear, and

$$A(x) \leq p(x),$$

for all \(x\in X\). If \(p\) is continuous, then \(A\) is continuous.

Proof. To show that \(A\) is continuous, it suffices to show that for every \(\epsilon > 0\), there is an open neighbourhood of \(0_X\) such that \(A(V) \subseteq (-\epsilon, \epsilon)\). Since \(p\) is continuous (at \(0\)), there is a balanced neighbourhood of \(0\) such that \(p(V) \subseteq (-\epsilon, \epsilon)\).

For \(x \in V\) we have

$$A(x) \leq p(x) < \epsilon.$$

Moreover,

$$A(x) = A(-(-x)) = -A(-x) \geq -p(-x) > -\epsilon,$$

where we used the fact that \(V\) is balanced, so \(x\in V\) implies \(-x\in V\). We have shown that \(A(V) \subseteq (-\epsilon, \epsilon)\). \(\blacksquare\)

Definition 5 (Partial order). Let \(A\) be a nonempty set. A relation, \(\leq\), is a partial order on \(A\) if it satisfies the following properties

1. (Reflexivity) \(a \leq a\) for all \(a\in A\)
2. (Antisymmetry) \(a \leq b\) and \(b \leq a\) implies \(a = b\) for all \(a, b\in A\)
3. (Transitivity) \(a \leq b\) and \(b \leq c\) implies that \(a \leq c\) for all \(a, b, c \in A\)

Definition 6 (Chain). Let \(A\) be a nonempty set equipped with a partial order \(\leq\). A set \(B\ subseteq A\) is said to be a chain if for every \(a,b\in B\), either \(a\leq b\) or \(b\leq a\).

Definition 7 (Maximal element). Let \(A\) be a nonempty set equipped with a partial order \(\leq\). An element \(M \in A\) is said to be a maximal element of \(A\) if for all \(x\in A\),

$$m \leq x \Rightarrow x = m.$$

Definition 8 (Upper boun of a chain). Let \(A\) be a nonempty set equipped with a partial order \(\leq\) and let \(B\subseteq A\) be a chain. An element \(m \in A\) is said to be an upper bound of the chain if \(x \leq m\) for every \(x\in B\).

Lemma 9 (Zorn's lemma). Let \(A\) be a nonempty set equipped with a partial order \(\leq\) and every chain has an upper bound. Then, \(A\) has a maximal element.

Theorem 10 (Hahn-Banach Theorem). Let \(X\) be a TVS and \(p: X \to {\rm I\!R}\) is an PSLFs. Let \(Y\subseteq X\) be a subspace of \(X\) and a linear functional \(f:Y\to{\rm I\!R}\) is such that

$$f(y) \leq p(y),$$

for all \(y\in Y\). Then, there exists a linear functional \(\hat{f}: X \to {\rm I\!R}\) such that

1. \(\hat{f}\) extends \(f\), i.e., \(\hat{f}(y) = f(y)\) for all \(y\in Y\)
2. \(\hat{f}(x) \leq p(x)\) for all \(x \in X\)

Proof. We will prove the Hahn-Banach theorem using Zorn's lemma. Hereafter the notation "\(Y \sqsubseteq Z\) means "\(Y\) is a linear subspace of \(Z\)" (both \(Y\) and \(Z\)s are linear spaces). We start by defining the set

$$A = \left\{(Z, f_Z) : \begin{array}{l}Y \sqsubseteq Z \sqsubseteq X, \\ f_Z: \text{ linear}, \\ f_Z | Y = f, \\ f_Z(z) \leq p(z), \forall z\in Z \end{array}\right\}$$

We know that \((Y, f) \in A\). We introduce a partial order \(\leq\) on \(A\) where

$$(Z, f_Z) \leq (Z', f_{Z'}),$$

if and only if \(Z \sqsubseteq Z'\) and \(f_{Z} \leq f_{Z'}|Z \); that is, \(f_Z(x) \leq f_{Z'}(x)\) for all \(x\in Z\).

Let \(B = \{(Z_i, f_{Z,i})\}_{i\in I}\) be a chain in \(A\). The following element of \(A\) is an upper bound of \(B\):

$$\left(\bigcup_{i\in I}Z_i, \bigcup_{i\in I}f_{Z,i}\right),$$

where the union of functions is meant in the sense of the union of their graphs.

From Zorn's lemma, \(A\) has a maximal element, \((\bar{Z}, \bar{f})\). We will show tha that \(\bar{Z} = X\).

If not, there is a \(z_0 \in X \setminus \bar{Z}\) and we can extend \(\bar{Z}\) to a space \(\bar{Z}' = \bar{Z} \oplus {\rm I\!R}z_0\). Take \(x, y \in \bar{Z}\). Then,

$$\begin{aligned}&f_{\bar{Z}}(x-y) \leq p(x-y)\\ {}\Leftrightarrow{}&f_{\bar{Z}}(x) - f_{\bar{Z}}(y) \leq p(x-z_0) + p(z_0 - y)\\{}\Leftrightarrow{}&f_{\bar{Z}}(x) - p(x-z_0) \leq f_{\bar{Z}}(y) - p(z_0 - y),\end{aligned}$$

for all \(x, y \in \bar{Z}\). Now take a supremum on the LHS and an infimum on the RHS

$$ \sup_{x\in \bar{Z}}f_{\bar{Z}}(x) - p(x-z_0) \leq \inf_{y\in \bar{Z}} f_{\bar{Z}}(y) - p(z_0 - y). $$

Therefore, there is an \(a\) in between

$$ \sup_{x\in \bar{Z}}f_{\bar{Z}}(x) - p(x-z_0) \leq a \leq \inf_{y\in \bar{Z}} f_{\bar{Z}}(y) - p(z_0 - y).\tag{$*$} $$

We can now extend \(\bar{f}\) (which is defined on \(\bar{Z}\)) to a \(\bar{f}'\) defined on \(\bar{Z}'\). All \(z' \in \bar{Z}'\) can be written as \(z' = z + \lambda z_0\) for some \(\lambda \in {\rm I\!R}\). We define

$$\bar{f}'(z') = \bar{f}'(z + \lambda z_0) = \bar{f}(z) + \lambda a.$$

It suffices to show that \(\bar{f}' \leq p\) on \(\bar{Z}'\). Equivalently, we need to show that

$$\begin{aligned}\bar{f}'(z') \leq p(z') \Leftrightarrow{}& \bar{f}'(z+ \lambda z_0) \leq p(z + \lambda z_0) \\ \Leftrightarrow{}& \bar{f}(z) + \lambda a \leq p(z+\lambda z_0),\tag{1}\end{aligned}$$

for all \(z\in \bar{Z}\) and \(\lambda \in {\rm I\!R}\).

We consider three cases. Firstly, if \(\lambda = 0\), the condition of Equation (1) is satisfied trivially (you can check). If \(\lambda > 0\), Equation (1) is equivalent to

$$\begin{aligned} a {}\leq{}& \tfrac{1}{\lambda}p(z+\lambda z_0) - \tfrac{1}{\lambda}\bar{f}(z) \\ {}={}& p\left(\frac{z}{\lambda}+ z_0\right) +\bar{f}\left(- \frac{z}{\lambda}\right),\end{aligned}$$

which is true due to Equation (\(*\)).

Likewise, if \(\lambda < 0\) Equation (1) is equivalent to

$$a \geq -p\left(-\frac{z}{\lambda}-z_0\right) + \bar{f}\left(-\frac{z}{\lambda}\right),$$

which is true due to Equation (\(*\)).

We have shown that \((\bar{Z}' ,\bar{f}')\) is an element of \(A\) and it is \((\bar{Z}' ,\bar{f}') > (\bar{Z}, \bar{f})\). This is a contradiction because \((\bar{Z}, \bar{f})\) is maximal.

Definition 11 (Minkowski functional). Let \(X\) be a TVS and \(K\subseteq X\) is a convex set that contains zero in its interior (\(0 \in \mathrm{int}\; K\)). We define the Minkowski functional as

$$p_K(x) = \inf \left\{ \lambda > 0 : \frac{x}{\lambda} \in K\right\} = \inf \left\{ \lambda > 0 : x \in \lambda K\right\}.$$

Proposition 12 (Minkowski functional is continuous PSLF). Let \(X\) be a TVS and \(K\subseteq X\) is a convex set that contains zero in its interior (\(0 \in \mathrm{int}\; K\)), and let \(p_K\) be the Minkowski functional of \(K\). Then \(p_K\) is a continuous PSLF.

Proof. Clearly, \(p_K \geq 0\). We will show that \(p_K\) is positively homogeneous. Let \(c > 0\). Then

$$p_K(c x) = \inf\left\{\lambda > 0 : \frac{cx}{\lambda} \in K\right\} = \inf\left\{ \lambda > 0 : \frac{x}{\tfrac{\lambda}{c}}\right\} = \ldots = c p_K(x).$$

It is easy to see that \(p_K(0) = 0.\)

Next, we will show that \(p_K\) is sublinear. Take \(\epsilon > 0\) and choose \(\lambda_1, \lambda_2 > 0\) such that

$$\begin{aligned}p_K(x) < \lambda_1 < p_K(x) + \epsilon, \\ p_K(y) < \lambda_2 < p_K(y) + \epsilon.\end{aligned}$$

As a result we have that \(x/\lambda_1 \in K\) and \(y/\lambda_2 \in K\).

It suffices to show that \(p_K(x+y) \leq \lambda_1 + \lambda_2\). We have

$$\frac{x+y}{\lambda_1 + \lambda_2} = \frac{\lambda_1}{\lambda_1 + \lambda_2}\frac{x}{\lambda_1} + \frac{\lambda_2}{\lambda_1 + \lambda_2}\frac{y}{\lambda_2} \in K.$$

Therefore, \(p_K(x+y) \leq \lambda_1 + \lambda_2\) and taking \(\epsilon{}\to{}0\), it follows that \(p_K(x+y) \leq p_K(x) + p_K(y).\)

Lastly, we will show that \(p_K\) is continuous using Proposition 2. For \(x\in K\), \(x/1 \in K\), so \(0 \leq p_K(x) \leq 1\), so it is bounded in \(\mathrm{int}\; K\), which is an open neighbourhood of zero, therefore, it is continuous. \(\blacksquare\)

Proposition 13 (Topological properties of convex sets). Let \(X\) be a TVS and \(K\) is a convex set with \(0 \in \mathrm{int}\; K\) and let \(p_K\) be the Minkowski functional of \(K\). Then,

1. \(\mathrm{int}\; K = [p_K < 1]\)
2. \(\mathrm{cl}\; K = [p_K \leq 1]\)
3. \(\partial K = [p_K {}={} 1]\)

Proof. 1. We have that \([p_K < 1] = p_K^{-1}((-\infty, 1))\) and since \(p_K\) is continuous (Prop 12), it is open. Since \(K\) is convex and contains zero in its interior, \(\lambda K \subseteq K\) for all \(0<\lambda < 1\). This observation allows us to see that \([p_K < 1] \subseteq K\). Since \([p_K < 1]\) is an open set inside \(K\), we conclude that

$$[p_K < 1] \subseteq \mathrm{int}\; K.$$

The reason for this is that \(\mathrm{int}\; K\) is the largest open set inside \(K\). We then need to show that \([p_K < 1] \supseteq \mathrm{int}\; K\).

Take \(x_0 \in \mathrm{int}\; K\). We will use the fact that the scalar multiplication is continuous: the scalar multiplication maps

$${}\cdot{}: (1, x_0) \mapsto x_0 \in \mathrm{int}\; K,$$

where \(\mathrm{int}\; K\) is open. From the continuity of the scalar multiplication, there is \(\epsilon > 0\) such that

$$(1-\epsilon, 1+\epsilon) x_0 \subseteq \mathrm{int}\; K.$$

Choosing

$$\lambda = \frac{1}{1+\tfrac{\epsilon}{2}},$$

we have \(x_0/\lambda \in K\), therefore, \(p_K(x_0) < 1\) \(\Box\).

2. Firstly \([p_K \leq 1] = p_K^{-1}((-\infty, 1])\) is closed since it is the inverse image of the closed set \((-\infty, 1]\) through the continuous function \(p_K\). Next, if \(x\in K\),

$$p_K(x) = \inf\{\lambda>0 {}:{} x/\lambda \in K\} \leq 1,$$

so,

$$K \subseteq \underbrace{[p_K \leq 1]}_{\text{closed}} \Rightarrow \mathrm{cl}\; K \subseteq [p_K \leq 1].$$

We will show that \([p_K \leq 1] \subseteq \mathrm{cl}\; K\). Take \(\tilde{x}\in [p_K \leq 1]\); equivalently \(p_{K}(\tilde{x}) \leq 1\). Take a sequence of scalars \((\lambda_{\nu})_{\rm I\!N}\) with \(0 < \lambda_\nu < 1\) and \(\lambda_\nu \to 1^{-}\). Then

$$\lambda_\nu \tilde{x} \in K,$$

for all \(\nu \in {\rm I\!N}\). So, \(\lim_\nu \lambda_\nu x = x \in \mathrm{cl}\;K\). \(\Box\)

Proposition 14 (Minkowski functional of convex set). Let \(X\) be a TVS and \(K\) is a convex set with \(0 \in \mathrm{int}\; K\). Then,

$$p_{\mathrm{int}\; K} = p_{K} = p_{\mathrm{cl}\; K}.$$

Proof. We will start by showing that \(p_{\mathrm{int}\; K} = p_{K}\). Since \(\mathrm{int}\; K \subseteq K\), we have \(p_{\mathrm{int}\; K} \geq p_{K}\). We will try to end up in a contradition by assuming that there is \(s\) such that

$$p_{\mathrm{int}\; K}(x) > s > p_{K}(x)$$

for some \(x\). Then, \(p_{\mathrm{int}\; K}(x/s) > 1\). However,

$$p_{K}\left(\frac{x}{s}\right) \Rightarrow \frac{x}{s} \in \mathrm{int}\; K \Rightarrow p_{\mathrm{int}\; K}\left(\frac{x}{s}\right) \leq 1,$$

which is a contradiction. Similary we can prove that \(p_{K} = p_{\mathrm{cl}\; K}.\) \(\blacksquare\)

Corollary 15 (Topological property of convex sets). Let \(X\) be a TVS and \(K\) is a convex set with \(0 \in \mathrm{int}\; K\). Then,

$$\mathrm{cl}\; \mathrm{int}\; K {}={} \mathrm{cl}\; K.$$

Proof. We have

$$\mathrm{cl}\; \mathrm{int}\; K = [p_{\mathrm{int}\; K} \leq 1] = [p_K \leq 1] = \mathrm{cl}\; K,$$

which completes the proof. \(\blacksquare\)

Theorem 16 (First separating theorem). Let \(X\) be a TVS and \(K\) is a convex set with a nonempty interior. Let \(x_0 \notin \mathrm{int}\; K\). Then there is a nonzero continuous linear functional, \(f: X \to {\rm I\!R}\), that separates \(x_0\) from \(K\), that is

$$\sup f(K) {}\leq{} f(x_0).$$

Proof. Without loss of generality we shall assume that \(0\in \mathrm{int}\; K\). If not, we can simply take a point \(\bar{x}\) and use the change of variables \(x \mapsto x - \bar{x}\), i.e., to move the set so that zero is inside its interior.

Since \(x_0 \notin \mathrm{int}; K\), we have from Proposition 13 that \(p_K(x_0) \geq 1\).

On the space \(Y = {\rm I\!R}x_0\) we define the function

$$g(y) = g(\lambda x_0) = \lambda p_K(x_0).$$

It is easy to see that \(g(y) \leq p_K(y)\) for all \(y\in R\) and you see where this is going...

From the Hahn-Banach theorem, there is a linear functional, \(f\), that extends \(g\) to \(X\) such that \(f(x) \leq p_K(x)\) for all \(x\in X\).

Proposition 4 implies that \(f\) is continuous on \(X\) since \(p_K\) is a continuous PSLF as we know from Proposition 12.

We have that

$$f(x_0){}={}g(x_0){}={}p_K(x_0)\geq 1,$$

so, \(f\) is a nonzero linear functional, and for all \(x\in K\), \(p_K(x) \leq 1\), therefore, \(f(x) \leq 1\).

This completes the proof. \(\blacksquare\)

Theorem 17 (Second separating theorem). Let \(X\) be a TVS and \(K, L\) be two convex sets, \(K\) has a nonempty interior and \(\mathrm{int}\; K \cap L = \emptyset\). Then there is a nonzero continuous linear functional, \(f: X \to {\rm I\!R}\), that separates \(K\) from \(L\), that is

$$\sup f(K) {}\leq{} \inf f(L).$$

Proof. The set \(\mathrm{int}\; K - L\) is open because

$$\mathrm{int}\; K - L = \bigcup_{l \in L}(\mathrm{int}\; K - l),$$

so it is a union of open sets.

The set is convex because it is the Minkowski sum of two open sets, and \(0\notin \mathrm{int}\; K - L\). As a result, from the first separating theorem (Theorem 16), there is a nonzero continuous linear functional, \(f\), that separates \(0\) from \(\mathrm{int}\; K - L\), that is

$$\begin{aligned}&\sup f(\mathrm{int}\; K - L) \leq f(0) = 0\\\Rightarrow{}&\sup f(\mathrm{cl}\; \mathrm{int}\; K) \leq \inf f(L),\end{aligned}$$

but since \(K\) is convex, \(\mathrm{cl}\; \mathrm{int}\; K = K\), so

$$\sup f(K) \leq \inf f(L).$$

This completes the proof. \(\blacksquare\)

Theorem 18 (Third separating theorem). Let \(X\) be a locally convex TVS, \(L\) is a nonempty closed convex set, \(K\) is a nonempty compact convex set and

$$K \cap L = \emptyset.$$

Then, there is a linear continuous functional \(f:X\to{\rm I\!R}\) that separates the two sets strictly.

Proof. Since \(K \cap L = \emptyset\), we have that \(0 \notin K - L\).

Claim. We will show that \(K-L\) is closed.

Equivalently, we will show that its complement is open. To that end, for \(x \notin K - L\) it suffices to find a neighbourhood of 0 which is symmetric (see the above remark) such that

$$\underbrace{(x+V)}_{\text{neigh. of } x} \cap (K - L) = \emptyset.$$

Equivalently, it suffices to find \(V\) such that

$$(K+V) \cap (x + L) = \emptyset.$$

Note: in fact it should be \(K-V\), but \(V\) is symmetric.

Since \(K \cap (x+L) = \emptyset\) and \(x+L\) is closed, for all \(y \in K\) there is a neighbourhood of zero, \(V_y\), such that \((y+V_y) \cap (x + L) = \emptyset\). Then, we can determine \(U_y \ni 0\) such that \(U_y + U_y \subseteq V_y\). Now consider the following cover of \(K\)

$$K \subseteq \bigcup_{y \in K}(y + U_y).$$

Since \(K\) is compact, there is a finite subcover, i.e., there are \(y_1, \ldots, y_n\) such that

$$K \subseteq \bigcup_{i=1}^{n}(y_i + U_{y_i}).$$

Define the set

$$U = \bigcap_{i=1}^{n}U_{y_i},$$

which is an open set that contains \(0\). For every \(y\in K\) there is \(i\) such that \(y \in y_i + U_{y_i}\). Then,

$$y + U \subseteq y_i + U_i + U \subseteq y_i + U_i + U_i \subseteq y_i + V_{y_i}.$$

This means that \((y+U) \cap (x+L) \subseteq (y_i + V_{y_i}) \cap (x+L) = \emptyset.\) This proves the claim.

Since \(K-L\) is closed and \(0 \notin K-L\) there is a convex symmetric neighbourhood \(V\ni 0\) such that \(V \cap (K-L) = \emptyset\). Using Theorem 17 we can separate \(V\) from \(K-L\), i.e., there is a nonzero linear continuous \(f: X \to {\rm I\!R}\) such that

$$\sup f(V) \leq \inf f(K-L) = \inf f(K) - \sup f(L).$$

The proof is completed by showing that \(\sup f(V) > 0\). There is an \(x\in X\) with \(f(x) > 0\). There is \(\lambda >0\) such that \(\lambda x \in V\) and \(f(\lambda x) = \lambda f(x) > 0\), so \(\sup f(V) > 0\). $\blacksquare$

Proposition 19 (Representation of convex sets). Let \(X\) be a locally convex TVS, and \(K\) is a nonempty closed convex set. Then \(K\) can be written as the intersection of a famiily of halfspaces.

Proof. Take \(x\notin K\). Since \(\{x\}\) is a compact and convex, from Theorem 18, there is a continuous linear operator, \(f_{x}\) such that \(\sup f_x(K) < s_x < f_x(x)\). Clearly

$$K \subseteq \bigcap_{x\notin K}f_{x}^{-1}((-\infty, s_x]).$$

To show that the above intersection is a subset of \(K\) it suffices to show that if \(x_0 \notin K\), then \(x_0 \notin \bigcap_{x\notin K}f_{x}^{-1}((-\infty, s_x])\), which is immediate. \(\blacksquare\)