2
$\begingroup$

Possible Duplicate:
Prove that the convex hull of a set is the smallest convex set containing that set

First prove that the convex hull of X is itself a convex set containing X. Then show it is the smallest such set.

How do I prove this?

The definition of the convex hull of a set X is the set of all convex combinations of elements from X.

  • 1
    What have you tried? Can you prove either (a) the convex hull of X is convex or (b) every convex set containing X contains the convex hull of X?2011-10-08

1 Answers 1

2

As the hint in your problem indicates, proving that the convex hull $C(X)$ of $X$ is "the smallest convex set containing $X$" consists of proving two facts:

  1. $C(X)$ is a convex set containing $X$.
  2. Any other convex set $D$ that contains $X$ must contain $C(X)$.

First, let's write down the definition of $C(X)$ in symbols: $C(X)=\left\{\sum_{i=1}^na_ix_i\;\bigg\vert\; a_1,\ldots,a_n\geq0, \sum_{i=1}^n a_i=1\right\}$ In other words, $C(X)$ is the union of all convex combinations of elements of $X$.

To show that $C(X)\supseteq X$ is very easy: for any $a\in X$, we have that $1a=a\in C(X).$ To show that $C(X)$ is convex, take any two elements $\sum_{i=1}^na_ix_i$ and $\sum_{j=1}^mb_ix_i$ in $C(X)$ (where each $x_i,y_i\in X$, each $a_i,b_j\geq0$, and $\sum_{i=1}^na_i=1$ and $\sum_{j=1}^mb_j=1$) and show that the line connecting them is contained in $C(X)$ (that is, after all, the definition of convex set). Note that the line connecting them consists of points of the form $(1-t)\left(\sum_{i=1}^na_ix_i\right)+t\left(\sum_{j=1}^mb_jy_j\right)=\sum_{k=1}^nc_kx_k+\sum_{k=i+1}^{n+m}c_ky_k=\sum_{k=1}^{n+m}c_kz_k$ where $c_k=\begin{cases}(1-t)a_k\;\;\text{ if }1\leq k\leq i\\ tb_{k-n}\;\;\qquad\text{ if }n+1\leq k\leq n+m\end{cases}$ and $z_k=\begin{cases}x_k\;\;\;\;\;\;\;\text{ if }1\leq k\leq i\\ y_{k-n}\;\;\text{ if }n+1\leq k\leq n+m\end{cases}$ Furthermore, note that $\sum_{k=1}^{n+m}=(1-t)\left(\sum_{i=1}^na_i\right)+t\left(\sum_{j=1}^mb_j\right)=(1-t)(1)+(t)1=(1-t)+t=1$ Therefore, we have shown that any point on the line connecting two elements of $C(X)$ is also in $C(X)$ (because it is of the correct form), and therefore that $C(X)$ is convex.

Finally, to show that any convex set $D$ that contains $X$ must contain $C(X)$, simply use that $D$ is a convex set.


  • 0
    @ZevChonoles It's been a while, but can you please elaborate about how to use the fact that D is a convex set to show that when it contains X it must contain C(X)?2017-03-21