# Convexity of sum and intersection of convex sets

Let $A_i$ be a subset of $\Bbb{R}^m$ which is convex for $i=1,...,n$. How can I prove that the sum of $A_i$ is also convex?

I know how to prove it with two sets:

Let $x = a_1 + b_1$ and $y = a_2 + b_2$ be two points of $A + B$, where $a_i \in A$, $b_i \in B$, $i= 1,2$. For $t \in [0,1]$, $$tx + (1-t)y = ta_1 + tb_1 + (1-t)a_2 + (1-t)b_2 = ( ta_1 + (1-t)a_2 ) + (tb_1 + (1-t)b_2)$$ which is a sum of a point in $A$ (as $A$ is convex, the convex combination of $a_1$ and $a_2$, both in $A$, is still in $A$) and a point of $B$ (same reasoning), so is in $A + B$. So $A + B$ is convex.

Also, how can I prove that the $A_1 \times A_2 \times \cdots \times A_n$ is convex if $A_i$ is convex?

• Holy crap, that was a mess. Thanks @TBongers for the edit. – AlexR Sep 19 '13 at 21:16
• @AlexR No problem. For the benefit of the asker, your questions will likely get a better response if typed in MathJax. – user61527 Sep 19 '13 at 21:17
• Have you tried inducting on n? – Nate Sep 19 '13 at 21:18
• I know that I have to use proof by induction, but I don't know how I can show it though. – user87274 Sep 19 '13 at 21:23
• You don't need induction. Just do exactly the same proof as for $n=2$, perhaps changing notation: $x=a_1+\cdots +a_n$, $y=b_1+\cdots +b_n$, ... By the way, $A_1\times \cdots\times A_n$ should be $A_1+\cdots +A_n$. – Etienne Sep 19 '13 at 21:46

Your proof that $A+B$ is convex for convex $A$ and $B$ is correct, the general case follows by induction.
If $A_i\subseteq\Bbb R^m$ for $i=1,...,n$ then $A_1\times...\times A_n$ is convex in $\Bbb R^{mn}$:
Let $a=(a_1,...,a_n)$ and $b=(b_1,...b_n)$ where $a_i,b_i\in A_i$ for each $i$. Then $tb+(1-t)a=(tb_1+(1-t)a_1,...,tb_n+(1-t)a_n)$ is an element of the product since all $A_i$ are convex.