[Math] Proof regarding an identity about the symmetric difference in set theory

elementary-set-theoryproof-verification

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

  1. First, let $x \in (A \setminus B) \cup (B \setminus A)$. Then we have three options:

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

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

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

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

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

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

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

Related Question