2

suppose X,Y are two convex sets

x1, x2 in X and y1, y2 in Y

defn of X and Y being convex:
tx1+(1-t)x2 in X
ty1+(1-t)y2 in Y

it is clear that:
1) X+Y is convex.
2) X intersection Y is convex

3) question: I know A union B is not convex but I don't understand why

AUB = A+B - A(intersection)B

but both on RHS are convex and subtraction of convex sets is convex. so shoudn't AUB also be convex?

how about A\B?

A\B = A - A(intersection)B again both on RHS are convex so shouldn't A\B be convex?

QN: for a convex set P, 2P belongs to P+P? How? How it it that 2P is not equal to P+P?

EDIT:

is A-B not a convex set? I thought it would be.

ta1+(1-t)a2 in A tb1+(1-t)b2 in B

WTS t*(a1-b1)+(1-t)(a2-b2) in A-B

but t*(a1-b1)+(1-t)(a2-b2) = t(a1)+(1-t)a2 - [t*b1+(1-t)b2]

first half in RHS is in A and second half in RHS is in B so whole thing is in A - B hence A-B is convex? no?

user128616
  • 615

3 Answers3

3

I don't think subtraction of convex sets is convex.

Let's look at a particular example in 1 dimension of a union of convex sets not being convex:

The intervals $[0,1]$ and $[2,3]$ are both convex because they satisfy your definition. But $[0,1] \cup [2,3]$ is not convex because, for example, $t \cdot 1 + (1 - t)\cdot 2$ is not in $[0,1] \cup [2,3]$ for any $t \in (0,1)$ (we chose $1$ and $2$ because $1$ is in the first set of the union, and $2$ is in the second set).

Intuitively, if the two sets have some "space" between them, then any line you draw between a point in one space and a point in the other will have points not in either.

As to why set difference of convex sets is not convex, we can use a similar idea. Consider the convex set $[0,3]$. Inside of it we have the interval $[1,2]$, which is also convex. But if we remove $[1,2]$ from $[0,3]$, we are left with $[0,1) \cup (2,3]$ which is not convex since, for example, we can find $t \in (0,1)$ such that $t \cdot \frac{1}{2} + (1 - t) \cdot \frac{5}{2}$ is not in this new set.

EDIT

For your last question: $2P$ is basically the set where you take each element of $P$ and multiply it by $2$, or, say, add it to itself once. But $P + P$ is the set where you take any two elements of $P$ and add them. If $P$ has more than one elememt, then $2P$ is a proper subset of $P + P$ because if you have two elements $p_{1}, p_{2}$ in $P$ that are not equal, then $p_{1} + p_{2}$ is in $P + P$ but not $2P$. Do you understand why?

layman
  • 20,191
  • subtraction of convex set it not convex? i suppose that makes sense and everything i'm asking readily deduces from that. however, please do check my edit. when i'm trying to formally write it out, it seems like A-B would indeed be convex. – user128616 Nov 10 '14 at 13:03
  • @user128616 I kept thinking about what is wrong with your proof in the edit you made. At first, everything seemed like it was OK. But now I realize what is wrong. $A - B$ is the set where you take the set of elements of $A$, and remove the elements of $B$ from this set. It is not elements of the form $a - b$ for $a \in A, b \in B$. I know that sounds weird, especially since $A + B = { a + b \mid a \in A, b \in B }$, but when we talk about set difference, which is what $A - B$ almost always means, we mean $A - B = { a \in A \mid a \not \in B }$. – layman Nov 10 '14 at 13:47
  • @user128616 So you proof is wrong in that it assumes elements of $A - B$ are of the form $a - b$. If you decided you wanted to define $A - B = { a - b \mid a \in A, b \in B }$, then you are right, this set is convex, and your proof is perfect for this. But I don't think $A - B$ means that in this context. Usually $A - B$ means the elements of $A$ that are not in $B$, and the example in my question proves that this set is not convex. I hope this makes sense. – layman Nov 10 '14 at 13:49
  • @user128616 Sorry for all of the confusion about notation. Just to be completely sure, you should ask your teacher what he or she means by $A - B$. Very rarely I have heard some people actually do use $A - B = { a - b \mid a \in A, b \in B }$ and it seems like that's what it should be used for since $A + B = { a + b \mid a \in A, b \in B }$, but that's not the case. Do you have any questions? – layman Nov 10 '14 at 13:50
0

Take the disjoint union of two squares, say at x=0, x=100, each with sides = 1. The point x=50 is in the convex hull of these two squares but isn't in the disjoint union, so the disjoint union isn't convex.
Again, for A\B, take two squares, A with sides 2, B with sides 1, if they are both centered at x=0 the point x=0,y=0 is in the convex hull of A\B yet isn't in A\B, so A\B isn't convex

GenericUsrnme
  • 395
0

If you define A such that $ S=A-B= a-b; a \epsilon A,b \epsilon B $ [in this content some authors use - with circle in "$\ominus$" to differentiate A\B] and A and B are both convex sets, then S is convex.

Proof: Let $ x = a-b $ and $ y= a'-b$ $\lambda \epsilon [0,1] $ $z = \lambda x + (1-\lambda)y = \lambda (a-b) + (1-\lambda) (a'-b') z \epsilon A \ominus B $

and we can modify z as $z=[\lambda a+(1-\lambda)a']-[\lambda b+(1-\lambda)b']$

let $ a''=[\lambda a+(1-\lambda )a']$ and $b'' = [\lambda b+(1-\lambda)b'] $

Therefore, $ z= a''-b''\epsilon A \ominus B,$ where $a'' \epsilon A$ and $ b'' \epsilon B $

secret_garden
  • 1