1
$\begingroup$

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?

3 Answers 3

2

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

  • 0
    Thanks for the input. I appreciate your guidance.2012-10-05
2

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

  • 0
    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$.2012-10-05
0

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.