Proof of $(A - B) - C = A - (B \cup C)$

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. I tried asking another problem, but it turned out to be a special case problem, so hopefully this one works out normally.

The question is:

Prove $(A - B) - C = A - (B \cup 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 \in C$, then $x \notin A$ and $x \in B$.
• So $x \in (B \cup C)$
• So $A - (B \cup C)$

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!

Solution 1:

The normal way to prove equalities like this one is in two steps. First, show that if some $x \in$ LHS, then it must also be $\in$ RHS. Then, you must show that if $x\in$ RHS, then it must also be $\in$ RHS. These two together are enough to prove that LHS = RHS.

So, in this specific example, step 1 looks like this.

$x\in (A\backslash B)\backslash C$

$\Rightarrow ( x\in A$ and $x\notin B )$ and $x\notin C$

$\Rightarrow x\in A$ and not $(x\in B $ or $x\in C)$

$\Rightarrow x\in A$ and $x\notin B \cup C$

$\Rightarrow x\in A \backslash ( B \cup C )$

So that's the first half. I have left the second half as an exercise for you to solve yourself.

Note that there are other ways of solving such questions, but this is probably the most straightforward. Good luck.

Solution 2:

In the case of very simple expressions like this, an alternative approach is to use "truth tables". Essentially, one considers, for an element $x$, all possible combinations of whether it is or it not in any given set, and computes whether it is in the set determined by the complex expression. Here, with three sets, we need to consider $8$ possibilities.

Use $0$ to denote that the element is not in the set, and $1$ to denote that it is. Remembering that $x\in X-Y$ if and only if $x\in X$ and $x\notin Y$, we have: $$\begin{array}{|c|c|c||c|c|} \hline A&B&C&A-B&(A-B)-C\\ \hline 0 & 0 & 0& 0 & 0\\ \hline 0 & 0 & 1 & 0 & 0\\ \hline 0 & 1 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 0 & 0\\ \hline 1 & 0 &0 & 1 & 1\\ \hline 1 & 0 & 1 & 1 & 0\\ \hline 1 & 1 & 0 & 0 & 0\\ \hline 1 & 1 & 1 &0 & 0\\ \hline \end{array}$$

For $A-(B\cup C)$, we have: $$\begin{array}{|c|c|c||c|c|} \hline A&B&C&B\cup C&A-(B\cup C)\\ \hline 0 & 0 & 0& 0 & 0\\ \hline 0 & 0 & 1 & 1 & 0\\ \hline 0 & 1 & 0 & 1 & 0\\ \hline 0 & 1 & 1 & 1 & 0\\ \hline 1 & 0 &0 & 0 & 1\\ \hline 1 & 0 & 1 & 1 & 0\\ \hline 1 & 1 & 0 & 1 & 0\\ \hline 1 & 1 & 1 &1 & 0\\ \hline \end{array}$$

Now look at the final column: since the columns for $A-(B\cup C)$ and for $(A-B)-C$ are identical, it follows that the sets are the same.

Now, for large number of "sets", this technique becomes unwieldly: the table will have $2^n$ rows when the equation involves $n$ different sets. But for small numbers of sets (two or three, usually), it provides a simple, mechanical way of testing for equality. For example, the truth-table method is much simpler to prove the associativity of the symmetric difference than element-wise methods.

Solution 3:

Depending on how much you are allowed to assume (De Morgan's laws, etc), you can also just show this algebraically via the identity $X\setminus Y = X\cap \bar{Y}$.

It's a couple of applications of that identity, one associativity step and one De Morgan step, to give the outline. (It's really simple, so I don't want to completely give it away)

Also, before the editor gets to this, don't change my $\setminus$ to $-$, I don't like the ambiguity.

Solution 4:

Working with the Characteristic function of a set makes these problems easy:

$$1_{(A - B) - C}= 1_{A-B} - 1_{A-B}1_C=(1_A- 1_A1_B)-1_A1_C+ 1A1_B1_C \,$$

$$1_{A-(B \cup C)}= 1_{A}- 1_{A}1_{B \cup C}=1_A- 1_A ( 1_B+ 1_C -1_B1_C)\,$$

It is easy now to see that the RHS are equal.

Solution 5:

In a variation of the currently approved answer, I would prove this through the following simple calculation: for every $x$,

$$ \begin{array}{ll} & x \in (A - (B \cup C)) \\ \equiv & \;\;\;\text{"definition of $-$"} \\ & x \in A \land \lnot (x \in (B \cup C)) \\ \equiv & \;\;\;\text{"definition of $\cup$"} \\ & x \in A \land \lnot (x \in B \lor x \in C) \\ \equiv & \;\;\;\text{"logic"} \\ & x \in A \land \lnot (x \in B) \land \lnot (x \in C) \\ \equiv & \;\;\;\text{"definition of $-$, to work towards our goal"} \\ & x \in (A - B) \land \lnot (x \in C) \\ \equiv & \;\;\;\text{"definition of $-$"} \\ & x \in ((A - B) - C) \\ \end{array} $$

By the definition of set equality, this proves the given theorem.