Convexity/What is a convex set?

From Wikibooks, open books for an open world
Jump to: navigation, search
A convex set; no line can be drawn connecting two points that does not remain completely inside the set

A convex set is a set of points such that, given any two points A, B in that set, the line AB joining them lies entirely within that set.

Intuitively, this means that the set is connected (so that you can pass between any two points without leaving the set) and has no dents in its perimeter. Sections of the perimeter may be straight lines.

Notes[edit]

  1. It is assumed that the concept of a line joining two points is defined. In a vector space over the reals, it is the set {λA+(1-λ)B}, 0 < λ < 1}. It will be assumed that we are dealing with vector spaces over the reals unless the contrary is stated explicitly.
  2. By convention, the empty set and all sets consisting of a single point are regarded as convex. Since we cannot find two distinct points in such sets, we cannot say that the line joining two such points isn't contained in the set.

Theorem[edit]

If X is a convex set and x1 ... xk are any points in it, then

\displaystyle x = \sum_{i=1}^k \lambda_i x_i where all \displaystyle \lambda_i > 0 and \displaystyle \sum_{i=1}^k \lambda_i=1

is also in X.

Proof: If k=2, the theorem is true by the definition of a convex set.

Now proceed by induction. Assume the theorem is true for k=m. If k=m+1, we can formulate the definition of x as a linear combination of two points, one of which is itself a linear combination of the first m points and the other is the (m+1)th point. By the induction hypothesis, the first point must be in X; therefore, from the definition, s is in X.