Prove the distributive property for sets:
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
I'm not good with proofs but my understanding is that I have to prove 2 things:
(1) $A \cup (B \cap C) \subset (A \cup B) \cap (A \cap C)$
(2) $A \cap (B \cap C) \supset (A \cup B) \cap (A \cup C)$
This is what I have done so far:
Part (1)
If $x\in A$, then $x \in (A \cup B)$ and $x \in (A \cup C)$.
$\therefore x \in (A \cup B) \cap (A \cap C)$
If $x \in (B \cap C)$ then $x \in (A \cup B)$ and $x \in (A \cup C)$ because $x \in B$ and $x \in C$.
$\therefore x \in (A \cup B) \cap (A \cap C)$
$\therefore A \cup (B \cap C) \subset (A \cup B) \cap (A \cup C)$
Part (2)
Now we have to prove the reverse inequality: $(A \cup B) \cap (A \cap C)$. Then $x \in A \cup B$ and $x \in (A \cup C)$
If $x \in A$, then $x \in A \cup (B \cap C)$
This is where I am up to. I wanted to know whether my approach is correct and if I did part (1) correctly. I'm stuck on part (2) and don't know how to proceed. I'd appreciate any help.
Thank you!!
$\endgroup$ 13 Answers
$\begingroup$You must first prove 2 cases:
(1) $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$
(2) $(A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$
Note that in mathematics we use the following symbols:
$\cap=$ AND = $\land$
$\cup=$ OR = $\lor$
Case 1: $A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$
Let $x \in A \cap (B \cup C) \implies x \in A \land x \in (B \cup C)$
$\implies x \in A \land \{ x \in B \lor x \in C \}$
$\implies \{ x \in A \land x \in B \} \lor\{ x \in A \land x \in C \} $
$\implies x \in (A \cap B) \lor x \in (A \cap C)$
$\implies x \in (A \cap B) \cup (A \cap C)$
$\therefore x \in A \cap (B \cup C) \implies x \in (A \cap B) \cup (A \cap C)$
$\therefore A \cap (B \cup C) \subset (A \cap B) \cup (A \cap C)$
Case 2: $(A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$
Let $x \in (A \cap B) \cup (A \cap C) \implies x \in (A \cap B) \lor x \in (A \cap C)$
$\implies \{x \in A \land x \in B \} \lor \{ x \in A \land x \in C \}$
$\implies x \in A \land \{ x \in B \lor x \in C\}$
$\implies x \in A \land \{B \cup C \}$
$\implies x \in A \cap (B \cup C)$
$\therefore x \in (A \cap B) \cup (A \cap C) \implies x \in A \cap (B \cup C)$
$\therefore (A \cap B) \cup (A \cap C) \subset A \cap (B \cup C)$
$\therefore A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
$\endgroup$ 1 $\begingroup$Let $X = A \cap (B \cup C)$ and $Y = (A \cap B) \cup (A \cap C)$
To show that $X=Y$, we must show that:
- $X \subseteq Y$
- $Y \subseteq X$
Case 1: $X \subseteq Y$
If $x \in X$, then $x \in A$ and $x \in (B \cup C)$
The latter implies that $x$ is a member of at least one of $B$ or $C$.
We will proceed from here in 3 cases:
Case A: $x \in B$ and $x \notin C$
We know from above that $x \in A$.
If $x \in B$ and $x \in A$, then $x \in (A \cap B)$.
If $x \in (A \cap B)$, then $x \in (A \cap B) \cup (A \cap C)$.
$(A \cap B) \cup (A \cap C) = Y$, therefore $x \in Y$.
Case B: $x \notin B$ and $x \in C$
This is symmetric to Case A.
Case C: $x \in B$ and $x \in C$
This is simply an extension of Case A and Case B.
Therefore, if $x \in X$, then $x \in Y$, which implies $X \subseteq Y$.
Case 2: $Y \subseteq X$
If $y \in Y$, then $y$ is a member of at least one of $(A \cap B)$ or $(A \cap C)$.
Again, we have 3 cases:
Case A: $y \in (A \cap B)$ and $y \notin (A \cap C)$.
The former implies $y \in A$ and $y \in B$ by the definition of intersection.
If $y \in B$, then $y \in (B \cup C)$.
If $y \in A$ and $y \in (B \cup C)$, then $y \in (A \cap (B \cup C))$.
$(A \cap (B \cup C)) = X$, therefore $y \in X$.
Case B: $y \notin (A \cap B)$ and $y \in (A \cap C)$.
This is symmetric to Case A.
Case C: $y \in (A \cap B)$ and $y \in (A \cap C)$.
This is simply an extension of Case A and Case B.
Therefore, if $y \in Y$, then $y \in X$, which implies $Y \subseteq X$.
From Case 1 and Case 2, we have:
$X \subseteq Y$ and $Y \subseteq X$, therefore $X = Y$, which implies $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. This completes the proof.
$\endgroup$ $\begingroup$A simple way is to do a calculational proof, starting at the most complex side, to calculate which elements are in $(A \cup B) \cap (A \cup C)$: for all $x$, $$ \begin{align} & x \in (A \cup B) \cap (A \cup C) \\ \equiv & \;\;\;\;\;\text{"definition of $\cap$; definition of $\cup$, twice"} \\ & (x \in A \lor x \in B) \land (x \in A \lor x \in C) \\ (*) \; \equiv & \;\;\;\;\;\text{"logic: simplify by 'factoring out' $x \in A$, using the fact that $\lor$ distributes over $\land$"} \\ & x \in A \lor (x \in B \land x \in C) \\ \equiv & \;\;\;\;\;\text{"definition of $\cap$; definition of $\cup$"} \\ & x \in A \cup (B \cap C) \\ \end{align} $$ Now by extensionality (i.e., equal sets have the same elements) it follows that $$(0) \;\;\; A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$
Note how we didn't need to prove two separate $\subseteq$ cases. Also note that the key step $(*)$ uses the logical law $$(1) \;\;\; P \lor (Q \land R) \;\equiv\; (P \lor Q) \land (P \lor R)$$ We see that $(0)$ and $(1)$ have the same structure. Since $(1)$ is in the logic domain, it is more generally useful than $(0)$, which is only applicable when dealing with sets.
$\endgroup$ 1
