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

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. :-)

• ,Why don't you use truth table ? – Peđa Terzić Sep 27 '11 at 7:23
• You can use \to or \rightarrow – 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 )$.

• 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. – 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.

• +1 for the info, but the point of this ex. was to use logical operators. – 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$$

and

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