0
$\begingroup$

Suppose there are three points $x_1,x_2,x_3$, and they can be ranked in any order. For each order, e.g., $(x_1,x_2,x_3)$, each pair of points have a set, for example, regarding to this order, the sets are $S_{12},S_{13},S_{23}$. If we change the order of points, the resulting sets should be different, for example, if the order is $(x_3,x_2,x_1)$, the resulting sets are $\bar{S_{12}},\bar{S_{13}},\bar{S_{23}}$, where $S_{12}$ and $\bar{S_{12}}$ are complement to each other.

My question is, if for every order, a solution region is the intersection of sets. Then does the union region of all possible order is the whole space? For example, there are 3! orders and the corresponding solution region are:

$(x_1,x_2,x_3)$: $A_1 = S_{12}\cap S_{13} \cap S_{23}$

$(x_1,x_3,x_2)$: $A_2 = S_{12}\cap S_{13} \cap \bar{S_{23}}$

$(x_2,x_1,x_3)$: $A_3 = \bar{S_{12}}\cap S_{13} \cap S_{23}$

$(x_2,x_3,x_1)$: $A_4 = \bar{S_{12}}\cap \bar{S_{13}} \cap S_{23}$

$(x_3,x_1,x_2)$: $A_5 = S_{12}\cap \bar{S_{13}} \cap \bar{S_{23}}$

$(x_3,x_2,x_1)$: $A_6 = \bar{S_{12}}\cap \bar{S_{13}} \cap \bar{S_{23}}$

REVISED: Also, for each order, there is a transitivity property, for example, if the order is $(x_1,x_2,x_3)$, then $(S_{12}\cup S_{23}) \supseteq S_{13} \supseteq (S_{12}\cap S_{23})$ must holds. There might be some order whose solution region is empty. My problem is try to show the union of solution region for every possible order is an entire space.

Does the union of all these solution regions (for all possible orders), say $(A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6)$ is the whole space (say $D$?) what if the number of points are $n$? I think it is true, but not easy to prove it. Hope somebody gives some clues. Thanks.

$\endgroup$
  • $\begingroup$ I am not sure what your transitivity property means, but if I've interpreted it correctly, the proof becomes a lot easier! See answer below. $\endgroup$ – user326210 Aug 16 '17 at 23:30
1
$\begingroup$

I think what you are asking is this:

Suppose you have an ambient set $D$ and an ordered index list $\langle 1, 2, 3\rangle$. You assign to each pair of different indices $\langle i, j\rangle$ $(i\neq j \in \{1,2,3\})$ a subset $S_{i,j}\subseteq D$ which respects parity in the sense that $S_{i,j}$ and $S_{j,i}$ are complements of each other in $D$.

Then for any permutation $\langle i, j, k\rangle$ of $\langle 1, 2, 3\rangle$, you define the set

$$A_{i,j,k} \equiv S_{i,j} \cap S_{j,k} \cap S_{i,k}.$$

There are 6 such sets $A_{i,j,k}$ corresponding to the 3! permutations of $\langle 1, 2, 3\rangle$. Your question is whether the union over all six $A_{i,j,k}$ is necessarily equal to $D$.

I claim that the union of the $A_{i,j,k}$ is equal to $D$ if and only if the cyclic permutations $S_{1,2}, S_{2,3}, S_{3,1}$ have empty intersection and their union is $D$.


Let $A$ refer to the union of all six $A_{i,j,k}$.

Let us start by grouping the six results into pairs. Note that by the properties of union and intersection,

$$\begin{align*}A_{1,2,3} \cup A_{1,3,2} &= S_{1,2}\cap S_{1,3}\cap(S_{2,3} \cup S_{3,2})\\&= S_{1,2} \cap S_{1,3} \cap D\\ &= S_{1,2} \cap S_{1,3}\end{align*}$$

And similarly $$\begin{align*}A_{2,1,3} \cup A_{2,3,1} &= S_{2,1} \cap S_{2,3}\\ A_{3,2,1} \cup A_{3,1,2} &= S_{3,2} \cap S_{3,1}.\\ \end{align*}$$

Hence

$$A = (S_{1,2}\cap S_{1,3})\cup (S_{2,1} \cap S_{2,3}) \cup (S_{3,2}\cap S_{3,1})$$

To expose the complementarity here, we can put $P \equiv S_{1,2}$, $Q\equiv S_{2,3}$, $R\equiv S_{3,1}$. Then

$$A = (P \cap R^C) \cup (Q \cap P^C) \cup (R \cap Q^C) $$

In which case, union/intersection laws (or drawing a Venn diagram) reveals that $A = D$ if and only if $P\cap Q\cap R = \varnothing$ and also $P\cup Q\cup R = D$.

(Intuitively, this is because none of the terms above intersects $P\cap Q\cap R$, because each term intersects the complement of one of them.)


I am not sure what this transitivity property means. I interpret it as meaning that for all permutations $\langle i,j,k\rangle$ of $\{1,2,3\}$ we must have $S_{i,j} = S_{i,k}\cap S_{k,j}$.

Using the fact that $S_{i,j} = S_{j,i}^C$ and DeMorgan's laws, you can prove that this means that $S_{i,k} = S_{k,j}$ for all permutations $\langle i,k,j\rangle$. Indeed,

$$\begin{align*} S_{i,j} &= S_{j,i}^C\\ (S_{i,k}\cap S_{k,j}) &= (S_{j,k} \cap S_{k,i})^C\\ S_{i,k} \cap S_{k,j} &= S_{k,j} \cup S_{i,k} \end{align*}$$

and the only time the intersection of two sets is equal to their union is if the two sets are the same.

Hence

$S_{i,j} = S_{j,k} = S_{k,i}$ for all permutations $\langle i,j,k\rangle$ of $\{1,2,3\}$.

In our specific case, let us define $S_+ = S_{1,2} = S_{2,3} = S_{3,1}$ and $S_- = S_{3,2} = S_{2,1} = S_{1,3}$. The sets $S_+$ and $S_-$ are requred to be complements, and we have that for all $\langle i,j,k\rangle$,

$$S_{i,j,k} = S_+ \text{ or } S_- \text{ or }\varnothing$$

The first case occurs when the indices are a cyclic permutation of $\langle 1, 2, 3\rangle$ and the second case occurs when the indices are a cyclic permutation of $\langle 3,2,1\rangle$, and the empty case occurs every other time.

Hence $$A \supseteq A_{1,2,3} \cup A_{3,2,1} = A_+ \cup A_- = D$$.


This argument straightforwardly generalizes to $n>3$: by the transitivity and complentarity properties, we must have that there is a set $A$ such that

$$S_{i,j} = \begin{cases}A &\text{if }i < j\\ A^C & \text{if }j<i\end{cases}$$

Consequently, $S_{1,2,3,\ldots,n} = A$ and $S_{n,n-1,\ldots,1} = A^C$, so their union is $D$— the entire space.

$\endgroup$
  • $\begingroup$ Yes, you're right! Actually, there is transitivity in the permutation (which holds in my problem). For example, if 1<=2, and 2<=3, then 1<=3 must holds. Which means in your notation, $P \cap Q \cap R = \varnothing$. And if so, then $P \cup Q \cup R = D$ (I am not quite sure whether this is true, but seems very likely). So if the transitivity property exists, is there a way to generalize the proof of situation from 3 points to $n$ points? $\endgroup$ – WYC Aug 16 '17 at 20:14
  • $\begingroup$ @WYC, I don't understand exactly what you mean, but to generalize for $n$: if the intersection of the sets $S_{i_1,\ldots,i_n}$ with cyclicly-permuted indexes is empty and their union is the whole space $D$, then you can generalize the proof to $n$. The trick for the induction proof is that to permute $n+1$ things, you permute $n$ things and then choose where to put the last thing, with $n+1$ possibilities. $\endgroup$ – user326210 Aug 16 '17 at 22:20
  • $\begingroup$ Thank you, I will try in this way, it helps me a lot. $\endgroup$ – WYC Aug 16 '17 at 22:23
  • $\begingroup$ I am sorry there is a mistake in the question ($S_{i,j} \cap S_{j,k} \subseteq S_{i,k}$ for order <i,j,k>, not equal in the question). By transitivity, I mean in an order $(x_1,x_2,x_3)$, the intersection of $S_{1,2}$ and $S_{2,3}$ must be a subset of $S_{1,3}$. Because if $f(x_1)>=f(x_2)$ and $f(x_2)>=f(x_3)$, then $f(x_1)>=f(x_3)$, for the $f$ is a monotone increasing function that forms the solution region. $\endgroup$ – WYC Aug 16 '17 at 23:54
  • $\begingroup$ For $S_{i,j} \cap S_{j,k} = S_{i,k}$, your following deduction is correct. But if it's subset, that might not be true. Sorry about that I made this naive mistake. $\endgroup$ – WYC Aug 16 '17 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.