# Separation theorem

Is it true that given a real vector space $X$ and two disjoint convex sets $A,B\subseteq X$, there is always a linear functional that (weakly) separates them? I.e., is there a non-zero linear functional $\phi\colon X\to \mathbb R$ and a $\gamma\in\mathbb R$, such that $\phi(a)\le \gamma \le \phi (b)$ for all $a\in A$ and $b\in B$? If not, can you give a counterexample?

I know the statement is true if you add the aditional hypothesis that at least one of the sets has an internal point. This follows from the Hahn-Banach theorem using the Minkowski functional, but I was wandering whether this hypothesis is necessary.

-

The answer is no. here is an elaborated counterexample:

Let $X=c_{00}$ (the space of real valued sequences which are eventually zero).

Let $A$ tbe he subset of $X$ of all sequences whose last non-zero entry is positive (the zero sequence is not in $A$).

Let $B= \{0\}$.

Clearly $A\cap B=\varnothing$ and both $A$ and $B$ are convex, so the hypothesis is satisfied.

Now, suppose we have a separating linear functional $\phi:X\to \mathbb R$. It is clearly zero on $B$. Suppose we had $a\in A$, such that $\phi (a)>0$. Let $N$ be the index of the last non zero entry of $a$. By modifying slightly the $N+1$ entry of $-a$ we will get an element $a'\in A$, such that $\phi (a')<0$ contradicting the separation property. The same holds for if we had $a\in A$ with $\phi (a)<0$. Therefore, $\phi$ must be zero on $A$ and hence on $X$.

-
Very nice example. Here's another way to see that it works. Let $\{e_i\}$ be the standard basis vectors for $c_{00}$. If $\phi$ is a nonzero linear functional then $\phi(e_n) \ne 0$ for some $n$. For any $a \in \mathbb{R}$ we have $a e_n + e_{n+1} \in A$, so in fact $\phi(A) = \mathbb{R}$, and we see that $A$ cannot be weakly separated from any set. – Nate Eldredge Feb 5 '12 at 14:20
Nice observation indeed. Thanks. – KotelKanim Feb 5 '12 at 15:08

Consider $X=l_2(\mathbb{N})$, take $$A=c_{00}(\mathbb{N})$$ $$B=A+(2^0,2^{-1},\ldots,2^{-n},\ldots)$$ It is easy to check that $A$, $B$ are disjoint convex dense subsets with empty interior. Since they are dense in $X$, they can not be separated.

-
Why not? not by a continuous functional, but by some functional? I think you can extend the "limit" functional to do the job. – KotelKanim Feb 4 '12 at 22:28
How can you even have two disjoint dense convex subsets of a vector space? That just seems wrong to me. I'm mostly saying this because I don't know what $c_{00}(\mathbb N)$ stands for, so I'm just wondering. – Patrick Da Silva Feb 4 '12 at 22:50
@Patrick $c_{00}$ is the set of finitely supported sequences (the coordinates are all 0 after some point). – David Mitra Feb 4 '12 at 22:53
@KotelKanim You are right this solution holds for continuous functionals. – Norbert Feb 4 '12 at 22:56
@David : Thanks. Now everything makes more sense. =) – Patrick Da Silva Feb 4 '12 at 22:59

The answer is no in general. Put $X:=\ell^1(\mathbb N^*)$, \begin{align} A_0 &:=\{x=\{x_n\}\in X, \forall n\geq 1, x_{2n}=0\},\\ B &:=\{x=\{x_n\}\in X, \forall n\geq 1, x_{2n}=2^{-n}x_{2n-1}\}.\end{align}

Let $c\in X$ given by $c_{2n-1}=0$ and $c_{2n}=2^{-n}$. Then $c\notin A_0+B$, and putting $A:=A_0-c$, we note that $A$ and $B$ are two closed disjoint subset which cannot be weakly separated.

-
What is $\mathbb N^*$? and what is $E$ please? – KotelKanim Feb 4 '12 at 22:30
$\mathbb N^*$ is the set of integers which are greater than $1$, and $E$ should be $X$. – Davide Giraudo Feb 4 '12 at 22:31
I think I've got it, but I would still appreciate a lot if you could sketch the argument for why they can't be separated by a functional. – KotelKanim Feb 4 '12 at 22:54
I don't see that this works. If I'm reading the definition correctly, $A_0$ and $B$ are both linear subspaces of $X$. By Zorn's lemma we can find a linear functional $\phi$ with $\phi(A_0+B)=0$ but $\phi(c)=1$. Then $\phi(B)=0$ but $\phi(A)=-1$ so $A,B$ are separated. – Nate Eldredge Feb 5 '12 at 3:10
By the way, I corrected $E$ to $X$ and formatted the $\LaTeX$ (IMHO) better. – Nate Eldredge Feb 5 '12 at 3:19

You can find a counterexample in $\mathbb R^2$. Let $A=\{(x,y): y\leq 0\}$ and let $B$ be the closed convex set above the graph of $e^x$. Since the $d(A,B)=0$ they can not be separated.

-
They can be weakly separated – Norbert Feb 4 '12 at 22:23
In fact two closed disjoint subsets in a finite dimensional space can be weakly separated. – Davide Giraudo Feb 4 '12 at 22:26