0
$\begingroup$

Given $n$ sets $A_1 \ldots A_n$, and $1 \lt k \lt n$, is it true that the union of the intersections of all the combinations of $k$ sets is equal to the intersection of the unions of the same combinations? If yes, how to prove it?

For example, for $n = 3$ and $k = 2$, I have verified that:

$$(A_1 \cap A_2) \cup (A_1 \cap A_3) \cup (A_2 \cap A_3) = (A_1 \cup A_2) \cap (A_1 \cup A_3) \cap (A_2 \cup A_3)$$

$\endgroup$
1
  • 1
    $\begingroup$ Think of 'membership bits': what combinations of memberships in $A_1$, $A_2$ and $A_3$ — written as a three-bit table, if that makes things easier for the reasoning — would cause an element to be in the set on the LHS of your equation? What about the set on the RHS? $\endgroup$ – Steven Stadnicki Apr 22 '20 at 21:04
1
$\begingroup$

The first set consists of all the elements that are in at least $k$ of the $A_i$

The second set consists of all the elements that are in every union of $k$ $A_i$. So an element is not in the set if we can find $k$ $A_i$ that do not contain it, that is, the second set consists of all the elements that are in at least $n-k+1$ $A_i$

$\endgroup$
4
  • $\begingroup$ Isn't it "if we can find $k$ $A_i$ that do not contain it", i.e. an element is not in the set if it is contained in maximum $n-k$ $A_i$, and thus to be in the set it must be contained in at least $n-k+1$ sets? $\endgroup$ – BillyJoe Apr 22 '20 at 21:45
  • $\begingroup$ 100% correct, thanks for pointing it out ! $\endgroup$ – HereToRelax Apr 22 '20 at 22:00
  • $\begingroup$ You modified the answer, but I think what it actually should be is: "So an element is not in the set if we can find $k$ $A_i$ that do not contain it, that is, the second set consists of all the elements that are in at least $n−k+1$ $A_i$", which also applies to my example, because $2 = k = n - k + 1 = 3 - 2 + 1 = 2$. $\endgroup$ – BillyJoe Apr 23 '20 at 6:12
  • $\begingroup$ I have proposed an edit according to the above comment. $\endgroup$ – BillyJoe Apr 23 '20 at 6:26

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.