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.

I have several of these types of problems, and it would be great if I can get some help on one so I have a guide on how I can solve these.

The question is:

Prove $A \setminus (B\setminus C) \neq (A\setminus B) \setminus C$

I know I must prove both sides are not equivalent to each other to complete this proof. Here's my shot: We start with left side.

  • if $x$ is in $A$, then $x$ is not in $B$, not not in $C$
  • so $x$ is in $A$ and $C$
  • if $x$ is in $A$, then it's not in $B$ $\rightarrow$ $(A\setminus B)$
  • but if $x$ is in $A\setminus B$, then it must not be in $C$
  • however, earlier we stated $x$ is in both $A$ and $C$
  • we see that the two sides are not equal

Is this the right idea? Should I then reverse the proof to prove it the other way around, or is that unnecessary? Should it be more formal?

Thanks!

share|improve this question
1  
I'm assuming that by \ you meant \setminus (the relative complement). Also, the statement is not true for any $A$, $B$, and $C$; for example, if $B=C=\varnothing$, and $A$ is any set, then we do in fact have that $$A\setminus(B\setminus C)=(A\setminus B)\setminus C.$$ Please see here for how to typeset common math expressions with LaTeX, and see here for how to use Markdown formatting. –  Zev Chonoles Jul 18 '12 at 6:16
    
Yes, thank you for editing it for me. I'm a bit confused by your statement....would you kindly explain? –  pauliwago Jul 18 '12 at 6:20
    
@pauliwago In putting the slashes \ did you mean set difference or something else? –  Andrew Salmon Jul 18 '12 at 6:21
    
@pauliwago: As Andrew Salmon has also said below, the claim that $$A\setminus (B\setminus C)\neq (A\setminus B)\setminus C$$ for any sets $A$, $B$, and $C$ is false; that is, there are some choices for $A$, $B$, and $C$ for which it is instead the case that $$A\setminus (B\setminus C)\;\;\fbox{$=\strut$}\;\;(A\setminus B)\setminus C$$ –  Zev Chonoles Jul 18 '12 at 6:22
1  
The claim may or may not be true. When that happens you are note supposed to prove anything but look for a counterexample instead, i.e. examples of sets $A,B,C$ such that the equality does not hold. The claim you are supposed to refute that $A\setminus(B\setminus)$ is ALWAYS the same as $(A\setminus B)\setminus C$. –  Jyrki Lahtonen Jul 18 '12 at 6:37
show 4 more comments

4 Answers 4

up vote 4 down vote accepted

In order to show that equality does not always hold, you should produce specific examples of $A$, $B$ and $C$ where the two sides do not agree.

Note that the left-hand side is equivalent to $$\begin{align*} A\setminus (B\setminus C) &= A\setminus (B\cap C^c)\\ &= A\cap (B\cap C^c)^c\\ &= A\cap (B^c\cup C). \end{align*}$$ That is, the things that are in $A$ and either in $C$ or not in $B$.

On the other hand, the right hand side is equivalen to: $$\begin{align*} (A\setminus B)\setminus C &= (A\cap B^c)\setminus C\\ &= (A\cap B^c)\cap C^c\\ &= A\cap B^c\cap C^c \end{align*}$$ that is, the things that are in $A$, and not in $B$, and not in $C$.

So an easy way to find examples is to find one in which there is an element that is in both $A$ and $C$; then it will be on the left-hand side but not on the right-hand side.

So take $A=\{1\}$, $B=\varnothing$, $C=\{1\}$. Then $$A\setminus(B\setminus C) = \{1\}\setminus(\varnothing\setminus \{1\}) = \{1\}\setminus\varnothing = \{1\},$$ but $$(A\setminus B)\setminus C = (\{1\}\setminus\varnothing)\setminus\{1\} = \{1\}\setminus\{1\} = \varnothing.$$ This proves that equality does not always hold.

Note that there are cases where the two expressions are equal; for example, if $C$ is empty. More generally, if $A$ is disjoint from $C$, then $A\subseteq C^c$, so $(A\setminus B)\setminus C = A\setminus B$, and $$A\setminus (B\setminus C) = A\cap (B^c\cup C) = (A\cap B^c)\cup (A\cap C) = A\cap B^c$$ so the two are equal. This is the only situation where you have equality: if $x\in A\cap C$, then $x\in A\setminus(B\setminus C)$, but $x\notin $A\cap B^c\cap C^c=(A\setminus B)\setminus C$.

share|improve this answer
    
Thanks for your answer. What does that small C indicate? –  pauliwago Jul 18 '12 at 6:41
    
It indicates the complement of a set. –  Andrew Salmon Jul 18 '12 at 7:47
add comment

$(\varnothing \setminus \varnothing) \setminus \varnothing = \varnothing \setminus ( \varnothing \setminus \varnothing)$, so you can't prove that they are not equal. However, you CAN find a counterexample that violates the propositiong $ A \setminus (B \setminus C) = (A \setminus B) \setminus C$.

For example, set $A = B = C = \{1\}$ Then, the left side of the equality is equal to $\{1\}$, but the right side is equal to $\varnothing$.

share|improve this answer
    
I see your reasoning here. So I guess this proof is invalid... –  pauliwago Jul 18 '12 at 6:28
4  
@pauliwago: The approach is wrong. To show that the two sets are not necessarily equal (there are cases where they are!) you have to exhibit a specific instance in which they are not equal. That is, you need a counterexample to the equality, not a proof that they are never equal (because it is false that they are never equal). –  Arturo Magidin Jul 18 '12 at 6:32
    
Actually you don't even have to use a specific set (your $\{1\}$). Just $A=B=C$ suffices. Then $(A\setminus A)\setminus A=\emptyset$ but $A\setminus(A\setminus A)=A$. Indeed, even $A=C$ is sufficient, so specifying $B$ isn't needed either. –  celtschk Jul 18 '12 at 13:59
    
@ArturoMagidin: He did give a counterexample. First he gave a counterexample to $A\setminus(B\setminus C)\neq(A\setminus B)\setminus C$, then he gave a counterexample to $A\setminus(B\setminus C)=(A\setminus B)\setminus C$. –  celtschk Jul 18 '12 at 14:03
    
@celtschk: Andrew did. The original poster, pauliwago, did not. I understood the comment pauliwago made here to refer to his own "proof" in the original post, not to Andrew Salmon's examples here. –  Arturo Magidin Jul 18 '12 at 16:04
show 1 more comment

To find an example to show that $A\setminus(B\setminus C)$ is not necessarily equal to $(A\setminus B)\setminus C$, think like this.

Look at $A\setminus(B\setminus C)$. If $B=C$, we will be taking away nothing from $A$. But (most of the time) $(A\setminus B)\setminus C$ takes something away from $A$.

Now for details. Let $A=\{1,2\}$, $B=C=\{2\}$. Then $B\setminus C$ (everything in $B$ which is not in $C$) is the empty set. So $A\setminus(B\setminus C)=\{1,2\}$.

But $A\setminus B=\{1\}$, and therefore $(A\setminus B)\setminus C=\{1\}.$

share|improve this answer
add comment

Alternatively, as a more general solution, you can calculate for which sets the equality holds: \begin{align} & A \setminus(B \setminus C) \;=\; (A \setminus B) \setminus C \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & \langle \forall x :: x \in A\setminus(B \setminus C) \;\equiv\; x \in (A \setminus B) \setminus C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, two times"} \\ & \langle \forall x :: x \in A \land \lnot(x \in B \setminus C) \;\equiv\; x \in (A \setminus B) \land \lnot(x \in C) \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, two more times"} \\ & \langle \forall x :: x \in A \land \lnot(x \in B \land \lnot(x \in C)) \;\equiv\; (x \in A \land \lnot(x \in B)) \land \lnot(x \in C) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: use DeMorgan; simplify"} \\ & \langle \forall x :: x \in A \land (x \not\in B \lor x \in C) \;\equiv\; x \in A \land x \not\in B \land x \not\in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: extract common part from both sides of $\;\equiv\;$"} \\ & \langle \forall x :: x \in A \Rightarrow (x \not\in B \lor x \in C \;\equiv\; x \not\in B \land x \not\in C) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify: $\;P \lor Q \equiv P \land \lnot Q\;$ is equivalent to $\;\lnot Q\;$"} \\ & \langle \forall x :: x \in A \Rightarrow x \not\in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rewrite $\;\Rightarrow\;$ -- so that we can go back to set notation"} \\ & \langle \forall x :: \lnot(x \in A \land x \in C) \rangle \\ \equiv & \;\;\;\;\;\text{"introduce $\;\cap\;$ and $\;\emptyset\;$ using their definitions"} \\ & A \cap C = \emptyset \\ \end{align} So any sets $\;A\;$ and $\;C\;$ which have at least one element in common are a counterexample.

share|improve this answer
add comment

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.