2
$\begingroup$

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

  • 0
    You ca$n$ use `\to` or `\rightarrow`2011-09-27

3 Answers 3

2

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.

5

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.

  • 0
    +1 for the info, but the point of this ex. was to use logical operators.2011-09-27
4

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

  • 0
    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.2011-09-27