I have been asked to prove that: $(A \cup B)$ \ $(A \cap B) = (A$ \ $B) \cup (B$ \ $A)$

I have got this far in the proof:

$(A \cup B)$ \ $(A \cap B)$

$(x \in (A \cup B)) \land (x \not \in (A \cap B))$ - definition of set difference

$(x \in A \lor x \in B) \land (x \notin A \land x \notin B)$ - definition of set union and set intersection

I can't see how to go any further, as using the distributive laws may get quite complicated considering there are 2 things either side of the conjunctive operator. Is this the right direction to head or have I started off on the wrong foot?

  • $\begingroup$ Assume for example $x\notin B\\A$, and prove it's in A\\B$. $\endgroup$ – hamam_Abdallah Oct 27 '16 at 13:21
  • $\begingroup$ This is the right direction. Please continue and distribute the first parenthesis on the second one. $\endgroup$ – Hamed Baghal Ghaffari Oct 27 '16 at 13:24
  • $\begingroup$ Please do not vandalize your own post. It has received upvoted answers, and should not be deleted. $\endgroup$ – Noah Schweber Oct 27 '16 at 15:49
  • $\begingroup$ I have been asked by my university for it to be taken down, however it isn't letting me so I am unsure on what to do. $\endgroup$ – A-Lill Oct 27 '16 at 16:05
  • 1
    $\begingroup$ You would need to ask your university to contact the company directly and file a DMCA takedown notice, see point 15 in the legal matters. $\endgroup$ – Daniel Fischer Oct 27 '16 at 16:15

HINT: Go back one step and the next step should be:

$$(x \in A ∨ x \in B) ∧ (x \not \in A \cap B)$$ $$(x \in A ∧ (x \not \in A \cap B)) ∨ (x \in B ∧ (x \not \in A \cap B))$$

  • $\begingroup$ Eventually, the OP is going to need to confront the fact that $$x \notin (A\cap B), \text{ means } (x \notin A)\lor (x \notin B)$$ I confronted his/her mistake at the start of my answer, and then proceeded. Unfortunately you failed to address or reference the OP's error, and why it is an error. You conveniently avoided it. $\endgroup$ – Namaste Oct 27 '16 at 18:00
  • $\begingroup$ @amWhy Do we really need to use that? From $(x \in A ∧ (x \not \in A \cap B))$ we can immeadiately conclude that $(x \in A ∧ x \not \in B) \implies x \in A$\ $ B $. $\endgroup$ – Stefan4024 Oct 27 '16 at 18:02
  • $\begingroup$ @amWhy Yes, the OP made a mistake, but this is another and maybe a better way to solve the problem. $\endgroup$ – Stefan4024 Oct 27 '16 at 18:04
  • $\begingroup$ Given the detail fiven by the OP, and the fact that $s/he$ is very new to this, I would never assume anything. Yes, I know what you know, what follows, Obviously, the OP fails to recognize what you failed to address, and that's the need for DeMorgans. As the OP saw it, what follows from your one line answer (first disjunct) is nothing more than $x \in A \land x \notin A \land x \notin B$. This is clearly false. $\endgroup$ – Namaste Oct 27 '16 at 18:09
  • $\begingroup$ Similarly, the OP's process would be to take from your second conjunct, $$x \in B \land x\notin A\land x \notin B$$ Also false. By failing to address the fact that DeMorgans is needed to show $$(x \notin (A\cap B)) \equiv (x\notin A \lor x\notin B)$$ you've done little for the OP except to validate his/her initial incorrect statement. $\endgroup$ – Namaste Oct 27 '16 at 18:16

The final line in your proof attempt has one error.

Let's go back one step to your correct statement:

$$\begin{align} &\iff (x\in (A\cup B)) \land (x\notin (A \cap B))\\ \\ &\iff (x \in A \lor x \in B) \land \lnot (x \in A \cap B)\\ \\ &\iff (x \in A \lor x \in B) \land \lnot ((x \in A) \land (x \in B))\\ \\ &\iff (x \in A \lor x \in B) \land (\lnot (x \in A) \lor \lnot (x \in B))\tag{DeMorgan's}\\ \\ &\iff ((x \in A) \lor (x \in B)) \land ((x \notin A) \lor (x \notin B))\\ \\ &\iff [((x\in A) \lor (x \in B)) \land (x\notin A)] \lor [((x \in A) \lor (x\in B)) \land x\notin B] \end{align}$$

If you distribute again, you have (excluding $((x \in A) \land (x\notin A))$, and also excluding $((x \in B) \land (x \notin B))$), $$((x \in B) \land (x \notin A)) \lor ((x\in A) \land (x\notin B))$$ Now you can read off the definitions to get the desired goal.

Also, since each step is birectional, it suffices to conclude the equality of the sets.


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.