I'm asking for proof verification! That would be great!
Theorem:
$(A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$
Proof:
I'm using element chasing to show that $(A \setminus B) \cup (B \setminus A) \subseteq (A \cup B) \setminus (A \cap B)$ and $(A \cup B) \setminus (A \cap B) \subseteq (A \setminus B) \cup (B \setminus A)$.
-
First, let $x \in (A \setminus B) \cup (B \setminus A)$. Then we have three options:
-
$x \in A \setminus B \wedge x \in B \setminus A$, so $x \in A \cap B^C \wedge x \in B \cap A^C$. This mean that $x \in A \wedge x \in A^C$ so this is not possible.
-
$x \in A \setminus B \wedge x \notin B \setminus A$. Since $x \in A$, $x \in A \cup B$. Also, $x \notin B$, so $x \notin A \cap B$. Together $x \in (A \cup B) \setminus (A \cap B)$.
-
$x \notin A \setminus B \wedge x \in B \setminus A$. Since $x \in B \cap A^C$, $x \notin A$, so $x \notin A \cap B$. Also, $x \in B$, so $x \in A \cup B$. This means that $x \in (A \cup B) \setminus (A \cap B)$.
-
-
Then, let $x \in (A \cup B) \setminus (A \cap B)$. That is, $x \in A \cup B \wedge x \notin A \cap B$. Again, we have three options:
-
$x \in A \wedge x \in B$. This means that $x \in A \cap B$, but this contradicts that $x \notin A \cap B$, so this is not an option.
-
$x \in A \wedge x \notin B$. This means that $x \in A \cap B^C$, so that $x \in (A \cap B^C) \cup (B \cap A^C)$, that is, $x \in (A \setminus B) \cup (B \setminus A)$.
-
$x \notin A \wedge x \in B$. This means that $x \in A^C \cap B$, so that $x \in (A \cap B^C) \cup (B \cap A^C)$, that is, $x \in (A \setminus B) \cup (B \setminus A)$.
-
Best Answer
Your proof "works" and is correct, but the proof can proceed a bit more straightforward by simply unpacking the definitions of the set operations, and "chasing the element" through the implications. I'll demonstrate a more direct route for proving:
$$(A \setminus B) \cup (B \setminus A) \subseteq (A \cup B) \setminus (A \cap B)$$
Suppose $x \in (A\setminus B) \cup (B\setminus A)$.
Then $x\in A \setminus B\;$ OR $\;x \in B\setminus A.\;$ That is, $(x \in A \land x\notin B) \lor (x \in B \land x\notin A)$.
Then, (using the distributive law), we arrive at $(x \in A \lor x\in B) \land (x \notin A \lor x\notin B)$.
By DeMorgan's, this means $(x \in A \lor x \in B) \land \lnot (x \in A \land x \in B)$.
That is, $x \in (A \cup B) \land x\notin (A\cap B) \iff x \in (A\cup B)\setminus (A \cap B).$