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.

  • 1
    $\begingroup$ Following "The statement can be rewritten..." are errors. The complement of the union is not the union of the complements. See DeMorgan's laws. The complement of the difference is not the difference of the complements. It might help to note that this is equivalent to $A\triangle B\subseteq \overline{A\cap B}$. $\endgroup$ – Jonas Meyer Dec 4 '12 at 5:23
  • $\begingroup$ Woops, actually it was an error while translating from paper. Thanks! Fixing now... $\endgroup$ – Zol Tun Kul Dec 4 '12 at 5:26

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


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.