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

Problem: Prove that $A\cap (B\setminus C)=(A \cap B)\setminus(A \cap C)$.

I've tried it on my own: \begin{align} x&\in A\cap (B\setminus C) \\ &\Leftrightarrow (x\in A) \wedge (x\in B\setminus C) \\ &\Leftrightarrow (x\in A) \wedge (x\in B \wedge x\notin C) \\ &\Leftrightarrow (x\in A \wedge x\in B) \wedge (x\notin C) \\ &\Leftrightarrow x\in (A\cap B)\setminus C\\ &\Leftrightarrow \dots \end{align} What would the next step be? I've no idea how to get from $x\in (A\cap B)\setminus C$ to $x\in(A \cap B)\setminus(A \cap C)$.

If I'm trying to do the right side, we get \begin{align} x&\in(A \cap B)\setminus(A \cap C)\\ &\Leftrightarrow (x\in A \wedge x\in B)\wedge x\notin (A \cap C)\\ &\Leftrightarrow (x\in A \wedge x\in B)\wedge (x\notin A \wedge x\notin C)\\ &\Leftrightarrow \dots \end{align} How do I make it simpler?

• $(A \cap B)\setminus(A \cap C) = (A \cap B)\setminus C$ – Sammy Black Oct 22 '13 at 18:48
• In other words, you're done. Good job. – Sammy Black Oct 22 '13 at 18:49
• @AjmalW: The latter one is not correct: $x\notin (A \cap C)$ means $(x\notin A \vee x\notin C)$. – user35603 Oct 22 '13 at 18:56
• – Martin Sleziak Oct 22 '13 at 18:57

## 3 Answers

You replaced $x\notin A\cap C$ with $(x\notin A)\land(x\notin C)$, which is incorrect.

The correct one would be:

$$x\notin A\cap C \\ \Leftrightarrow \neg (x\in A\cap C)\\ \Leftrightarrow \neg (x\in A \land x\in C)\\ \Leftrightarrow (x\notin A)\lor (x\notin C)$$

Try, whether you can finish the problem using this.

• So $((x\in A) \wedge (x\in B))\wedge ((x\notin A) \vee (x\notin C))\Leftrightarrow ((x\in A) \wedge (x\in B))\wedge (x\notin C)$ because $x\notin A$ is false due to the existence of $x\in A$, according to @Martin Sleziak's first link? – UnknownW Oct 22 '13 at 19:59
• Other way to say this is that $(p\land q)\land(\neg p \lor r) \Leftrightarrow (p\land q)\land r$ is a tautology for any statements p, q, r. In this case we use this tautology for $p\equiv x\in A$, $q\equiv x\in B$ and $r\equiv x\in C$. – Martin Sleziak Oct 23 '13 at 6:01

This is why I like characteristic functions, see this answer.

With Characteristic functions we have

$$\chi_{(A \cap B)\setminus(A \cap C)}= \chi_{A \cap B}-\chi_{A \cap B}\chi_{A \cap C} =\chi_A \chi_B -\chi_A \chi_B\chi_A \chi_C \\ =\chi_A \chi_B -\chi_A \chi_B\chi_C= \chi_A( \chi_B -\chi_{B} \chi_C)=\chi_A \chi_{B \setminus C}=\chi_{(A \cap (B \setminus C)}$$

it's the same as multiplying a fractions, A . B then A . C = (A Union B )\ (A union C)

• For some basic information about writing math at this site see e.g. here, here, here and here. For example you can write $A\cup B$ using $A\cup B$ or $C\setminus D$ as $C\setminus D$. – Martin Sleziak Oct 29 '13 at 19:07