Let $S\subset \mathbb{R}^{n}\times \mathbb{R}$ and consider it’s projection onto $\mathbb{R}^n$, $S ={ x\in \mathbb{R}^n\mid (x, y)\in S, y\in \mathbb{R}}.$ Assuming $S$ is convex, prove that $S$ is convex.
My question is how does one go about proving the projection is convex. I know it seems trivial, but I keep losing marks for what I feel is the correct way to go about it. Thus I was wondering if someone could possibly give me an example of how I am supposed to do this. Thanks!
Let restate the problem using $T$ for one of the sets to avoid confusion above: let $S \subset \mathbb{R}^{n}\times \mathbb{R}$ and consider it’s projection onto $\mathbb{R}^n$, $T =\{ x\in \mathbb{R}^n|(x, y)\in S, y\in \mathbb{R}\}.$ (a) Assuming $S$ is convex, prove that $T$ is convex.
Let $x_1\in T$ and $x_2\in T$. To establish that $T$ is convex, we want to show that for $\theta\in (0,1)$, $\theta x_1 + (1-\theta)x_2 \in T$.
Since $x_1\in T$, there is some $y_1\in \mathbb{R}$ such that $(x_1,y_1)\in S$. Similarly there is some $y_1\in \mathbb{R}$ such that $(x_2,y_2)\in S$.
For any $\theta\in(0,1)$, convexity of $S$ implies that, $$ \left(\theta x_1 + (1-\theta)x_2, \theta y_1 + (1-\theta)y_2 \right) \in S. $$
We conclude that $\theta x_1 + (1-\theta)x_2$ is the projection of some point in $S$, i.e., $\theta x_1 + (1-\theta)x_2 \in T$. Thus $T$ is convex.
