Given that $A$, $B$ and $C$ are sets, and that $(A ∪ B) \setminus C ⊆ A \setminus B$.

Prove that $(A \setminus C) ∩ B = ∅$.

I tried to prove it this way:

It is given that the containing set $(A \setminus B)$ doesn't contain any $x \in B$ (by the definition of set difference). Therefore, no $x \in B$ & $x \notin C$ exists. Therefore, in no way there is $x \in B$ & $x \notin C$ & $x \in A$ exists (equivalent to $(A \setminus C) ∩ B = ∅ )$.

I'm afraid my proof is incorrect, because $x \notin A$ seems unneccesary.
I'm a new student in the university in Israel, learning parallel to my highschool studies. English isn't my mother tongue. I am sorry for any mistakes and my bad formatting.
Thank you!


(Added by A.K. translation of the Hebrew in the image)

By the assumption every $x$ which belongs to $A$ or $B$, and does not belong to $C$ is necessarily an element of $A$ and not an element of $B$ (by the definitions of inclusion, union and difference). In the right hand side ($A\setminus B$) no element belongs to $B$, therefore it is impossible that in the left hand side there is an element which belongs to $B$. Therefore there is no $x\in B$ and $x\notin C$. In particular there is no such $x$ for which $$x\in A\land x\in B\land x\notin C$$ Q.E.D

  • $\begingroup$ I'm not certain what you mean by "containing set" in the first line of your proof. $\endgroup$ – user642796 Nov 11 '12 at 15:02
  • $\begingroup$ I mean A \ B. (the left part of the given expression) $\endgroup$ – Mark Segal Nov 11 '12 at 15:07
  • $\begingroup$ If you are not sure about the correctness of your terminology write it in Hebrew and I'll translate. $\endgroup$ – Asaf Karagila Nov 11 '12 at 15:08
  • $\begingroup$ @Asaf Kargila - I just did. Thanks! $\endgroup$ – Mark Segal Nov 11 '12 at 15:16

You have to prove that $A\setminus C$ is disjoint from $B$ (i.e. their intersection is empty), when you are given that $(A\cup B)\setminus C\subseteq A\setminus B$.

We need to show that if $x\in A\setminus C$ then $x\notin B$, and if $x\in B$ then $x\notin A\setminus C$. If we have shown both these things then there is no $x$ which is an element of both $A\setminus C$ and $B$, therefore $(A\setminus C)\cap B=\varnothing$.

Given $x\in B$ we know that $x\notin A\setminus B$ by the definition of $\setminus$. In particular this means that $x\notin (A\cup B)\setminus C$ (because the assumption was that $(A\cup B)\setminus C\subseteq A\setminus B$).

Therefore either $x\notin A\cup B$ or $x\in C$. Since we assume $x\in B$ we have to have that $x\in C$ as well. Therefore $x\notin A\setminus C$.

On the other hand, if $x\in A\setminus C$ we have that $x\in A$ and $x\notin C$. In particular this means that $x\in A\cup B$ and $x\notin C$ and therefore $x\in(A\cup B)\setminus C$. The assumption tells us, again, that $x\in A\setminus B$. Therefore $x\notin B$.

  • $\begingroup$ @amWhy: Thanks. We just finished covering this in our course... (which also happens to be in a university in Israel, but we didn't give this question in any of the sheets.) $\endgroup$ – Asaf Karagila Nov 11 '12 at 15:28
  • $\begingroup$ Thank you very much!!! Great answer. Thanks for the translation also. Took me a minute to grasp the English, but I finally understood the solution. $\endgroup$ – Mark Segal Nov 11 '12 at 15:34

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.