# Prove that a set is convex

Let $X \subseteq \mathbb R^n$ be a convex set and $g\colon X\to\mathbb R$ a concave function. Prove that the set $\{(x,z)\in X \times \mathbb R \mid g(x) \geq z\}$ is a convex set.

How do I go about proving this?

If I take 2 elements in $X \times \mathbb R$, e.g. $(x_1,z)$ and $(x_2,z)$ I will end up with an $g(z)$ and can't prove the inequality.

Thanks.

-
Take $0\leq \alpha\leq 1$, put $x':=\alpha x_1+(1-\alpha)x_2$ and show that $g(x')\geq z$, using the concavity of $g$. – Davide Giraudo Oct 6 '11 at 20:04

Since $g$ is concave, for any $a,b\in X$ and any $t\in[0,1]$ we have $$g\bigl(ta + (1-t)b\bigr) \geq tg(a) + (1-t)g(b).$$
If $(x,z), (y,w)\in X\times\mathbb{R}$, then given $t\in[0,1]$ we have $$t(x,z) + (1-t)(y,w) = \bigl( tx + (1-t)y, tz+(1-t)w\bigr).$$
In order for this to be in $X\times \mathbb{R}$, we need $tx+(1-t)y\in X$ (convexity of $X$ should come into play here); $tz+(1-t)w\in \mathbb{R}$ (trivial); and $$g\bigl( tx+(1-t)y\bigr) \geq tz + (1-t)w.$$ We know $g(x)\geq z$, $g(y)\geq w$. And we know $g$ is concave, which gives us a lower bound for $g\bigl(tx + (1-t)y\bigr)$. Does that lower bound and the rest of the information suffice?