Show that $A \setminus ( B \setminus C ) \equiv ( A \setminus B) \cup ( A \cap C )$

This is an exercise I was trying to do ( not homework ) and I got stuck as follows:

Working from $A \setminus ( B \setminus C )$:

$x \in A \wedge x \notin ( B \setminus C )$ $x \in A \wedge ((x \in B \wedge x \in C) \vee (x \notin B \wedge x \in C) \vee (x \notin B \wedge x \notin C) )$

At this point I'm not sure how to proceed.

Working from the other side $ ( A \setminus B) \cup ( A \cap C ) $:

$ x \in ( A \setminus B) \cup ( A \cap C ) $

$ x \in ( A \setminus B) \vee x \in ( A \cap C ) $

$ ( x \in A \wedge x \notin B ) \vee ( x \in A \wedge x \notin C ) $

$ x \in A \wedge (x \notin B \vee x \notin C ) $

$ x \in A \wedge x \notin ( B \cap C ) $

$ A \setminus ( B \cap C ) $

I could also use some formating tips like how display logical not and how to get the lines to display properly without blank lines inbetween. :-)

  • $\begingroup$ ,Why don't you use truth table ? $\endgroup$ – Peđa Terzić Sep 27 '11 at 7:23
  • $\begingroup$ You can use \to or \rightarrow $\endgroup$ – Asaf Karagila Sep 27 '11 at 7:24

Remember $x\in B\setminus C \iff x\in B\land x\not\in C$. Thus $x\not\in B\setminus C\iff x\not\in B\lor x\in C$ by de Morgan's laws.

So for some element $x$, $$ \begin{align*} x\in A\setminus (B\setminus C) &\iff x\in A \land (x\not\in B\setminus C)\\ &\iff x\in A \land (x\not\in B\lor x\in C). \end{align*} $$ But $$ \begin{align*} x\in (A\setminus B)\cup (A\cap C) &\iff x\in A\setminus B\lor x\in A\cap C\\ &\iff (x\in A\land x\not\in B)\lor (x\in A\land x\in C)\\ &\iff x\in A\land (x\not\in B\lor x\in C). \end{align*} $$

So you get $A \setminus ( B \setminus C ) = ( A \setminus B) \cup ( A \cap C )$.

  • $\begingroup$ Arg.. Two silly mistakes :-) I wrote the problem down wrong in my notepad, wrote A\C instead of A intersetion C. Now wonder I couldn't figure it out. $\endgroup$ – Robert S. Barnes Sep 27 '11 at 7:46

You can either write a table with all the possible locations of $x$ with respect to $A,B,C$ or you can use these identities (which you should prove, as they are most useful):

  • $(A\cup B)^c = A^c\cap B^c$

  • $A\setminus B = A\cap B^c$

  • $A\cup (B\cap C) = (A\cup B)\cap(A\cup C)$

  • $A\cap (B\cup C) = (A\cap B)\cup(A\cap C)$

Now we can proceed:

$$ A\setminus(B\setminus C) = A\setminus (B \cap C^c) = A\cap (B\cap C^c)^c = A\cap(B^c\cup C) = (A\cap B^c)\cup(A\cap C) $$

Where $\cdot ^c$ is the complement.

  • $\begingroup$ +1 for the info, but the point of this ex. was to use logical operators. $\endgroup$ – Robert S. Barnes Sep 27 '11 at 7:53

Exercises like this are often easy to solve using the characteristic function and its properties. For this, consider $A,B,C$ included in a big set $X$. And define $$ \chi_A : X \to \{0,1\}, \ \chi_A(x)=\begin{cases}1, & x \in A \\ 0, &x \notin A \end{cases} $$

It is easy to see that $\chi_{A\cap B}=\chi_A \chi_B, \chi_{A\cup B}= \chi_A+\chi_B-\chi_{A\cap B}, \chi_{A\setminus B}=\chi_A-\chi_A\chi_B$.

Moreover, two sets are equal if and only if they have the same characteristic function. In our case

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


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

Where we have used the obvious fact that $\chi_A^2=\chi_A$.

The two sets have the same characteristic function, therefore, they are equal. This method can be used to prove some more complicated set identities as $A\Delta (B \Delta C)=(A \Delta B)\Delta C$, which can get quite messy using just set operations properties.


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.