0
$\begingroup$

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).

Screenshot

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)

is made.

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)]$? $\endgroup$ – Franz Drollig Mar 24 at 17:13
  • 1
    $\begingroup$ @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$. $\endgroup$ – st.math Mar 24 at 17:16
1
$\begingroup$

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$.)

$\endgroup$
1
$\begingroup$

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..

$\endgroup$

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.