# Is the union of intersections of all combinations of sets equal to the intersection of unions of the combinations?

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)$$

• 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? – Steven Stadnicki Apr 22 '20 at 21:04

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$$
• 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? – BillyJoe Apr 22 '20 at 21:45
• 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$. – BillyJoe Apr 23 '20 at 6:12