How does 'AND' distribute over 'OR' (Set Theory)?

Question

In my textbook, there is a solved example:

Prove that $A \cup (B \cap C) = (A \cup B)\cap(A\cup C).$

Solution

Let $x$ be an arbitrary element of $A \cup (B\cap C)$. Then, $$ \begin{aligned} &x\in A\cup (B\cap C)\\ \implies &x \in A \lor (x\in B\cap C)\\ \implies &x \in A \lor (x\in B \land x\in C)\\ \implies &(x \in A \lor x\in B) \land (x\in A \lor x\in C)\\ \implies &x\in(A \cup B) \land x\in(A\cup C)\\ \implies &x\in((A\cup B)\cap(A\cup C))\\ \therefore\ A\cup(B\cap C) \subseteq (A\cup B)\cap (A\cup C) \end{aligned} $$ Similarly, $(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$.
Hence, $A\cup (B\cap C) = (A\cup B)\cap(A\cup C)$.

The book didn't prove $(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$. So, I tried to do it:

Let $y$ be an arbitrary element of $(A\cup B)\cap(A\cup C)$. Then, $$ \begin{aligned} &y\in(A\cup B) \land y\in(A\cup C)\\ \implies &(y\in A \lor y\in B) \land (y\in A \lor y\in C)\\ \implies &((y\in A \lor y\in B)\land y\in A) \lor ((y\in A \lor y\in B)\land y\in C)\\ \implies &((y\in A \land y\in A)\lor (y\in B\land y\in A))\lor ((y\in A \land y\in C) \lor (y\in B \land y\in C)) \end{aligned} $$

I don't know how to proceed further. There could be a better way to prove this, but I just want to simplify this expression into something that could enable me to solve the problem.

Answer 1

The reason "similarly" was written is because all the $\implies$ could be replaced with $\iff$, thus allowing a path from $x\in(A\cup B)\cap(A\cup C)$ to $x\in A\cup(B\cap C)$ by reading backwards. Thus, you actually need no effort to prove the reverse case; it has already been printed out for you.

The set operations $\cap$ and $\cup$ correspond exactly with the $\land$ and $\lor$ of Boolean logic.

Answer 2

Remember that Distribution goes two ways. That is, you can go from $X \land (Y \lor Z)$ to $(X \land Y) \lor (X \land Z)$, but you can go from $(X \land Y) \lor (X \land Z)$ back to $X \land (Y \lor Z)$.

Now, going the other way doesnt feel like 'Distribution' (it feels more like a 'Reverse Distribution' or 'Çollecting common Terms'), which is exactly why so many beginning students of logic miss it, and instead end up doing the exact same thing you do: going from $(X \land Y) \lor (X \land Z)$ to $((X \land Y) \lor X) \land ((X \land Y) \lor Z)$ ... But that, as you saw, doesn't really go anywhere. This is a very common 'mistake'!

So, the key is to do Distribution 'the reverse way' after line 2:

$$ \begin{aligned} &y\in(A\cup B) \land y\in(A\cup C)\\ \implies &(y\in A \lor y\in B) \land (y\in A \lor y\in C)\\ \implies &y\in A \lor (y\in B \land y\in C)\\ \implies &y\in A \lor (y\in B \cap C)\\ \implies &y\in A \cup (B \cap C) \end{aligned} $$

And this, as @ParclyTaxel notes, just with all steps reversed from the first proof.

Answer 3

Indeed, it is always true that $(\alpha\lor\beta)\land(\alpha\lor\gamma)\equiv\alpha\lor(\beta\land\gamma)$. You can see this by verifying it semantically using truth tables (so there is also a derivation for it, but I can't seem to remember it):

\begin{array}{|c|c|c|c|} \hline \alpha&\beta &\gamma & (\alpha\lor\beta)\land(\alpha\lor\gamma) &\alpha\lor(\beta\land\gamma) \\ \hline 0& 0& 0& 0 &0\\ \hline 0& 0& 1& 0 &0\\ \hline 0& 1& 0& 0 &0\\ \hline 0& 1& 1& 1 &1\\ \hline 1& 0& 0& 1 &1\\ \hline 1& 0& 1& 1 &1\\ \hline 1& 1& 0& 1 &1\\ \hline 1& 1& 1& 1 &1\\ \hline \end{array}

We can thus write the expression

$$(y\in A\lor y\in B)\land (y\in A\lor y\in C)$$

as

$$y\in A\lor (y\in B\land y\in C)$$

which gives your claim and you don't have to expand any further.

Answer 4

Well, you shouldn't expand it. The statement $(y\in A \lor y \in B) \land (y\in A \lor y \in C)$ is equivalent by the distributive law to $y\in A \lor (y \in B \land y \in C)$.

Answer 5

Assuming your text means for $A,B,C$ to be non-empty we have the following.

To prove $A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$, we must show that $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$ and $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C) $.

In order to show $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$, let $x\in A\cup (B\cap C)$. Since $x\in A\cup (B\cap C)$, either $x\in A$ or $x\in B\cap C$.

Case 1: $x\in A$. If $x\in A$ then $x\in A$ or $x\in B$, so $x\in A\cup B$. Similarly, since $x\in A$, $x\in A$ or $x\in C$, so $x\in A\cup C$. Thus, $x\in A\cup B$ and $x\in A\cup C$, so $x\in (A\cup B)\cap (A\cup C)$. Hence $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$.

Case 2. $x\in B\cap C$. Argue similarly to case 1, conclude $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$. Try it out.

Still need to prove $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$. Let $x\in (A\cup B)\cap (A\cup C)$. Since $x\in (A\cup B)\cap (A\cup C)$, it follows that $x\in (A\cup B)$ and $x\in(A\cup C)$.

Case 1. $x\in A$. If $x\in A$, we are done since $x\in A$ implies that $x\in A\cup (B\cap C)$, so $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$.

Case 2. $x\not\in A$. If $x\not\in A$, then $x\in B$ and $x\in C$. So, $x\in B\cap C$ which gives us that $x\in A\cup (B\cap C)$. Conclusion, $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C)$.

Finally, we've shown $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$ and $(A\cup B)\cap (A\cup C)\subseteq A\cup (B\cap C) $ and so we can conclude that $A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$.