# Prove that the convex hull of X is the smallest convex set containing X [duplicate]

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.

• What definition of convex hull are you using? – Zev Chonoles Oct 8 '11 at 21:57
• 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? – Chris Eagle Oct 8 '11 at 22:05

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.

• How do u show the line connecting these two elemtns is contained in C(X)? – xuan Oct 9 '11 at 7:08
• @xuan: My sincere apologies, I gave an absolutely incorrect definition of $C(X)$ and consequently much of my answer was wrong. I have corrected my answer and given a full explanation of how to do it (now using the correct definition). – Zev Chonoles Oct 9 '11 at 7:42
• Thank you so much! Just one more question, how to use the fact that D is a convex set to show that when it contains X it must contain C(X)? – xuan Oct 9 '11 at 8:35
• @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)? – Alex Goft Mar 21 '17 at 14:43