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 have been asked to prove that, given a convex set $C$, its intersection with a line is also convex.

From convexity definition, I have that $\forall x_1,x_2\in C, \alpha x_1+\beta x_2 \in C$ with $\alpha,\beta\ge0, \alpha+\beta=1$.

If I have $x_3,x_4 \in C \cap L$, every point in the line can be expressed as $x = x_4 + t (x_3-x_4)=tx_3+(1-t)x_4$. If the convex combination $\alpha x_3+(1-\alpha) x_4$ belongs to $C$, then it is trivial to show that, just by making $t=\alpha$, it also belongs to L, hence to $C \cap L$.

As always, I think I am oversimplifying or forgetting something. Is my proof right, or am I missing the crucial point?

Thanks in advance.

share|improve this question
1  
convex optimization tag was not good for this question, so I removed it. –  Beni Bogosel Sep 30 '11 at 8:08
add comment

3 Answers

up vote 3 down vote accepted

You need to do just a little more work: it’s possible that $C$ and $L$ intersect in a single point; of course in that case $C\cap L$ is trivially convex, so let’s assume now that there are at least two distinct points in $C\cap L$, say $p$ and $q$. Then you can argue pretty much as you did, though it could be phrased more clearly.

Added: Here’s one slightly smoother way to phrase your argument.

Suppose that $p$ and $q$ are distinct points of $C\cap L$ and that $\alpha\in\mathbb{R}$ satisfies $0\le \alpha \le 1$; we must show that $\alpha p + (1-\alpha)q \in C\cap L$. Certainly $\alpha p + (1-\alpha)q \in C$, since $p,q\in C$ and $C$ is convex. Moreover, we know that $L = \{tp+(1-t)q:t\in\mathbb{R}\}$, so $\alpha p + (1-\alpha)q \in L$: just take $t=\alpha$. Thus, $\alpha p + (1-\alpha)q \in C\cap L$, as desired, and $C\cap L$ is convex.

share|improve this answer
    
Thank you, Brian. I am happy to see that I was on the path to the right answer. Any hint about which parts of my proof are bad-phrased? I would like to polish my future proofs. –  Fernandez Sep 30 '11 at 8:47
1  
@Fernandez: Just little things. For instance, you don’t need four named points, $x_1,x_2,x_3,x_4$. It’s easiest just to give an example; I’ll add to my answer a version as I might write it at your stage in the course. –  Brian M. Scott Sep 30 '11 at 8:52
    
Wow! That was a great example. I can see the difference now. Thank you very much. –  Fernandez Sep 30 '11 at 10:08
add comment

In general, the intersection of two convex sets is again a convex set. To do this, pick $x,y \in C_1 \cap C_2$ and $\alpha \in (0,1)$. Then by convexity of $C_1$ we have that $\alpha x +(1-\alpha)y \in C_1$. The same argument proves that $\alpha x +(1-\alpha)y \in C_2$ so $\alpha x +(1-\alpha)y \in C_1\cap C_2$ and by definition $C_1 \cap C_2$ is convex.

A line is a convex set, so the intersection of a line and a convex set is again convex.

share|improve this answer
add comment

That looks about right. If you want it slightly slicker, you can also observe that a line is itself a convex set and the intersection of convex sets is convex.

share|improve this answer
2  
I suspect that this is an exercise preceding the result that the result that the intersection of convex sets is convex, in which case it’ll have to be done from the definition. –  Brian M. Scott Sep 30 '11 at 8:12
    
Yes. That was the point. Maybe I forgot to put that in the question. :-( –  Fernandez Sep 30 '11 at 8:44
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.