# Proving $(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$

In this exercise sheet (German) there is the following problem: Prove that $$(A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$$. There is a solution shown below (und means and, oder means or).

I don't understand how the transition from

$$x\in (A\cup B) \wedge x\notin(A\cap B)$$ (item 1 above)

to

$$(x \in A \wedge x \notin B) \vee (x \in B \wedge x \notin A)$$ (item 2)

The only thing that comes to mind is De Morgan's law. Then

$$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee \neg (x \notin (A \cap B))$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee (x \in (A \cap B))$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee \neg(x \in A \wedge x \in B)$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee (x \notin A \vee x \notin B)$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee (x \notin A \vee x \notin B)$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff \neg (x \in A \wedge x\notin B) \vee (x \notin A \vee x \notin B)$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff (x \notin A \vee x\in B) \vee (x \notin A \vee x \notin B)$$ $$x\in (A\cup B) \wedge x\notin(A\cap B) \iff x \notin A \vee x\in B \vee x \notin A \vee x \notin B$$

The problem is that I have two $$x\notin A$$, whereas in the solution from the exercise there is one $$x\in A$$ and one $$x\notin A$$.

Where exactly did I make a mistake?

This would be one way of proving it:

$$x\in (A\cup B) \wedge x\notin(A\cap B)$$

$$\iff (x\in A\lor x\in B)\land \neg(x\in A\land x\in B)$$

$$\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)]$$

$$\iff(x\in A\land x\notin A)\lor(x\in B\land x\notin A)\lor (x\in A\land x\notin B)\lor(x\in B\land x\notin B)$$

$$\iff (x\in B\land x\notin A)\lor (x\in A\land x\notin B)$$

And, to continue:

$$\iff (x\in B\setminus A)\lor (x\in A\setminus B)$$

$$\iff x\in (B\setminus A)\cup(A\setminus B)$$

• What rule/law did you use to go from $(x \in A \vee x \in B)$ to $[(x \in A \vee x \in B) \wedge (x \notin A)]$? – Franz Drollig Mar 24 at 17:13
• @FranzDrollig Distributivity; in this case: $(x\lor y)\land (z\lor w)\iff [(x\lor y)\land z]\lor[(x\lor y)\land w]$. This is simliar to distributivity for real numbers, $(a+b)(c+d)=(a+b)c+(a+b)d$. – st.math Mar 24 at 17:16

The statement $$x\in (A\cup B)\backslash (A\cap B)$$ is equivalent to the statement $$x\in (A\backslash B)\cup (B\backslash A)$$ because both are equivalent to $$(x\in A)\not\equiv(x\in B)$$.

Or if you prefer a proof by diagrams, both statements imply $$x$$ is in one of two intersecting circles that denote $$A,\,B$$, but not in their intersection. (The part of one circle that doesn't intersect the other denotes $$A\backslash B$$; with the other circle, we get $$B\backslash A$$.)

Once you know $$x \in A \cup B$$ and $$x \notin A \cap B$$, you have two cases: $$x \in A$$ and $$x \in B$$, from the union. If $$x \in A$$ we know $$x \notin B$$ (or else $$x\in A \cap B$$, which is not the case) and if $$x \in B$$ in the same way : $$x \notin A$$. Hence the step from (1) to (2) in your proof. No need for heavy formula manipulation, just simple reasoning..