# Prove or disprove: $A-(B-C) = (A-B)-C$

This is what I have so far:

First, we will attempt to show $A-(B-C) \subseteq (A-C) - C.$ Let $x \in A -(B-C)$. Then $x\in A$ and $x \notin (B-C)$. By DeMorgan's we have that $$x \notin (B-C) = x \notin B \vee x \in C.$$ We have that $x \in A \wedge (x \notin B \vee x \in C)$. Then we have that $(x \in A \wedge x \notin B) \vee (x \in A \wedge x \in C)$.

So by definition of $\cup$ and $\cap$, we have $x \in (A-B) \cup (x\in (A \cap C))$. I'm kind of stuck here.

I can see a contradiction here in that LHS says $x \in C$ but the RHS says $x \notin C$.

Can anyone tell me what to do from here? I'm not quite sure how to formally state that the statement is false. I feel like I'm not being complete here.

• In order to disprove this statement, it suffices to find a counterexample, i.e. sets $A,B,C$ that don't satisfy the claimed identity. See below for one such example. – Stefan Mesken Nov 4 '16 at 4:29
• @testpilot No, if $A,B,C$ are disjoint (in fact, if $A$ is disjoint from $B$ and $C$), then this identity always holds. Both sides just evaluate to $A$. – Stefan Mesken Nov 4 '16 at 4:32
• just need one element. If you have x in C then x won't be in the LHS but might be in the right hand side under what conditions? Well, it has to be in A of course but if it isn't in B it won't be omitted. So just need x in A and x in C but X not in B. Let A = {1} B = emptyset C = {1}. RHS = {1}, LHS = empty set. – fleablood Nov 4 '16 at 4:41
• If $B=\emptyset$ then the left side is $A$ and the right side is $A-C.$ Do you think $A=A-C$ is a valid identity? – bof Nov 4 '16 at 4:42
• The natural numbers are an instructive special case. – Jacob Wakem Nov 4 '16 at 5:12

Let $A=B=C = \{1\}$. Then $$(A - B) - C = \emptyset,$$ but $$A-(B-C) = \{1\} - \emptyset = \{1\} \neq \emptyset.$$

You can use your observation to create a counterexample. I claim that if $x \in A \cap C$, then $x \in A-(B-C)$ (the left-hand side), but $x \notin (A-B)-C$ (the right hand side). Do you see why?

To create a counterexample, come up with (very simple) sets $A, B,$ and $C$ and an element $x \in A \cap C$. Then explicitly compute what $A-(B-C)$ and $(A-B)-C$ are, and show they are not the same.

Note subtraction is not associative in the natural numbers. If A,B,C are finite with natural cardinalities and C is a subset of B is a subset of A then the cardinality on either side is determined precisely by this subtraction on the cardinalities. But the cardinalities not being equal,the corresponding sets are not equal.

Let X <=Y if x is a subset of Y. Note if X<=Y, Z-X>=Z-Y. B-C <=B . Thus A-(B-C)>=A-B . A-(B-C)-nullset>=A-B-C similarly. It is easily shown when we have one strict inequality between B-C and B or the nullset and C our final inequality is strict and the theorem fails. When we have no such strict inequality by antisymmetry of <= the equation holds. That is, when C is disjoint from B and C is not the nullset.

Why would you start trying to prove some random identity without first testing it in some easily computed cases to see if it's right or wrong??? Because I like to look for easy solutions before hard ones, I always try plugging in zero for one of the variables, or in this case because we're dealing with sets, the empty set.

If $A=\emptyset$ then $A-(B-C)=(A-B)-C$ turns into $\emptyset=\emptyset,$ check.

If $C=\emptyset$ it turns into $A-B=A-B,$ check.

If $B=\emptyset$ it turns into $A=A-C.$ Now that looks fishy, doesn't it? What if $C=A,$ then we get $A=\emptyset.$ That sure isn't an identity . . .

Counterexample: Let $B=\emptyset$ and $A=C=\mathbb R$ (or any nonempty set). Then $$A-(B-C)=\mathbb R-(\emptyset-\mathbb R)=\mathbb R-\emptyset=\mathbb R$$ while $$(A-B)-C=(\mathbb R-\emptyset)-\mathbb R=\mathbb R-\mathbb R=\emptyset.$$