2
$\begingroup$

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.

  • 0
    Woops, actually it was an error while translating from paper. Thanks! Fixing now...2012-12-04

2 Answers 2

4

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

1

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.