Prove $A-(B-C) = (A-B) \cup (A \cap B \cap C)$ :

What I think of doing is showing the LHS is a subset of the RHS and the RHS is a subset of the LHS, then the RHS = LHS.


We have $x \in A$, but $x \notin (B-C)$, thus $x \in (A-B)$ and then we see that $x \in (A-B) \cup (A \cap B \cap C)$. And we have the LHS a subset of the RHS.


3 cases:

1.) $x \in (A-B)$ only

from this we see that the RHS is a subset of the LHS

2.) $x \in (A \cap B \cap C)$ only

This is not possible. Exclude this from our discussion.

3.) $x \in (A-B) \wedge x \in (A \cap B \cap C) $

This is not possible. Exclude this from our discussion.

Thus, the RHS is a subset of the LHS, shown by case 1.

Since the LHS is a subset of the RHS and the RHS is a subset of the LHS, then the LHS = RHS and

$A-(B-C) = (A-B) \cup (A \cap B \cap C) $

Is this methodology right. I have more details in the proof I constructed but wanted to know if this method of thinking is good for the proof. Thanks!


You could use a Venn Diagram:

enter image description here

Unless the goal was to learn the specific axioms of a theory, I wouldn't make the problem harder than it has to be.


$$(A-B)\cup(A\cap B\cap C)=(A\cap B')\cup(A\cap B\cap C)=A\cap (B'\cup(B\cap C))=A\cap((B'\cup B)\cap (B'\cup C))=A\cap (B'\cup C)=A\cap (B\cap C')'=A-(B-C)$$

  • $\begingroup$ But wouldn't you need to prove this the other way as well? Makes sense for the direction you showed. $\endgroup$
    – SilverCat
    Jan 13 '15 at 23:40
  • $\begingroup$ I do not understand your comment $\endgroup$
    – CLAUDE
    Jan 13 '15 at 23:41
  • $\begingroup$ You proved (A−B)∪(A∩B∩C) = A - (B- C), but now you would need to prove that A -(B - C) = (A−B)∪(A∩B∩C) right? $\endgroup$
    – SilverCat
    Jan 13 '15 at 23:43
  • $\begingroup$ No, Because if $a=b$, then $b=a$. Isn't it ? $\endgroup$
    – CLAUDE
    Jan 13 '15 at 23:44
  • 1
    $\begingroup$ @bobbydaCat You have the option of either proving that $L.H.S.\subseteq R.H.S.$ and $R.H.S. \subseteq L.H.S.$ to prove $L.H.S.=R.H.S.$, or you can use identities (strings of equalities that are always true) and algebraic manipulation like AMIR did above since '$=$' is an equivalence relation and if $a_1 = a_2 = \dots = a_n$ then $a_1 = a_n$. In effect $=$ signs are an "if and only if" in that the argument can be read front to back and back to front and is valid in both directions. In doing it as AMIR did, it requires less case-arguments and is more compact a proof. $\endgroup$
    – JMoravitz
    Jan 14 '15 at 0:20

Its much easier to work with indicator function. An indicator function $I_A$ of a subset $A$ is defined as: $$ I_{A}(x)=\begin{cases} 1 & x\in A\\ 0 & x\not\in A \end{cases} $$

Some basic rules: $$ A=B\quad \text{iff}\quad I_A=I_B $$ and $$ I_{A\cap B}=I_AI_B,\quad I_{A^c}=1-I_A,\quad I_{A-B}=I_{A\cap B^c}=I_A(1-I_B) $$ and $$ I_{A\cup B}=1-I_{(A\cup B)^c}=1-I_{A^c\cap B^c}=1-(1-I_A)(1-I_B),\quad I_A^2=I_A $$ Working from the left side: \begin{align} I_{A-(B-C)} &=I_A(1-I_{B-C})=I_A(1-I_B(1-I_C)) \\ &=I_A-I_AI_B+I_AI_BI_C \\ &=I_A - I_{A \cap B} + I_{A \cap B \cap C} \\ &= I_{A - (A \cap B) \cup (A \cap B \cap C)} \\ &= I_{(A-B) \cup (A \cap B \cap C)} \end{align}

from which the result follows.

  • $\begingroup$ This basically amounts to showing that both are equal to $(A \setminus (A \cap B)) \cup (A \cap B \cap C)$. I'm not sure this is really any easier than just doing it that way directly. $\endgroup$
    – Ian
    Jan 14 '15 at 0:33
  • $\begingroup$ @Ian This way is foolproof, and is indeed the best way. Do you find working with intuition very helpful in general? If it helps to convince you, this method is recommended by the late Chung Kai-Lai. $\endgroup$
    – Troy Woo
    Jan 14 '15 at 0:36
  • $\begingroup$ While it will work and it saves one memorizing the algebraic rules for sets, the algebra in the second part is rather laborious. You were really done after just doing the algebra in the first part, because $I_A - I_A I_B = I_{A - B}$ and $I_A I_B I_C = I_{A \cap B \cap C}$. Hence $I_A - I_A I_B + I_A I_B I_C = I_{(A - B) \cup (A \cap B \cap C)}$ without all the work in the second part. $\endgroup$
    – Ian
    Jan 14 '15 at 0:40
  • $\begingroup$ @Ian Feel to free to modify my answer. $\endgroup$
    – Troy Woo
    Jan 14 '15 at 0:44
  • $\begingroup$ Done, you can roll it back if you want. $\endgroup$
    – Ian
    Jan 14 '15 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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