# Question about the proof of distributive laws of unions

My question is about the proof of the distributive laws of boolean operations, more specifically I have some trouble understanding this equality: $$B \cup (A_1 \cap \cdots \cap A_n) = (B \cup A_1) \cap \cdots \cap (B \cup A_n)$$.

Denoting $$(A_1 \cap \cdots \cap A_n)$$ by $$C$$, the left hand side reads as $$x \in B$$ or $$C$$, that is $$x$$ is in at least one of $$B$$ and $$C$$.

Now, I interpret the right hand side the following way: If $$x$$ is not in $$B$$, then $$x$$ must be in all the $$A_i$$, because for each term, $$x$$ has to be in at least one of $$B$$ or $$A_i$$, and if $$x \notin B$$ for one term, then $$x \notin B$$ for all terms. That's about as far as I get, because I feel like the right hand side implies that $$x$$ can be in $$B$$ and just some of the $$A_i$$, which would contradict the left hand side. Like, if we look at the first term $$B \cup A_1$$, one valid possibility is that $$x$$ is in $$B$$ and $$A_1$$. At the same time, for the second term, $$B \cup A_2$$, it seems like it would be valid to say that $$x$$ is in $$B$$ but not in $$A_2$$, but this contradicts the left hand side, which implies that $$x$$ must be in every $$A_i$$ if it is in one of them.

So if I were given just the right hand side, $$(B \cup A_1) \cap \cdots \cap (B \cup A_n)$$, I would say, OK, $$x$$ can be in $$B$$ and $$A_i$$ for all $$i$$, $$x$$ can be in not $$B$$ and $$A_i$$ for all $$i$$, but $$x$$ cannot be in not $$B$$ and just some of the $$A_i$$, since for every term $$x$$ must be in at least $$B$$ or $$A_i$$. And then finally, the part which seems irreconcilable with the left hand side of the equation at the top: $$x$$ can be in $$B$$ and some of the $$A_i$$.

Your interpretation of RHS is okay ("if $$x$$ is not in $$B$$ then $$x$$ must be in all $$A_i$$").

Also if $$x$$ is an element of the RHS then $$x$$ can indeed be an element of $$B$$ and some of the $$A_i$$.

This however does not contradict that $$x$$ is an element of the LHS (as you seem to think). Every element that is in $$B$$ is an element of the LHS simply because $$B$$ is a subset of the LHS, and the question whether $$x$$ is an element of some, none or all of the $$A_i$$ is not relevant.

Observe that the LHS can be interpretated exactly the same as RHS: $$x$$ is an element of LHS if it is an element of $$B$$ or is an element $$A_i$$ for some $$i\in\{1,\dots,n\}$$.

Does this help?

• I think so. For instance, if $x$ is in $B$ and $A_1,A_2$, but not for any other $A_i$, this does not contradict the LHS, b.c. $x$ is still in $B$, which is consistent with the LHS? – goblinb Jan 28 at 12:06
• Yes, that is what I am saying. – drhab Jan 28 at 12:44

A $$\cup$$ (B $$\cap$$ C) = (A $$\cup$$ B) $$\cap$$ (A $$\cup$$ B).
Proof.
x in A $$\cup$$ (B $$\cap$$ C) iff x in A or x in B $$\cap$$ C
if x in A or (x in B and x in C)
iff (x in A or x in B) and (x in A or x in B)
iff x in A $$\cup$$ B and x in A $$\cup$$ B
iff x in (A $$\cup$$ B) $$\cap$$ (A $$\cup$$ B)

By induction this proof can be extended to any finite number of intersections.

If C is any collection of sets, then
A $$\cup$$ $$\cap$$C = $$\cap$${ A $$\cup$$ X : X in C }.
Proof.
x in A $$\cup$$ $$\cap$$C iff x in A or x in $$\cap$$C
iff x in A or for all X in C, x in X
iff for all X in C, (x in A or x in X)
iff for all x in C, x in A $$\cup$$ X
iff x in $$\cap$${ A $$\cup$$ X : X in C }.