0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $$ $\endgroup$ – John Griffin Sep 24 '17 at 1:17
  • $\begingroup$ @JohnGriffin Why does it change to $\lor$ $\endgroup$ – lakada Sep 24 '17 at 1:22
  • $\begingroup$ De Morgan's Law: $$\lnot (p \lor q) \equiv \lnot p \land \lnot q$$ $$\lnot (p \land q) \equiv \lnot p \lor \lnot q$$ $\endgroup$ – Andrew Tawfeek Sep 24 '17 at 1:24
2
$\begingroup$

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) $$ enter image description here

$\endgroup$
  • 1
    $\begingroup$ You can draw a Venn Diagram and get clear intuition from that. $\endgroup$ – Han Wang Sep 24 '17 at 1:34
  • $\begingroup$ Can you show me a Venn Diagram for that, I am not sure how to make one. $\endgroup$ – lakada Sep 24 '17 at 1:43
  • 1
    $\begingroup$ I drew a picture for you. $\endgroup$ – Han Wang Sep 24 '17 at 2:02
3
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

$\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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.