Equivalent definitions of convex hull

convex-analysisinduction

$\newcommand{\N}{\mathbb{N}}$
The convex hull $H$ of a subset $A$ of $X$ is defined as
$$
H = \{z \in X~|~\exists x,y \in A:\exists t \in [0,1]:z=(1-t)x+ty\}
$$

Then, can we show that any convex combination of elements of $A$ is in $H$? That is,

$$
\forall n \in \N: P(n)
$$

where
$$
P(n) \Leftrightarrow \forall (x_i)_{i \leq n} \subseteq A: \forall (t_i)_{i \leq n} \subseteq [0,1]:
\sum_{i=1}^n{t_i = 1} \Rightarrow \sum_{i=1}^n {t_i x_i} \in H
$$

I tried to show by mathematical induction:

First, it is obvious that $A \subseteq H$ because we can pick an element of $A$ twice; for all $x \in A$, $(1-t)x+tx = x \in H$.

Let $n = 1$. Then, $x_1 \in A$ and $t_1 = 1$ implies that $\sum_{i=1}^n {t_i x_i} = t_1 x_1 =x_1 \in A \subseteq H$. Therefore, $P(1)$ holds.

Now, let $n$ be arbitrary and suppose $P(n)$ holds. Let $(x_i)_{i \leq n+1} \subseteq A$, $(t_i)_{i \leq n+1} \subseteq [0,1]$, and $\sum_{i=1}^{n+1}t_i = 1$.

Case 1) $t_{n+1} = 1$. Then, $t_i = 0$ for all $i \leq n$, which gives $\sum_{i=1}^{n+1}t_ix_i = x_{n+1} \in A \subseteq H $.

Case 2) $t_{n+1} \neq 1$. From $\sum_{i=1}^{n+1}t_i = \sum_{i=1}^{n}t_i + t_{n+1} = 1$, we have $\sum_{i=1}^{n}\frac{t_i}{1-t_{n+1}} = 1$. Thus, by $P(n)$, $\sum_{i=1}^{n}\frac{t_i}{1-t_{n+1}}x_i \in H$. However, we cannot conclude that
$$
\sum_{i=1}^{n+1}t_i x_i = (1-t_{n+1})\sum_{i=1}^{n}\frac{t_i}{1-t_{n+1}}x_i + t_{n+1}x_{n+1} \in H
$$

because it is not guaranteed that
$$
\sum_{i=1}^{n}\frac{t_i}{1-t_{n+1}}x_i \in A
$$

whereas $x_{n+1} \in A$.

Best Answer

There is a major problem with your definition of the convex hull $H$: it is not a convex set!

As an example, let $A$ be 3 points in the plane that form the vertices of a triangle. Now, all of the edge points are included in $H$ because they are a convex combination of two of the vertices. However, no interior point of the triangle can be written as a convex combination of two of the vertices (since a convex combination of two points is collinear with them). This is a problem: now the line connecting the midpoints of two edges is not contained in $H$, breaking convexity.


I realized this issue while thinking about the end of your argument. Because you showed that $y := \sum_{j = 1}^n \frac{t_j}{1 - t_{n + 1}} x_j \in H$, you'd be done if you could conclude $$(1 - t_{n + 1})y + t_{n + 1}x_{n + 1} \in H$$ using the convexity of $H$. So I tried to verify that $H$ is convex and failed for a while.

Figure for reference:

Related Question