4
$\begingroup$

I have eleven sets, all of them are subsets of $X:=\{(a,b,c,d)\in[-1,1]^4: a\le b,\text{ and } c\le d\}$: $$\begin{align*} A_1&:=\{(a,b,c,d)\in X: b\ge 0,\ c\le a+b+d\}\\ A_2&:=\{(a,b,c,d)\in X: b\ge 0,\ d\ge 0\}\\ A_3&:=\{(a,b,c,d)\in X: b\ge 0,\ a+b+2d\ge 0\}\\ A_4&:=\{(a,b,c,d)\in X: d\ge 0,\ a\le b+c+d\}\\ A_5&:=\{(a,b,c,d)\in X: d\ge 0,\ 2b+c+d\ge 0\}\\ A_6&:=\{(a,b,c,d)\in X: a\le b+c+d,\ c\le a+b+d\}\\ A_7&:=\{(a,b,c,d)\in X: a\le b+c+d,\ a+b+2d\ge 0\}\\ A_8&:=\{(a,b,c,d)\in X: 2b+c+d\ge 0,\ c\le a+b+d\}\\ A_9&:=\{(a,b,c,d)\in X: 2b+c+d\ge 0,\ a+b+2d\ge 0,\ c\le 2b+d\}\\ A_{10}&:=\{(a,b,c,d)\in X: 2b+c+d\ge 0,\ a+b+2d\ge 0,\ a\le b+2d\}\\ A_{11}&:=\{(a,b,c,d)\in X : 2b+c+d\ge 0,\ a+b+2d\ge 0,\ b+d\ge 0\}. \end{align*}$$ My question is: Are these sets independent, i.e. is any of the sets a subset of a union of other sets?

  • 0
    Where did this arise?2012-02-23
  • 0
    It is out of my attempt to find shortest path on the unit sphere of the sup norm.2012-02-23
  • 0
    I have no idea how to do this efficiently, but +1 for an interesting algorithmic problem.2012-02-23
  • 1
    Is the condition on $X$ the conjunction of two conditions, $a\leq b$ and $c\leq d$, or was it the condition that both $b$ and $c$ lie between $a$ and $d$? The notation "$a\leq b,c\leq d$" is ambiguous.2012-02-23
  • 0
    Your edit is correct.2012-02-23
  • 0
    @ArturoMagidin: If you put (at)someuser at the start of a comment that user will get a ping when you comment. In this case Arturo Magidin might not see it. Unfortunately (IMHO) you can only ping one user this way. I had to make it (at) instead of the symbol because I got a warning about exactly the behavior I was complaining about.2012-02-23
  • 0
    You have 36 sets in $X$, 6 choices for each pair $(a,b)$ and $(c,d)$ So calculate all the A's: how many are left? Probably not many. A little thought looking at them may yield enlightenment.2012-02-24
  • 0
    @Ross. Don't know which 6 choices you mean. Perhaps you have another proof better than my case by case proof below?2012-02-24
  • 0
    @TCL: I was taking the elements to be integers, so (a,b) could be (-1,-1), (-1,0), etc up to (1,1). I see now that you were thinking reals.2012-02-24

1 Answers 1

1

No. Every $A_i$ is a subset of $A_1\cup A_4$.

For $A_2$: We have $b+d\ge 0$. Since either $c\le a$ or $a\le c$, we have either $c\le a+b+d$ or $a\le b+c+d$, proving that $A_2\subset A_1\cup A_4$.

For $A_3$: If $d\ge 0$, then the point is in $A_2$ which is a subset of $A_1\cup A_4$. If $d\le 0$ then $-d\ge c$ since $c\le d\le 0$. So $a+b+d\ge -d\ge c$, proving that the point is in $A_1$.

Similar arguments apply to other $A_i$'s.