Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
Could you be a bit more precise about what you want? There are two slightly different versions of the separation theorem that I know of: in one, you can strictly separate two disjoint nonempty compact convexes, in the sense that the sup of the real part of the functional over one body is strictly less than the inf of the real part of the functional over the other body; but there's also a version where you only know that the inf of Re $\psi$ over one body is strictly greater than Re $\psi(x)$ for each $x$ in the other body. –  Yemon Choi Sep 2 '10 at 22:41
1  
Of course, strict separation can fail for general disjoint convex subsets of ${\mathbb R}^2$, so I guess you are asking for something else... –  Yemon Choi Sep 2 '10 at 22:43
    
Hum, I just read the part where you said you want a normed linear space; in that case my example below obviously doesn't work. But my impression has always been that the interior point condition is to rule out the non locally convex case. Can you actually state the version of the separation theorem you are looking at and be even more precise about what you want? (In particular, in the locally convex case, to get any example you will need also $K_1$ and $K_2$ to be non-compact and non closed at the very least.) –  Willie Wong Sep 2 '10 at 23:28

5 Answers 5

up vote 30 down vote accepted

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.

share|improve this answer
    
Nice example feja! I was hoping for something a bit more 'geometric' but I suppose considering one needs to work in infinite dimensions this is inevitable. Thanks again! –  Dorian Sep 3 '10 at 0:58
    
Note that not only is neither of the sets open, the second (bigger) set is also noncompact and nonclosed. –  Willie Wong Sep 3 '10 at 1:02

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

share|improve this answer
    
How can you create a dense convex subspace though? I suppose the previous example shows this but all of my geometric intuition tells me that convexity + density should imply it's closed. –  Dorian Sep 4 '10 at 15:22
    
all subspaces are convex. –  Dan Petersen Sep 4 '10 at 19:13

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 = L2(μ). Then let,

  • A be the set of f ∈ L2(μ) with f ≥ 1 almost everywhere.
  • B be the one dimensional subspace of f ∈ L2(μ) 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 ∈ L2 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.

share|improve this answer
    
Nice! Thank you George! –  Dorian Sep 4 '10 at 15:28

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$.

share|improve this answer
    
Of course, a side remark is that the only convex open sets in the above-mentioned space is the entire space... –  Willie Wong Sep 2 '10 at 23:04
    
Hey this is a nice example. I was hoping for a counter example which does not depend on the hypotheses of the space however. Isn't there a simple example where those hypotheses are not satisfied and there fails to exist a linear functional? –  Dorian Sep 2 '10 at 23:43

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.