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 am having trouble understanding the proof for:

4.3.1 Lemma. Convex hull $C$ of a set $X \subseteq \Re $ equals the set: $$D= \left\{ \sum_{i=1}^{m}{t_i x_i} : m \geq 1, x_1...x_m \in X, t_1,...,t_m \geq 0, \sum_{t=1}^{m}{t_i} = 1 \right\}$$ of all convex combinations of finitely many points of X.

For the direction $C\subseteq D$, the authors say:

For the reverse inclusion it suffices to prove that $D$ is convex, that is, to verify that whenever $x,y \in D$ are two convex combinations and $t\in (0,1)$, then $tx + (1-t)y$ is again a convex combination.

Why does it suffice to prove that $D$ is convex? Shouldn't we prove that any point in $C$ is in $D$?

P.S. And what would it mean for a point to be in $C$ - which is convex hull? I find that confusing...

share|improve this question
2  
Take $m=1$, $t_1 = 1$ and $x_1 = x$ to see that $x \in D$ for all $x \in X$. Together with the stated fact that $D$ is convex we have $D \supset X$ and since $C$ is (probably) by definition the intersection of all convex sets containing $X$, we must have $C \subset D$. –  t.b. Nov 12 '11 at 9:35
    
Why do you need to have $X\subset D$? –  drozzy Nov 12 '11 at 9:39
5  
Again: $C$ is by definition the intersection of all convex sets containing $X$: $$C = \bigcap_{\substack {C' \text{ convex} \\ C' \supset X}} C'$$ If you know that $D$ contains $X$ (obvious, as I said above) and is convex (this requires an argument) then you know that $C \subset D$, as $D$ will then appear in the intersection. –  t.b. Nov 12 '11 at 9:41
    
My typo Didier - I fixed that. –  drozzy Nov 12 '11 at 10:17
    
Ok got it! Thanks! You should put this up as an answer so I can accept it! –  drozzy Nov 12 '11 at 10:24
add comment

1 Answer

up vote 3 down vote accepted

On drozzy's request I'm posting my comment as an answer:

By definition the convex hull $C$ of $X$ is the intersection of all convex sets $C'$ containing $X$: $$C = \bigcap_{\substack{C' \text{ convex} \\ C' \supset X}} C'.$$ If you know that $D$ is convex (that's what the authors show later on and needs some argument) and contains $X$ (that's obvious by taking $m = 1$, $t_1 = 1$ and $x_1 = x$ for each $x \in X$) then you know that $D$ will appear as some $C'$ in the intersection on the right hand side, so that $C \subset D$.

For the sake of completeness, the reasoning for the other inclusion $D \subset C$ is this: since all $C'$ appearing in the intersection are convex and contain $X$, they must contain all convex combinations of points of $X$. But $D$ is by its very description the set of all convex combinations of points of $X$, so $D$ is contained in all $C'$ appearing in the intersection and thus $D \subset C$.

share|improve this answer
    
Interesting, but the authors show the other direction $D\in C$ by induction. –  drozzy Nov 12 '11 at 16:55
    
I haven't looked at the book you mentioned, I assume that they show by induction the following: if $x_{1},\ldots,x_m \in C'$ and $t_1 + \cdots + t_m = 1$ with $t_i \geq 0$ then $\sum t_i x_i \in C'$. For $m = 2$ this is the definition of convexity and for greater $m$ you indeed need to prove this by induction. –  t.b. Nov 12 '11 at 17:03
add comment

Your Answer

 
discard

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

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