6
$\begingroup$

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!

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

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.

$\endgroup$
  • $\begingroup$ Nice job, Nice performance. $\endgroup$ – mrs Mar 28 '13 at 3:40
  • $\begingroup$ 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! $\endgroup$ – stochasm Mar 28 '13 at 3:43
  • $\begingroup$ You're welcome, stochasm. $\endgroup$ – Namaste Mar 28 '13 at 3:47
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Proof by contradiction

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

hence $x\in A∆B $

hence $x\in A$

which is contradiction

hence $x\in A$

$\endgroup$
  • 1
    $\begingroup$ You just repeated what the OP wrote. The OP is not asking for a proof, but whether his/her proof is fine. $\endgroup$ – Pedro Tamaroff Mar 28 '13 at 4:02
0
$\begingroup$

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 also $B \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".

$\endgroup$

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.