Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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}$. –  Jonas Meyer Dec 4 '12 at 5:23
    
Woops, actually it was an error while translating from paper. Thanks! Fixing now... –  Omega Dec 4 '12 at 5:26
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.