# Prove the set identity $(A \cap B) \setminus (B\cap C) = A \cap (B \setminus C)$

Prove the set identity $(A \cap B) \setminus (B\cap C) = A \cap (B \setminus C)$

Attempt at proof:

For some element $x\in (A \cap B) \setminus (B\cap C)$: $$x\in (A \cap B) \setminus (B\cap C) \implies x \in (A \cap B) \land x \notin (B\cap C)$$ $$\implies x \in A \land x\in B \land x \notin B \land x \notin C$$

For some element $x\in A \cap (B \setminus C)$: $$A \cap (B \setminus C) \implies x \in A \land x \in (B \setminus C) \implies x \in A \land x\in B \land X \notin C$$

The first part of the proof seems to have a contradiction with $x\in B \land x \notin B$ and I am not sure how to prove further

• You use $x\not\in(B\cap C)\implies x\not\in B \land x\not\in C$. This is false. It should be something like $$x\not\in(B\cap C) \iff \lnot(x\in B \land x \in C) \iff x\not\in B \lor x\not\in C.$$ – John Griffin Sep 24 '17 at 1:17
• @JohnGriffin Why does it change to $\lor$ – lakada Sep 24 '17 at 1:22
• De Morgan's Law: $$\lnot (p \lor q) \equiv \lnot p \land \lnot q$$ $$\lnot (p \land q) \equiv \lnot p \lor \lnot q$$ – Andrew Tawfeek Sep 24 '17 at 1:24

Be careful while using De Morgan's Law. (Please refer to the Venn diagram attached blow.) $$x\in (A \cap B) \setminus (B\cap C) \Leftrightarrow x\in (A \cap B) \land x \notin (B\cap C) \Leftrightarrow (x \in A \land x\in B) \land (x \notin B \lor x \notin C) \Leftrightarrow x\in A \land x\in B \land x\notin C \Leftrightarrow x\in A \land (x\in B \land x\notin C) \Leftrightarrow x\in A \land x\in (B \setminus C) \Leftrightarrow x\in A \cap (B \setminus C)$$ • You can draw a Venn Diagram and get clear intuition from that. – Han Wang Sep 24 '17 at 1:34
• Can you show me a Venn Diagram for that, I am not sure how to make one. – lakada Sep 24 '17 at 1:43
• I drew a picture for you. – Han Wang Sep 24 '17 at 2:02

Just use the fact that $X \setminus Y = X \cap Y^c$. Thus we get \begin{align} (A \cap B) \setminus (B \cap C) &= (A \cap B) \cap (B \cap C)^{c} \\ &= (A \cap B) \cap (B^{c} \cup C^{c}) \\ &= ((A \cap B) \cap B^c) \cup ((A \cap B) \cap C^c)\\ &= (\emptyset) \cup (A \cap (B \cap C^c)) \\ &= A \cap (B \setminus C)\end{align}

$\begin{array} \ x \in (A \cap B) \land x \notin (B\cap C) &\iff x \in (A \cap B) \land \lnot \big(x \in (B\cap C)\big)\\ &\iff(x\in A \land x\in B) \land \lnot (x\in B \land x\in C) \\ &\iff (x\in A \land x\in B) \land (x\notin B \lor x\notin C) \\ &\iff \big((x\in A \land x\in B) \land x\notin B \big) \lor \big( (x\in A \land x\in B) \land x\notin C \big) \\ &\iff F \lor \big( x\in A \land x\in B \land x\notin C \big) \\ \end{array}$

I'm sure you could take over from here!

• What is $F$, False? – lakada Sep 24 '17 at 1:36
• @lakada That's correct, due to $x\in B \land x \notin B$. – Andrew Tawfeek Sep 24 '17 at 1:37