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.

Ok I made an attempt to answer this question. I would like for someone to check it to see if I'm on the right track.

Suppose $A,B$ are sets and that $A\setminus B = A\oplus B$. Prove $B\subseteq A$. (btw, $\oplus$ represents symmetric difference).

Proof: Let $x$ be an element of $A$. Let $x$ also be an element of $B$. Therefore, $x$ is not an element of $A\setminus B$ and since $A\setminus B = A\oplus B$, $x$ is not an element of $A\oplus B$ either. Thus, $B$ is a subset of $A$.

I'm not sure if that is correct, but could someone double check it for me?

share|improve this question

3 Answers 3

up vote 2 down vote accepted

In order to show that $B\subseteq A$, you must start with an arbitrary element of $B$ and show that it’s in $A$; starting with an element of $B$ that is already in $A$ is assuming what you want to prove. Here’s a correct argument:

Suppose that $x\in B$. If $x\notin A$, then $x\in B\setminus A$. By definition of symmetric difference we know that $B\setminus A\subseteq A\oplus B$, so $x\in A\oplus B$. But by hypothesis $A\oplus B=A\setminus B$, so $x\in A$ and $x\notin B$. This contradiction shows that $x$ must be in $A$ and hence that $B\subseteq A$.

Added: Alternatively, you can try to prove the contrapositive: show that if $x\notin A$, then $x\notin B$. Suppose that $x\notin A$; then $x\notin A\setminus B$, and since $A\oplus B=A\setminus B$, $x\notin A\oplus B$. But this means that $x\notin B\setminus A$, since $B\setminus A\subseteq A\oplus B$, so either $x\notin B$, or $x\in A$. But we assumed that $x\notin A$, so it must be that $x\notin B$. We’ve now shown that if $x\notin A$, then $x\notin B$, which is logically equivalent to saying that if $x\in B$, then $x\in A$, i.e., that $B\subseteq A$.

share|improve this answer
    
Thanks for the input. I appreciate your guidance. –  blutuu Oct 5 '12 at 3:36

You don't want to assume that $x\in A$, only that $x\in B$. Then you must show that $x\in A$.

As an alternative, consider the following approach. By definition, for any sets $A,B$, we have $A\oplus B=(A\smallsetminus B)\cup(B\smallsetminus A)$. This is a disjoint union. (Why?) Hence, $A\oplus B=A\smallsetminus B$ if and only if $B\smallsetminus A=\emptyset$ if and only if $B\subseteq A$.

share|improve this answer
    
Thanks for your answer. Before I posted I had arrived at the idea that both A(+)B and A\B had to both be empty for B to be a subset of A. I guess I was sorta close. –  blutuu Oct 5 '12 at 3:39
    
Neither of them has to be empty. For example, let $A=\{1,2\}$ and $B=\{1\}$. Then $A\oplus B=A\smallsetminus B=\{2\}\neq\emptyset$. –  Cameron Buie Oct 5 '12 at 3:42

Here is an approach where we start at the most complex side ($\;A \setminus B = A \oplus B\;$), expand the definitions from set theory, and use predicate logic to simplify as much as possible.

\begin{align} & A \setminus B = A \oplus B \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & \langle \forall x :: x \in A \setminus B \;\equiv\; x \in A \oplus B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$; the simplest definition of $\;\oplus\;$"} \\ & \langle \forall x :: x \in A \land x \not\in B \;\equiv\; x \in A \not\equiv x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify by moving a negation into the rightmost part"} \\ & \langle \forall x :: x \in A \land x \not\in B \;\equiv\; x \in A \equiv x \not\in B \rangle \\ \equiv & \;\;\;\;\;\text{"logic: apply (what Dijkstra calls) the golden rule: $\;p \lor q \equiv p \land q \equiv p \equiv q\;$"} \\ & \langle \forall x :: x \in A \lor x \not\in B \rangle \\ \equiv & \;\;\;\;\;\text{"logic: $\;\lnot p \lor q\;$ is one of the ways to write $\;p \Rightarrow q\;$"} \\ & \langle \forall x :: x \in B \;\Rightarrow\; x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\subseteq\;$"} \\ & B \subseteq A \\ \end{align}

Note that this uses the fact that $\;\equiv\;$ and $\;\not\equiv\;$ are mutually associative, and $\;\equiv\;$ is associative.

This proves that actually both expressions are equivalent.

share|improve this answer

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.