How to prove $A\cap B \subseteq \overline{A \triangle B}$ An exercise asks me to prove the following:
$$A\cap B \subseteq \overline{A \triangle B}$$
Unlike most other exercises, this one implies a symmetric difference, of which I am unfamiliar in this kind of proofs. There was little I could do, here:
The statement can be rewritten as the following:
$$A\cap B \subseteq \overline{(A-B)\cap (B-A)}$$
$$A\cap B \subseteq \overline{(A-B)}\cap \overline{(B-A)}$$
$$A\cap B \subseteq (\overline{A} - \overline{B}) \cap (\overline{B} - \overline{A})$$
I rewrote it because the symmetric difference doesn't seem "primitive" enough for me to operate with. Then my proof begins:
$$x \in A \cap B \implies x\in A \land x \in B$$
$$\implies x \in (A \cap B) \land x \in (B \cap A)$$
$$\implies (x \in A \land x \in B) \land (x \in B \land x \in A)$$
And then, I got stuck. I don't see how can $(x \in A \land x \in B) \land (x \in B \land x \in A)$ become what I needed at all.
 A: You’ve some serious errors in your first calculations: it is not true in general that $$\overline{(A\setminus B)\cap(B\setminus A)}=\overline{A\setminus B}\cap\overline{B\setminus A}$$ or that $$\overline{A\setminus B}\cap\overline{B\setminus A}=(\overline A\setminus\overline B)\cap(\overline B\setminus\overline A)\;.$$ In fact,
$$\overline{(A\setminus B)\cap(B\setminus A)}=\overline{A\setminus B}\cup\overline{B\setminus A}$$
by one of the de Morgan laws, and $\overline{A\setminus B}=\overline A\cup B$, also by de Morgan.
Here’s an approach that does work.
Suppose that $x\in A\cap B$; you want to show that $x$ is not in $A\triangle B$. Judging by the work in your question, your definition of $A\triangle B$ is $(A\setminus B)\cup(B\setminus A)$, so you want to show that
$$x\notin(A\setminus B)\cup(B\setminus A)\;.$$
To do this, you must show that $x\notin A\setminus B$ and $x\notin B\setminus A$. But that’s easy: if $x$ were in $A\setminus B$, then by definition we’d have $x\in A$, which is fine, and $x\notin B$, which is not fine: since $x\in A\cap B$, we know that $x$ is in $B$. Thus, $x$ cannot belong to $A\setminus B$: $x\notin A\setminus B$. A virtually identical argument shows that $x\notin B\setminus A$, and hence that $x\notin(A\setminus B)\cup(B\setminus A)$.
Another approach is to show that your definition of $A\triangle B$ is equivalent to another comment definition: $$A\triangle B=(A\cup B)\setminus(A\cap B)\;.$$ That makes it very obvious that nothing can belong both to $A\triangle B$ and $A\cap B$.
A: A straightforward calculational proof, which uses the following definition of $\triangle$: $$x \in A \triangle B \;\equiv\; x \in A \not\equiv x \in B$$ starts at the most complex side (here: the right hand side) of the statement in question, and goes like this:
$$
\begin{align}
& x \in \overline{A \triangle B} \\
\equiv & \;\;\;\;\;\text{"definition of $\overline{\phantom\square}$; the above definition of $\triangle$"} \\
& \lnot(x \in A \:\not\equiv\: x \in B) \\
\equiv & \;\;\;\;\;\text{"logic: simplify"} \\
& x \in A \:\equiv\: x \in B \\
\Leftarrow & \;\;\;\;\;\text{"logic: weakening -- suggested by the shape of the left hand side ($A \cap B$)"} \\
& x \in A \:\land\: x \in B \\
\equiv & \;\;\;\;\;\text{"definition of $\cap$"} \\
& x \in A \cap B \\
\end{align}
$$
By the definition of $\subseteq$ this proves the original statement.
