Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
To prove that $X=Y$ you need to show that if $x\in X$ then $x\in Y$ and that if $y\in Y$ then $y\in X$. Even though the two things you need to show can sometimes be proved simultaneously, I strongly advise that you not attempt that. It is too easy to lose control of the logic. –  André Nicolas Jul 18 '12 at 12:44

5 Answers 5

up vote 6 down vote accepted

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.

share|improve this answer
    
Thank you very much! –  pauliwago Jul 18 '12 at 7:29
    
Would you kindly explain the 3rd step? You went from x $\notin$ B) and x $\notin$ C to not (x $\in$ B or x $\in$ C). Why the or? –  pauliwago Jul 18 '12 at 13:53
1  
It's called De Morgan's Laws, I believe. –  David Wheeler Jul 18 '12 at 20:03

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.