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?


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.

  • $\begingroup$ 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? $\endgroup$ – UnknownW Oct 22 '13 at 19:59
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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)

  • $\begingroup$ 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$. $\endgroup$ – Martin Sleziak Oct 29 '13 at 19:07

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.