Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
,Why don't you use truth table ? –  pedja Sep 27 '11 at 7:23
    
You can use \to or \rightarrow –  Asaf Karagila Sep 27 '11 at 7:24

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
+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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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