# Convexity of intersection

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?

-
convex optimization tag was not good for this question, so I removed it. – Beni Bogosel Sep 30 '11 at 8:08

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.

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.

-
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
@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

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.

-

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.

-
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