Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm going through some of the practice questions in my textbook, and one has me stumped, on account of seeming almost too straight-forward. We're instructed to show that two sets, $A$ and $B$ of $\mathbb{R}^n$, can be strongly separated iff the origin can also be strongly separated from the set $A-B$.

We know that the strong separation between $A$ and $B$ would require that the distance between the two sets be positive. We can otherwise state this as:

$\inf\{\lVert a-b\rVert\} \gt 0$, where $a\in A$ and $b\in B$.

If we assume that the distance from $A-B$ to the origin is also positive, then it can be expressed as:

$\inf\{\lVert \mathbf{0}-(a-b)\rVert\}\gt 0$, where $\mathbf{0}$ is the origin and $a\in A$, $b\in B$.

This can be simplified to $\inf\{\lVert a-b\rVert\} \gt 0$, which is equivalent to $\inf\{\lVert b-a\rVert\} \gt 0$, because distance is always positive.

This seems almost too easy. Did I mess up? Anyone have a better proof in mind? As always, many thanks.

share|improve this question
1  
This seems correct. –  PEV Apr 13 '11 at 18:27
add comment

1 Answer 1

up vote 2 down vote accepted

The statement is indeed not very difficult, and you have essentially proven it. But you need to be a bit careful with what you are allowed to assume and what you are supposed to conclude when you are writing it up. In particular, at no point should you be assuming that both $A$ and $B$ can be separated and that $A-B$ can be separated from the origin; yet your wording suggests you are doing so (when you say "if we assume the distance from $A-B$ to the origin is also positive", emphasis added).

So, to be clear and organized: you are trying to prove an "if and only if" statement. So you want to prove two things: that if $A$ and $B$ can be separated, then the origin can be separated from $A-B$; and also that if the origin can be separated from $A-B$, then $A$ and $B$ can be separated.

The standard way to do an "if and only if" proof is to do each implication separately, though sometimes one can proceed from one proposition to the other by performing steps that are all "reversible" (if and only if statements as well).

Let's do the former: to prove that "only if" implication, you want to show that $A$ and $B$ can be separated only if $\mathbf{0}$ can be separated from $A-B$ (that is, if $A$ and $B$ can be separated, then $\mathbf{0}$ can be separated from $A-B$). So, assume $A$ and $B$ can be separated. That means that there is a $d\gt 0$ such that $\lVert a-b\rVert \geq d$ for all $a\in A$ and $b\in B$ (that is, the infimum of these quantities is $d$, which is positive). You want to show that the infimum of $\lVert \mathbf{0} - x\rVert$, with $x$ ranging over all points in $A-B$, is also positive. And you can do it exactly as you do: since $x\in A-B$, then we can write $x=a-b$ for some $a\in A$ and $b\in B$. Then $$\lVert \mathbf{0} - x\rVert = \lVert \mathbf{0}-(a-b)\rVert = \lVert -a+b\rVert = \lVert b-a\rVert = \lVert a-b\rVert\geq d$$ (the last inequality by our assumption that we can separate $A$ and $B$). Since every single $\lVert \mathbf{0}-x\rVert$ is greater than or equal to $d$, then $d$ is a lower bound for the set $\{\lVert \mathbf{0}-x\rVert\mid x\in A-B\}$, so it follows that $$\inf\{\lVert \mathbf{0}-x\rVert\mid x\in A-B\} \geq d\gt 0.$$ Therefore $\mathbf{0}$ can be separated from $A-B$. This proves the "only if" clause.

To prove the "if" clause, we want to show that $A$ and $B$ can be separated if $\mathbf{0}$ can be separated from $A-B$; that is, if $\mathbf{0}$ and $A-B$ can be separated, then $A$ and $B$ can be separated. So we assume that $\mathbf{0}$ and $A-B$ can be separated; that is, that there exists some $r\gt0$ such that $\lVert \mathbf{0} - x\rVert\geq r$ for all $x\in A-B$. We want to show that $\inf\{\lVert a-b\rVert\mid a\in A, b\in B\}\gt 0$.

To that end, let $a\in A$ and $b\in B$. Then $a-b\in A-B$, so $$\lVert a-b\rVert = \lVert (a-b) - \mathbf{0}\rVert = \lVert\mathbf{0}-(a-b)\rVert \geq r$$ (the last inequality by our assumption that we can separate $\mathbf{0}$ from $A-B$). Since each $\lVert a-b\rVert$ is greater than or equal to $r$, then $r$ is a lower bound for the set $\{\lVert a-b\rVert\mid a\in A,b\in B\}$, which shows that $$\inf\{\lVert a-b\rVert\mid a\in A, b\in B\}\geq r\gt 0.$$ Thus we conclude that $A$ and $B$ can be separated. QED

(This is essentially your argument, spruced up and stated very carefully).

Note. In this particular instance, you can actually proceed by a chain of "if and only if"s: $$\begin{align*} \mbox{$A$ and $B$ can be separated}&\quad\text{if and only if}\quad \inf\{\lVert a-b\rVert\mid a\in A, b\in B\} \gt 0\\ &\quad\text{if and only if}\quad \inf\{\lVert \mathbf{0}-(a-b)\rVert\mid a\in A, b\in B\}\gt 0\\ &\quad\text{if and only if}\quad \inf\{\lVert \mathbf{0}-x\rVert\mid x\in A-B\}\gt 0\\ &\quad\text{if and only if}\quad\mbox{$\mathbf{0}$ can be separated from $A-B$.} \end{align*}$$ with the explanation that the penultimate step is done by noting that $x\in A-B$ if and only if $x=a-b$ for some $a\in A$ and $b\in B$, and the one prior to that because $\lVert 0 - y\rVert = \lVert y\rVert$ for all $y\in\mathbb{R}^n$.

share|improve this answer
    
very clear and insightful. Thanks! –  user8921 Apr 13 '11 at 20:03
add comment

Your Answer

 
discard

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