Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

1.4 Operations with sets

1.4 Operations with sets

Definition The sum of non-empty sets A and B is defined as the set

A + B : = { v + w | v A   a n d   w B } ,   w h e r e   A , B E n .

In case of translated linear subspaces (affine sets) the symbol + has been used in the same sense. The product of a set and a real number is

λ A = { λ v | v A } .

From the viewpoint of geometry the scalar multiplication is a central similarity (with the origin as the center), the addition is the union of images of A under translations with the elements of B (and vice-verse):

A + B = w B w + A = v A v + B .

(1.21)

This means that the scalar multiplication obviously preserves the convexity.

Theorem 1.4.1 The sum of convex sets is convex.

Proof If one of the terms is a singleton then the statement is trivial because the translation preserves the convexity. Otherwise let

z 1 = v 1 + w 1   a n d   z 2 = v 2 + w 2

be two elements of the set A+B, where

v i A   a n d   w i B ( i = 1,2 ) .

Then

λ z 1 + ( 1 - λ ) z 2 = λ v 1 + ( 1 - λ ) v 2 + λ w 1 + ( 1 - λ ) w 2 .

Because of the convexity

λ v 1 + ( 1 - λ ) v 2 A   a n d   λ w 1 + ( 1 - λ ) w 2 B .

Therefore

λ z 1 + ( 1 - λ ) z 2 A + B

as was to be proved. ▮

Proposition 1.4.2 Addition and scalar multiplication of sets have the following properties:

( A + B ) + C = A + ( B + C ) ,

(1.22)

A + B = B + A .

(1.23)

We also have the following distributivity-like property:

λ ( A + B ) = λ A + λ B .

(1.24)

If A is convex and the scalars have a common sign then

( λ 1 + λ 2 ) A = λ 1 A + λ 2 A .

(1.25)

Finally

( λ 1 λ 2 ) A = λ 1 ( λ 2 A )

(1.26)

and

1 A = A .

(1.27)

Proof Properties 1.22, 1.23, 1.24, 1.26 and 1.27 are trivial in the sense that they are direct consequences of the addition and the scalar multiplication of vectors. If one of the scalars is zero then property 1.25 is also obvious. Consider the case of positive scalars to prove one of the non-trivial cases (the case of negative scalars is similar). Suppose that

z = ( λ 1 + λ 2 ) v

for some element v in A. Then

z = λ 1 v + λ 2 v λ 1 A + λ 2 A

showing that the inclusion

( λ 1 + λ 2 ) A λ 1 A + λ 2 A

(1.28)

holds without any extra condition. Conversely if

z λ 1 A + λ 2 A

then we can write z into the form

z = λ 1 v 1 + λ 2 v 2 ,

where the right hand side involves not necessarily the same elements from A. Then we have that

1 λ 1 + λ 2 z = λ 1 λ 1 + λ 2 v 1 + λ 2 λ 1 + λ 2 v 2 .

The right hand side is a convex combination of elements from a convex set. Therefore

1 λ 1 + λ 2 z A

and property 1.26 says that

z ( λ 1 + λ 2 ) A

as was to be proved. ▮

Proposition 1.4.3 (Cancellation law, first version) If A, B and C are non-empty sets such that B is closed and convex, C is bounded then

A + C B + C

implies that

A B .

Proof Consider an element a in A and choose a point c(1) in C. Because of our hypothesis there exist

b 1 B   a n d   c 2 C   s u c h     t h a t   a + c 1 = b 1 + c 2 .

Similarly

a + c 2 = b 2 + c 3

for some elements b(2) in B and c(3) in C. In the kth step we have that

a + c k = b k + c k + 1 .

(1.29)

Taking the sum of equations 1.29 as k runs from 1 to n we have that

n a = b 1 + + b n + c n + 1

and, consequently,

a = b 1 + + b n n + c n + 1 n .

Since C is bounded

l i m n c n + 1 n = 0

and thus

a = l i m n b 1 + + b n n ,

where the right hand side involves a sequence of convex combinations of elements in B. Therefore the sequence runs in B (convexity) and its limit belongs to B because of the closedness. ▮

Corollary 1.4.4 (Cancellation law, second version) If A, B and C are non-empty sets such that A and B are closed and convex, C is bounded then

A + C = B + C

implies that A=B.

Remark The collection of non-empty compact convex sets forms a cancellative semigroup with respect to the set-addition.