5
$\begingroup$

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.

4 Answers 4

2

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

  • 0
    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.2012-02-05
  • 0
    Nice observation indeed. Thanks.2012-02-05
1

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.

  • 0
    What is $\mathbb N^*$? and what is $E$ please?2012-02-04
  • 0
    $\mathbb N^*$ is the set of integers which are greater than $1$, and $E$ should be $X$.2012-02-04
  • 1
    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.2012-02-04
  • 0
    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.2012-02-05
  • 0
    By the way, I corrected $E$ to $X$ and formatted the $\LaTeX$ (IMHO) better.2012-02-05
  • 0
    And in your comment above, I presume you mean $\mathbb{N}^*$ to be the set of all integers *greater than or equal to* 1?2012-02-05
  • 0
    @NateEldredge indeed, what I did works for continuous linear functional (I red too fast the question).2012-02-05
1

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.

  • 1
    Why not? not by a *continuous* functional, but by some functional? I think you can extend the "limit" functional to do the job.2012-02-04
  • 0
    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.2012-02-04
  • 0
    @Patrick $c_{00}$ is the set of finitely supported sequences (the coordinates are all 0 after some point).2012-02-04
  • 0
    @KotelKanim You are right this solution holds for continuous functionals.2012-02-04
  • 0
    @David : Thanks. Now everything makes more sense. =)2012-02-04
0

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.

  • 2
    They can be weakly separated2012-02-04
  • 1
    In fact two closed disjoint subsets in a finite dimensional space can be weakly separated.2012-02-04