11
$\begingroup$

I want to prove that any closed convex sets can be written as an intersection of half spaces using only the separation theorem as a pre-requisite. I'm getting a feel that I need to show two sets are subsets of each other, but not being able to understand how exactly to go about it.

$\endgroup$
10
$\begingroup$

I think that your approach should work.

Let $C\subseteq \mathbb{R}^n$ be a closed, convex set. Let $\mathcal{H}$ be the collection of closed, half-spaces that contain $C$. You would like to show that $$C = \bigcap_{H\in \mathcal{H}}H.$$

First we can show $C \subseteq \bigcap_{H\in \mathcal{H}}H.$ Let $x\in C$. By the definition of $\mathcal{H}$, any $H\in \mathcal{H}$ satisfies $C\subseteq H$. Hence $x\in H$ for any $H\in \mathcal{H}$ and therefore $x\in \bigcap_{H\in \mathcal{H}}H.$ This gives us the desired inclusion.

It is left to show that $C \supseteq \bigcap_{H\in \mathcal{H}}H.$ We prove this using the contrapositive, that is we will show that if $x\not\in C$ then $x\not\in \bigcap_{H\in \mathcal{H}}H.$ So choose $x$ such that $x\not\in C$. Since $C$ is closed and convex, there is a hyperplane that strictly separates $x$ from $C$. This hyperplane defines a half space $H$ containing $C$. Hence $x\not\in H$ implying that $x\not\in \bigcap_{H\in \mathcal{H}}H$. This proves the desired inclusion.

$\endgroup$
3
  • 1
    $\begingroup$ When you show the first direction, i.e. $C$ is contained in $H$, you use the premise that $H$ is the collection of closed half-spaces that contain $C$. that premise is not part of the premise OPs question. He just says "can be written as an intersection of half spaces " but does not say that $C$ is contained in $H$. so how can you use that? $\endgroup$ – makansij Oct 1 '18 at 22:13
  • $\begingroup$ The proof assumes there is at least one half space that contains $C$. A counterexample is $C=\mathbb{R}^n$. $\endgroup$ – Michael Jul 6 '20 at 10:05
  • $\begingroup$ Of course some people define $\cap_{H \in \phi}H=\mathbb{R}^n$. This assumes we somehow know we are working in $\mathbb{R}^n$ (the color green is a point that is “in each one” of the sets in the collection of no sets). $\endgroup$ – Michael Jul 6 '20 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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