# Prove that a convex polytope has finitely many extreme points.

$$a)$$ Prove that a convex polytope has finitely many extreme points.

$$b)$$ Prove that the unit disc $$S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$$ is not a convex polytope.

Hint : what are the extreme points of $$S?$$

My thoughts:

"A polytope is a bounded polyhedron", then formalize it we have:

$$\exists a_1^t\dots a_n^t\in\mathbb{R}^n,c_1\dots c_n\in\mathbb{R}, r\in\mathbb{R}\cap(0,\infty),s.t.$$

$$\{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}\subseteq B(0,r)$$

$$\text{iff } \{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}\text{ is a polytope.}$$

Using "Elementary Linear Programming With Application" by Bernard Kolman ⋅ Robert E. Beck

Intuition:

$$a)$$ Since those extreme points must located on intersections of finitely many half-spaces which implies extreme points are finite

$$b)$$ This is just a closed $$\mathbb{R}^2$$ circle, which has infinitely many extreme points, so it can not be formed by finitely many half-spaces, which can be bounded but can't be a polytope, so certainly not a convex polytope.

Intuitively, $$a),b)$$ are both almost trivial, but how do I write the proof formally$$?$$

More definitions

$$0.$$Definition of polyhedron

A polyhedron is the intersection of finitely many halfspaces

$$1.$$Definition of halfspaces $$P$$ in $$\mathbb{R}^n$$ $$P=\{x∈\mathbb{R}^n,a^tx\le(\ge)b\}$$

$$2.$$A point $$x\in\mathbb{R^n}$$ is a $$\underline{\text{convex combination}}$$ of the points $$x_1,x_2,\dots,x_r$$ in $$\mathbb{R}^n$$ if for some real numbers $$c_1,c_2,\dots,c_r$$ which satisfy $$\sum_{i=1}^r c_i=1\text{ and }c_i\ge0,\space1\le i\le r,$$ we have $$x=\sum_{i=1}^rc_ix_i$$

$$3.$$ The $$\underline{\text{convex hull}}$$ of a finite point set $$S$$ is the set of all convex combinations of its points.

$$4.$$ a $$\underline{\text{convex polytope}}$$ is the convex hull of a finite set of points

$$5.$$ A point $$u$$ in a convex set $$S$$ is called an $$\underline{\text{extreme point}}$$ of $$S$$ if it is not an interior point of any line segment in $$S$$. That is, $$u$$ is an extreme point of $$S$$ if there are no distinct points $$x_1$$ and $$x_2$$ in $$S$$ such that $$u=\lambda x_1+(1-\lambda)x_2,\space0<\lambda<1.$$

Rough work

$$a)$$Proof.

Assume $$S$$ is such convex polytope and has infinitely many extreme points, then

$$\forall n\in \mathbb{N},\exists^{\ge n} u\in S, s.t. \forall x_1\neq x_2\in S,\lambda\in(0,1)\cap\mathbb{R},u=\lambda x_1+(1-\lambda)x_2$$

Which contradict with $$S$$ is a convex hull of a finite set so it's not a convex polytope$$(\Rightarrow\Leftarrow)$$ $$\tag*{\square}$$

$$b)$$ Proof.

Define $$B(a;r):=\{x∈\mathbb{R}^n:|x−a| where $$a\in\mathbb{R}^n$$

Let $$\overline{S}:=\{{x∈\mathbb{R}^n:∀ε>0,B(x;ε)∩S≠\varnothing}\}$$. then we have:

$$\forall u\in\overline{S},x_1\neq x_2\in S,\lambda\in(0,1)\cap\mathbb{R},u\neq\lambda x_1+(1-\lambda)x_2$$

And also $$\overline{S}\subseteq S$$

But $$\overline{S}$$ is not a finite set, which means S has infinitley many extreme points, by contrapositive of $$a)$$

That implies $$S$$ is not a convex polytope. $$\tag*{\square}$$

Yet I'm trying to write a proof using def $$2,3,4,5$$,

Which I think is the correct definition that I suppose to use.

(keep updating$$\dots$$)

Any help or hint or suggestion would be appreciated.

• What is your book's definition of polytope ? – kimchi lover Oct 5 '19 at 16:29
• I do not know how to interpret your various ways to put parentheses into the natural language definition of convex polyhedron. I mean, I do not see how to formalize the statement in any other way than $$P=\bigcap_{i=1}^n H_i$$ where $n\in\Bbb N$ and for $1\le i\le n$, $H_i$ is a closed half-space. – Hagen von Eitzen Oct 5 '19 at 16:29
• @Manx Does that mean your book only defines (convex) polyhedron, not polytope? Does it define extreme point? – Hagen von Eitzen Oct 5 '19 at 16:31
• $B(0:r)$ stand for a open ball locate at $0$ with radius $r$, I'm trying to use the def for bounded set on this@Hagen von Eitzen – Manx Oct 5 '19 at 16:39
• @Manx I do not see that your book has a definition of polytope that implies boundedness. – Hagen von Eitzen Oct 5 '19 at 16:43