1
$\begingroup$

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!

  • 1
    I'm assuming that by \ you meant `\setminus` (the [relative complement](http://en.wikipedia.org/wiki/Complement_(set_theory)#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](http://meta.stackexchange.com/a/70559/161783) for how to typeset common math expressions with LaTeX, and [see here](http://meta.stackoverflow.com/editing-help) for how to use Markdown formatting.2012-07-18
  • 0
    Yes, thank you for editing it for me. I'm a bit confused by your statement....would you kindly explain?2012-07-18
  • 0
    @pauliwago In putting the slashes \ did you mean set difference or something else?2012-07-18
  • 0
    @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$$2012-07-18
  • 0
    I'm not sure what the terminology is, but I just know that if x is in A, then x is not in (B\C)2012-07-18
  • 0
    @pauliwago: Some other commands that may help you express yourself better here are `\in` (to produce $\in$), `\notin` (to produce $\notin$), and `\lnot` (to produce $\lnot$).2012-07-18
  • 0
    Sorry about that. So x $\in$ A & x $\notin$ B\C2012-07-18
  • 0
    @pauliwago you can also use "\land" to write $\land$. and "\lor" to write $\lor$.2012-07-18
  • 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$.2012-07-18

4 Answers 4

0

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.

5

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

  • 0
    I see your reasoning here. So I guess this proof is invalid...2012-07-18
  • 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).2012-07-18
  • 0
    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.2012-07-18
  • 0
    @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$.2012-07-18
  • 0
    @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.2012-07-18
  • 0
    @ArturoMagidin: Ah, I see. I didn't notice that the comment was by the same person who asked the question. Anyway, using "this" in that context to refer to anything but the answer is definitely confusing ... but you could have helped avoiding the confusion by explicitly writing "your approach" instead of "the approach".2012-07-18
4

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

  • 0
    Thanks for your answer. What does that small C indicate?2012-07-18
  • 0
    It indicates the complement of a set.2012-07-18
1

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