Convexity/What is a convex 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.

A convex set; no line can be drawn connecting two points that does not remain completely inside the 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

  where all   and  

is also in X.

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

Now we proceed by induction. Assume the theorem is true for  . If  , we can formulate the definition of   as a linear combination of two points, one of which is itself a linear combination of the first   points and the other is the  th point:

  where  .

By the induction hypothesis, the first point must be in  ; therefore, from the definition,  .