How to prove $(A - B) - C \subseteq A - (B - C)$

58 Views Asked by At

Here is what I have so far:

Suppose $x \in (A - B) - C$

So $(x \in A \land x \notin B) \land x \notin C$

Then, using the associative law we can say,

$x \in A \land (x \notin B \land x \notin C)$

But here is my problem. I'm not sure what the next step is because $(x \notin B \land x \notin C)$ does not equal $B - A$.

Am I missing something?

2

There are 2 best solutions below

3
On

So far so good, you have correctly proved that $x \in (A \setminus B) \setminus C \iff x \in A \land (x \not\in B \land x \not\in C)$.

Now you want to prove that this implies that $x \in A \setminus (B \setminus C)$. By definition this is equivalent to $x \in A \land x \not \in B \setminus C$. Again by definition, $x \in B \setminus C \iff x \in B \land x \not\in C$, hence by De Morgan's law, $$x \not\in B \setminus C \iff \neg(x \in B \land x \not\in C) \iff x \not \in B \lor x \in C.$$ Hence you want to prove: $$x \in A \land (x \not\in B \land x \not\in C) \implies x \in A \land (x \not \in B \lor x \in C).$$

But of course you have $x \not\in B \land x \not\in C \implies x \not\in B$, and in turn $x \not\in B \implies x \not \in B \lor x \in C$. So the implication above is true, because if $Q \implies R$, then $P \land Q \implies P \land R$ for any propositions $P$, $Q$ and $R$.


More concretely, $(A \setminus B) \setminus C$ is the set of elements of $A$ that are neither in $B$ nor in $C$. On the other hand, $A \setminus (B \setminus C)$ is the set of elements of $A$, minus the elements in $B$ except those that are in $C$. It's clear that if an element is not in $B$ then it's not in $B \setminus C$, and so the proposition follows. The difference between the two sets is precisely the set of elements that are in $A$ and $C$ but not in $B$; they're in the second set but not the first.

0
On

$x \in A \land (x \notin B \land x \notin C)$

Use De-Morgan's law ,

$\implies x\in A\land x\notin (B\cup C)$.

Since $(B-C)\subseteq (B\cup C)$

$\implies x\in A\land x\notin (B-C)$

$\implies x\in A-(B-C)$