# Proof for the symmetric difference?

I want to prove that:

a)

$A \Delta B = \emptyset \Leftrightarrow A = B$

Prove for $\Leftarrow$

Then:

$A \Delta B = (A$ \ $A) \cup (A$\ $A) = \emptyset$

Prove for $\Rightarrow$

Then(proof by contrapositive):

$A = B \rightarrow (A$ \ $B) \cup (A$\ $B) = (A$ \ $B) \cup (A$\ $B)= \emptyset$

b)

$A \Delta B = A \cup B \Leftrightarrow A \cap B = \emptyset$

Prove for $\Leftarrow$

$A \Delta B \rightarrow (A \cup B)$ \ $(A \cap B) = ( A \cup B) \rightarrow ( A \cap B) = \emptyset$

Prove for $\Rightarrow$

Then(proof by contrapositive):

$A \Delta B \rightarrow (A \cup B)$ \ $\emptyset = ( A \cup B) \rightarrow ( A \cap B) = ( A \cap B)$

I am not sure if these two proves are correct. I really appreciate your answer!

-
On a very formal level, $(A\cup B)\setminus(A\cap B)=A\cup B$ does not immediately give $A\cap B=\emptyset.$ At least $X\setminus Y=X$ does not imply $Y=\emptyset$. So you may want to add some detail there. – Hagen von Eitzen Jul 31 '13 at 14:30
@HagenvonEitzen: Suppose $A \cap B \neq \emptyset$. Then we can choose some $x$ such that $x \in A \cap B$. This means that $x \in A$ and $x \in B$. Since $x \in A$, it follows that $x \in A \cup B$. But then since $A \Delta B = A \cup B$, $x \in A \Delta B$, so $x \in A \cup B$ and $x \notin A \cap B$. This contradicts the fact that $x \in A \cap B$. Therefore $A \cap B = \emptyset$. – user21530 Jul 31 '13 at 23:38

a) ($\rightarrow$) Suppose $A \Delta B = \emptyset$. Let x be an arbitrary element of A. Suppose $x \notin B$. Then since $x \in A$ and $x \notin B$, $x \in B\setminus A$, so $x \in A \Delta B$, and therefore $x \in \emptyset$. But this last statement is clearly a contradiction, so we can conclude that $x \in B$. Since x was an arbitrary element of $A$, $A \subseteq B$. A similar argument shows that $B \subseteq A$. Then since $A \subseteq B$ and $B \subseteq A$, $A = B$.

($\leftarrow$) Suppose $A = B$. Suppose $A \Delta B \neq \emptyset$. Then we can choose some $x$ such that either $x \in A\setminus B$ or $x \in B\setminus A$. We consider these cases separately.
Case 1. $x \in A \setminus B$. Then since $A = B$, $x \in A \setminus A$, so $x \in A$ and $x \notin A$, which is a contradiction.
Case 2. $x \in B \setminus A$. Similarly, this leads to a contradiction.
Thus we can conclude that $A \Delta B = \emptyset$.

b) ($\rightarrow$) Suppose $A \Delta B = A \cup B$. Suppose $A \cap B \neq \emptyset$. Then we can choose some $x$ such that $x \in A \cap B$. This means that $x \in A$ and $x \in B$. Since $x \in A$, it follows that $x \in A \cup B$. But then since $A \Delta B = A \cup B$, $x \in A \Delta B$, so $x \in A \cup B$ and $x \notin A \cap B$. This contradicts the fact that $x \in A \cap B$. Therefore $A \cap B = \emptyset$.

($\leftarrow$) Suppose $A \cap B = \emptyset$. Let $x$ be an arbitrary element of $A \Delta B$. Then $x \in (A \cup B) \setminus (A \cap B)$. This means that $x \in A \cup B$ and $x \notin A \cap B$, so in particular $x \in A \cup B$. Since $x$ was an arbitrary element of $A \Delta B$, $A \Delta B \subseteq A \cup B$.
Now let $x$ be an arbitrary element of $A \cup B$. Then either $x \in A$ or $x \in B$.
Case 1. $x \in A$. Since $A \cap B = \emptyset$, $x \notin B$. Since $x \in A$ and $x \notin B$, $x \in A \setminus B$, so $x \in A \Delta B$.
Case 2. $x \in B$. A similar argument shows that $x \in A \Delta B$.
Since x was an arbitrary element of $A \cup B$, $A \cup B \subseteq A \Delta B$. But then since $A \Delta B \subseteq A \cup B$ and $A \cup B \subseteq A \Delta B$, we can conclude that $A \Delta B = A \cup B$.

-

Let $X$ be a set. Let $F_2 = \mathbb{Z}/2\mathbb{Z} = \{0, 1\}$ be the field consisting of $2$ elements. Let $F_2^X$ be the set of maps $X \rightarrow F_2$. $F_2^X$ is a ring with pointwise addition and multiplication. Let $A$ be a subset of $X$. Let $\chi_A$ be the characteristic function of $A$. We regard $\chi_A$ as an element of $F_2^X$.

Now let $A, B$ be subsets of $X$. Clearly $\chi_{A\Delta B} = \chi_A + \chi_B$.

Suppose $A\Delta B = \emptyset$. Then $0 = \chi_A + \chi_B$. Hence $\chi_A = -\chi_B = \chi_B$. Hence $A = B$.

Conversely suppose $A = B$. Then $\chi_A = \chi_B$. Hence $\chi_{A\Delta B} = \chi_A + \chi_B = 0$. Hence $A\Delta B = \emptyset$.

-

For a) $\Rightarrow)$ and since you want use the contrapositive argument you must prove that if $A\neq B$ then $A\Delta B\neq \emptyset$, so suppose that $A\neq B$ then there's $x\in A$ and $x\not\in B$ or there's $x\in B$ and $x\not\in A$ so $A\setminus B\ne\emptyset$ or $B\setminus A\ne\emptyset$ and then $A\Delta B=(A\setminus B)\cup (B\setminus A)\ne\emptyset$.

For b) if $A\Delta B=A\cup B$ then $(A\cup B)\setminus (A\cap B)=(A\cup B)$ so $(A\cap B)\subset(A\cup B)^c$ and since clearly $(A\cap B)\subset(A\cup B)$ then $$(A\cap B)\subset(A\cup B)\cap(A\cup B)^c=\emptyset$$

-

Here is an alternative, calculational proof which does not have two separate directions, using the fact (an alternative definition, actually) that for all $\;x\;$, $$x \in A \Delta B \equiv x \in A \not\equiv x \in B$$ Now we try to simplify $\;A \Delta B = \emptyset\;$: \begin{align} & A \Delta B = \emptyset \\ \equiv & \;\;\;\;\;\text{"basic property of $\;\emptyset\;$: it contains no elements"} \\ & \langle \forall x :: \lnot(x \in A \Delta B) \rangle \\ \equiv & \;\;\;\;\;\text{"the above definition of $\;\Delta\;$"} \\ & \langle \forall x :: \lnot(x \in A \not\equiv x \in B) \rangle \\ \equiv & \;\;\;\;\;\text{"logic"} \\ & \langle \forall x :: x \in A \equiv x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;=\;$ on sets, i.e., set extensionality"} \\ & A = B \\ \end{align} If you want to use the definition $\;A \Delta B = (A \setminus B) \cup (B \setminus A)\;$, then you can use a similar approach, using \begin{array}\\ x \in A \setminus B & \equiv & x \in A \land \lnot(x \in B) \\ x \in A \cup B & \equiv & x \in A \lor x \in B \\ \end{array} This makes the calculation slightly longer, of course. Hint: use DeMorgan, and the fact that $\;\lnot P \lor Q\;$ is the same as $\;P \Rightarrow Q \;$.

-