A counter example to Hahn-Banach separation theorem of convex sets. - MathOverflow

A counter example to Hahn-Banach separation theorem of convex sets.

2010-09-02T22:32:37Z

I'm trying to understand the necessity for the assumption in the Hahn-Banach theorem for one of the convex sets to have an interior point. The other way I've seen the theorem stated, one set is closed and the other one compact. My goal is to find a counter example when these hypotheses are not satisfied but the sets are still convex and disjoint. So here is my question:

Question: I would like a counter example to the Hahn-Banach separation theorem for convex sets when the two convex sets are disjoint but neither has an interior point. It is trivial to find a counter example for the strict separation but this is not what I want. I would like an example (in finite or infinite dimensions) such that we fail to have any separation of the two convex sets at all.

In other words, we have $K_1$ and $K_2$ with $K_1 \cap K_2 = \emptyset$ with both $K_1$ and $K_2$ convex belonging to some normed linear space $X$. I would like an explicit example where there is no linear functional $l \in X^*$ such that $\sup_{x \in K_1} l(x) \leq \inf_{z \in K_2} l(z)$.

I'm quite sure that a counter example cannot arise in finite dimensions since I think you can get rid of these hypotheses in $\mathbb{R}^n$. I'm not positive though.

Answer by Willie Wong for A counter example to Hahn-Banach separation theorem of convex sets.

2010-09-02T23:00:33Z

See http://en.wikipedia.org/wiki/Locally_convex_topological_vector_space#Nonexamples_of_locally_convex_spaces

Recalling that the second version of Hahn-Banach theorem you stated uses locally convex spaces, it is natural to look for your desired counter example in a topological vector space that is not locally convex.

Now consider the space $L^p[0,1]$ with $0<p<1$ , it is not locally convex, and the only continuous linear functional on it is the 0 functional. So no two points in fact can be separated by a continuous linear functional in $L^p$.

Answer by fedja for A counter example to Hahn-Banach separation theorem of convex sets.

2010-09-03T00:37:55Z

Here is a simple example of a linear space and 2 disjoint convex sets such that there is no linear functional separating the sets. Note that the notions of convexity and linear functional do not require any norm or whatever else. You can introduce them, if you want, but they are completely external to the problem.

The usual trick with taking the difference of the sets shows that it is enough to assume that one set is a point, say, the origin. Now we want to design a convex set $K$ not containing the origin such that the only linear functional $\ell$ that is non-negative on this set is $0$. To this end, take the space $X$ to be the space of all real sequences with finitely many non-zero terms and let $K$ be the set of all such sequences whose last non-zero element is positive. Now, if $x\in X$, choose $y$ to be any sequence whose last non-zero element is $1$ and lies beyond the last non-zero element in $x$. Then, for every $\delta>0$, both $x+\delta y$ and $-x+\delta y$ are in $K$, so $\pm \ell(x)+\delta \ell(y)\ge 0$ with any $\delta>0$ whence $\ell(x)=0$. Thus $\ell$ vanishes identically.

Answer by Bill Johnson for A counter example to Hahn-Banach separation theorem of convex sets.

2010-09-03T18:37:14Z

Take $K_1$ to be a proper dense subspace and $K_2$ the translate of $K_1$ by a vector not in $K_1$.

Answer by George Lowther for A counter example to Hahn-Banach separation theorem of convex sets.

2010-09-04T03:24:11Z

The Hahn-Banach theorem for a locally convex space X says that for any disjoint pair of convex sets A, B with A closed and B compact, there is a linear functional $l\in X^*$ separating A and B. So, it would be nice to have a counterexample where both A and B are closed, but not compact. As no-one has posted such an example, I'll do that now, where the space X is a separable Hilbert space. In fact, as with fedjas example, there will be no separating linear functionals at all, not even noncontinuous ones.

Take μ to be the Lebesgue measure on the unit interval [0,1] and X = L²(μ). Then let,

A be the set of f ∈ L²(μ) with f ≥ 1 almost everywhere.
B be the one dimensional subspace of f ∈ L²(μ) of the form f(x) = λx for real λ.

These can't be separated by a linear function $l\colon X\to\mathbb{R}$. A similar argument to fedja's can be used here, although it necessarily makes use of the topology. Suppose that $l(f)\ge l(g)$ for all f in A and g in B. Then $l$ is nonnegative on the set A-B of f ∈ L² satisfying $f(x)\ge 1-\lambda x$ for some λ. For any $f\in L^2$ and for each $n\in\mathbb{N}$, choose $\lambda_n$ large enough that $\Vert(1-\lambda_nx+\vert f\vert)_+\Vert_2\le 4^{-n}$ and set $g=\sum_n 2^n(1-\lambda_n x+\vert f\vert)_+\in L^2$. This satisfies $\pm f+2^{-n}g\ge1-\lambda_nx$, so $\pm l(f)+2^{-n}l(g)\ge 0$ and, therefore, $l$ vanishes everywhere.

If you prefer, you can create a similar example in $\ell^2$ by letting $A=\{x\in\ell^2\colon x_n\ge n^{-1}\}$ and B be the one dimensional subspace of $x\in\ell^2$ with $x_n=\lambda n^{-2}$ for real λ.

Note: A and B here are necessarily both unbounded sets, otherwise one would be weakly compact and the Hahn-Banach theorem would apply.

Answer by Maciej S. for A counter example to Hahn-Banach separation theorem of convex sets.

2011-03-09T22:00:05Z

A counterexample can be given even if both set are assumed to be closed, for any non-reflexive Banach space. See a proof of Klee's theorem

http://www.johndcook.com/SeparationOfConvexSets.pdf

Since in a reflexive space there exists a separation of two closed convex sets provided that one of them is bounded, I think above result is the best answer on your question.