I have two sets, each of which is the convex hull of finitely many points in $\mathbb{R}^n$ (in my case $\mathbb{R}^5$, but that shouldn't really matter). I'm certain that their intersection is itself the convex hull of finitely many points.
This seems to be one of those things that's "obvious" but hard to prove. A (somewhat terse) proof in two dimensions is given by The intersection of finite number of convex hulls is a convex hull.
I am unsure whether the induction mentioned is to handle $\mathbb{R}^n$. Attempting to generalize the argument even to $\mathbb{R}^3$ or $\mathbb{R}^3$, let alone $\mathbb{R}^n$ gets messy fast. I'm wondering if there's an easier way to handle this.
One idea is to show that a set is the convex hull of finitely many points iff both it is bounded and it is the intersection of finitely many closed half-spaces. That could be simpler, but I'm not sure how to do that either.
Best Answer
In "Polytopes, Rings, and K-Theory," Bruns/Gubeladze attribute the following to Minkowski:
which is the theorem you reference as a proof method in your last paragraph.
Sidenote: In attempting to look this up, it seems to be a special case of what many call the "Weyl-Minkowski theorem", which Bruns/Gubeladze instead attribute to Motzkin, so the attributions might still be in conflict. In any case, it makes it hard to look up a reference.
If we've already proven the above theorem, then your question is rephrased as "Is the intersection of two polytopes itself a polytope?" The answer to this is obviously "yes," as the intersection of two bounded sets is bounded and intersecting an intersection of finitely many closed [affine] half-spaces with another intersection of finitely many closed [affine] half-spaces is trivially an intersection of finitely many closed [affine] half-spaces (which is a whole lot of a words to basically say "finite + finite = finite")
The problem then is in proving this theorem. Of course, Bruns/Gubeladze prove it in the above book, but they develop quite a few tools in the previous sections to make their proof succinct, so if you want to see their proof, I'll direct you to the book.
To prove it from first principles, the following sketch should work:
$(\Rightarrow)$ By definition, there is some positive integer $N$ and for any $1\leq i \leq N,\lambda_i \in \mathbb{R}^n, b_i \in \mathbb{R}$ such that $$P = \{x \in \mathbb{R}^n : \lambda_i \cdot x \leq b_i, \forall i\}$$ For any $J \subseteq \{1,\ldots,N\},$ define $F_J = P \cap \{x \in \mathbb{R}^n : \lambda_j\cdot x = b_j, \forall j \in J\},$ and let $V$ denote the set of $\subseteq$-minimal elements of $\Big\{F_J : J \subseteq \{1,\ldots,N\}\Big\}\setminus\{\emptyset\}.$ Using the assumption $P$ is bounded and every affine linear subspace of positive dimension is unbounded, we can show $V = \{\{x_1\}, \ldots, \{x_m\}\}$ is a set of singletons. Now consider the convex hull of these points, which is immediately a subset of $P$ itself. This leaves showing $P$ is a subset of the given convex hull, which is a little tedious, but probably would work best by induction, showing each $F_J$ is the convex hull of some subset of $V.$
$(\Leftarrow)$ Obviously the convex hull $P$ of a finite set $V$ is bounded, so we would need to show $P$ is a polyhedron. Toward this end, we may assume $V$ is minimal (if we remove any point, the convex hull will be strictly smaller), and since an affine subspace of $\mathbb{R}^n$ is the finite intersection of closed affine half-spaces (by the existence of an orthogonal basis) we may reduce to the case that the affine subspace spanned by $V$ is all of $\mathbb{R}^n.$ Now just note that there is an affine linear map taking the $(|V|-1)$-simplex onto the convex hull of $V.$