# Separation Theorem in Euclidean Space.

I want to show the following:

Let $A,B \subseteq \mathbb{R}^n$ disjoint, nonempty, closed and convex sets. Then there exists a $h \in \mathbb{R}^n$, such that $A$ and $B$ gets separated in the following way: $$\langle b, h \rangle \le \langle a, h \rangle \quad \forall a \in A, b \in B.$$ I have the following proof: Consider $C := B - A$, which is convex too. Because $A$ and $B$ are disjoint, it must be that $0 \notin C$. (*) Then there exists a $h$ such that $\langle c, h \rangle \le 0$ for all $c \in C$ or $\langle c, h \rangle \ge 0$ for all $c \in C$. WLOG let $\langle c, h \rangle \le 0$, then $\langle b - a, h \rangle \le 0$, which means $\langle b, h \rangle - \langle a, h \rangle \le 0$, i.e. $$\langle b, h \rangle \le \langle a, h \rangle.$$

But (*) uses the fact that: For every convex set $X$ and a point $u \notin X$, there exists a $h$ such that $\langle u, h \rangle = 0$ and $\langle x, h \rangle \le 0$ for all $x \in X$ or $\langle x, h \rangle \ge 0$ for all $x \in X$.

Which I feel is geometrically true because the Elements $h$ could be identified with hyperplanes, but I am not sure how to proof this?

-
Do you understand how to identify an element $h \in \mathbb{R}^n$ and a constant $c$ with a hyperplane? It refers to the set of points $x\in \mathbb{R}^n$ such that $< h, x> = c$. For each point, the length of the projection onto vector $h$ will be of length $c/ ||h||$. – Calvin Lin Jan 4 '13 at 18:33
that i know, btw you mean the length of the projection of every point $p$ will be $c / ||p||$. – Stefan Jan 4 '13 at 18:36
The length of the projection of a point $p$ onto the vector $h$ will be $c/||h||$. This comes from the equation of a plane, say $x+2y+3z = 4$. This can be expressed by the dot product as $(x, y, z) \cdot (1, 2, 3) = 4$. – Calvin Lin Jan 4 '13 at 18:43
Well, $A$ and $B$ are closed, but does it follow that $C = B - A$ is closed? Why do you need closed sets anyway? – GEdgar Jan 4 '13 at 18:50
but $c / ||h||$ does not depend on the point, so it would be the same for every point? – Stefan Jan 4 '13 at 19:06

Your comment (*) is a bit off, so I'll go ahead without it.

Firstly, if there exists an $h$ such that $\langle c, h \rangle \le 0$ for all $c\in C$, then $-h$ satisfies $\langle c, -h \rangle \ge 0$ for all $c \in C$. So the two cases are equivalent, and you only need to solve either.

Now, your question is essentially reduced to building a hyperplane through the origin for which your convex set $X$ falls entirely on one side. A good guess would be to take the plane perpendicular to some point of the set (which would then become your $h$), but which? Try taking $h$ to be the closest point of $X$ to the origin. Try proving that if there was some point of $X$ on the other side of the hyperplane, then convexity would force another point to be closer to the origin than $h$.

-
The first paragraph is falsely stated (even in the question). It holds with a constant $c$ replacing $0$, which is the separating hyperplane theorem. We can't guarantee that the hyperplane will pass through the origin, since the origin could be contained within one of the sets. – Calvin Lin Jan 4 '13 at 20:11
@CalvinLin: but we're only applying it to $C = A - B$, which does not contain the origin. In any case, isn't it easy enough to just translate co-ordinates, and put the origin wherever you like? – Ben Millwood Jan 4 '13 at 21:33
I guess I'm confused about the 'uses the fact' then. Let's say that the convex set $X$ is the unit disc, and $u=(0,2)$ is not in $X$. What would $h$ be then? I do not see why that statement is true. More generally, even if you want $0 \not \in X$, take an interior point $I \in X$, take $u = I/n$, with $n$ large enough (since $0 \not \in X$. Then any vector $h$ such that $<u,h>=0$ is perpendicular to $u$, and the (neighbourhood of $I$) dot product $h$ has range a neighborhood of 0 – Calvin Lin Jan 4 '13 at 22:04
@CalvinLin: okay, I concede that the question itself is confused. I responded to what I assumed was meant, instead of what was actually written – I didn't prove (*) but instead a related idea that, well, is actually true, and leads to the desired result. – Ben Millwood Jan 4 '13 at 22:15
@CalvinLin: I see what you mean, now, I've edited some of my answer. – Ben Millwood Jan 4 '13 at 22:19