# Proof that a set $C$ is convex $\iff$ its intersection with any line is convex

I'm working through Convex Optimization by Boyd, and want to check my answer to the above question. Is the following reasoning correct?

Let $L$ be an arbitrary line.

For $\Rightarrow$:

Case 1: $C \cap L = \emptyset$

This is convex by definition.

Case 2:$C \cap L \neq \emptyset$

$x,y \in C$ and $x,y \in L \implies \lambda x + (1- \lambda)y \in C$ (by assumption) for $\lambda \in [0,1]$

Also, $\lambda x + (1- \lambda)y$ lies on the line segment between $x,y$, which is in $L$.

For $\Leftarrow$:

I decided to try proof by contradiction:

We are given that $C\cap L$ is convex for all lines. Assume $C$ is not convex.

Our assumption implies $\exists x,y \in C$ and $\lambda_0\in [0,1]: \lambda_0 x + (1-\lambda_0)y \notin C$. However, the line formed by $ax+(1-a)y,\;\;a\in \mathbb{R}$ will have a nonempty intersection with $C$ and yet the resulting set will not be convex (i.e, it will not contain $\lambda x + (1-\lambda)y$). Hence, we must negate our assumption, which means that $C$ must be convex.

I think this is correct as per this question:Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.

I also justified it by noting that if we let $A$ be the proposition "$C \cap L$ is convex for all lines $L$", and $B$ be the proposition "$C$ is convex" then what I showed was:

$A \wedge \neg B \implies \neg A$ which is equivalent to:

$\neg (A \wedge \neg B) \vee \neg A$ which (via DeMorgan's Laws) is $\neg A \vee B$.

This last statement can also be expressed $A \implies B$, hence I think I've shown the converse.

• I think your proof is good. In statement Our assumption implies ... it's better to add for a $\lambda_0\in\mathbb{R}$. Jan 19 '17 at 21:23
• @MyGlasses thanks. I added your statement, although since I'm working with convex sets, I restricted lambda to the unit interval.
– user408433
Jan 19 '17 at 21:25
• No, This $\lambda$ is $\exists\lambda$ which $0<\lambda<1$. Jan 19 '17 at 21:27
• @MyGlasses Oh...yes! Thanks! It wont be true for ALL lambdas.
– user408433
Jan 19 '17 at 21:28
• I can't remember on which thread, but this question has already been asked (and answered) here on SE in the past... Jan 20 '17 at 8:54

$$\Leftarrow$$: Let $$x,y\in C$$ and let $$\lambda\in[0,1]$$. We wish to prove $$\lambda x + (1-\lambda)y\in C$$.
Let $$L$$ be the line through $$x$$ and $$y$$. $$x$$ and $$y$$ are in $$C\cap L$$. By convexity of $$C\cap L$$, we have that $$\lambda x + (1-\lambda)y\in C\cap L$$ and hence clearly $$\lambda x + (1-\lambda)y\in C$$.
• don't you also have to show that if $C \cap L$ is not convex then $C$ cannot be convex (to satisfy IFF)? May 21 at 13:51