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