# Prove that if $A \mathop \triangle B \subseteq A$ then $B\subseteq A$

I'm having trouble with the logic in this proof and was wondering if anyone could point me in the right direction (if I'm wrong)?

Prove that if $A\mathop\triangle B\subseteq A$ then $B\subseteq A$. (Here $\triangle$ refers to the symmetric difference).

I started by using the definition of symmetric difference that $A\mathop\triangle B = (A\setminus B)\mathop\cup \mathop(B\setminus A)$. So $A\mathop\triangle B\subseteq A$ = $\forall\psi[(\psi\in A \wedge \psi \notin B) \vee (\psi \in B \wedge \psi \notin A) \rightarrow \psi \in A$].

Here is what I have for my proof:

Suppose $x \in B$. Suppose $x \notin A.$ Then since $x \in B$ and $A\mathop\triangle B\subseteq A$, it follows that $x \in A$. But this contradicts the fact that $x \notin A$, so we can conclude that $x \in A$. Since $x$ was an arbitrary element of $B$, it follows that $B\subseteq A$.

What I'm wondering is, is it enough to use universal instantiation on $x$ from the statement $\forall\psi[(\psi\in A \wedge \psi \notin B) \vee (\psi \in B \wedge \psi \notin A) \rightarrow \psi \in A$] given that $x \in B$ and $x \notin A$ to get my contradiction? Also, should I be giving more information about the logic used in the proof, or is it ok to leave it to the reader? Thanks for the help!

• Your proof is fine just as it is. – Brian M. Scott Mar 28 '13 at 3:30
• Using $\phi$ as set element is a little misleading, since the symbol is much like the empty set. – Jean-Claude Arbaut Mar 28 '13 at 4:05
• That's a good point arbautjc, I'll avoid that in the future. I've changed them to $\psi$. – stochasm Mar 28 '13 at 4:14

Your proof is fine: you need only show the inclusion you've shown. You chose (any) arbitrary $x$ such that $x \in B, x\notin A$, and you've reached a contradiction through your assumption that $x \in B \land x\notin A$. This implies (by definition, and perhaps you want to make this explicit) that $x \in A\triangle B$. But then since $A\triangle B \subseteq A, x\in A$. This is a contradiction which is realized whatever the $x$ satisfying the initial assumption is chosen. So the proof already shows that for any (all) $x$ such that $x \in B \land x\notin A \rightarrow x\in A \triangle B$, and since $A\triangle B \subseteq A,\;$ then $\; x\in A$.

Universal instantiation would be redundant.

• Nice job, Nice performance. – mrs Mar 28 '13 at 3:40
• Ahhh, of course, that makes a lot of sense. I'm self studying this stuff so I don't have an instructor to point me in the right direction, so I wanted to be sure...Thanks for the answer! – stochasm Mar 28 '13 at 3:43
• You're welcome, stochasm. – Namaste Mar 28 '13 at 3:47

Without contradiction, just in case, now that your proof has been checked: $$B\subseteq A\cup B=A\cup (A\Delta B)\subseteq A\cup A= A$$

let $x\in B$ but $x\notin A$

hence $x\in A∆B$

hence $x\in A$

hence $x\in A$
Throwing in my 0.02, I'd simply calculate \begin{align*} & A \Delta B \subseteq A \\ \equiv & \;\;\;\;\;\text{"expand definition of \;\subseteq\;"} \\ & \langle \forall x : x \in A \Delta B : x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"expand definition of \;\Delta\;"} \\ & \langle \forall x : x \in A \not\equiv x \in B : x \in A \rangle \\ (*) \;\; \equiv & \;\;\;\;\;\text{"logic: use negation of consequent in antecedent of (implicit) \;\Rightarrow\;"} \\ & \langle \forall x : \textrm{false} \not\equiv x \in B : x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify range"} \\ & \langle \forall x : x \in B : x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"definition of \;\subseteq\;"} \\ & B \subseteq A \\ \end{align*} and discover that alsoB \subseteq A \;\Rightarrow\; A \Delta B \subseteq A$holds. I don't remember the name for the rule used in the key step$(*)\$, but at least in proofs from Edsger W. Dijkstra c.s. it is fairly often used as a well-known law. It might be in Gries's "A Logical Approach to Discrete Math".