# Symmetric Difference

• Nov 1st 2010, 01:45 PM
novice
Symmetric Difference
Prove $A \triangle B = A \triangle C \Rightarrow B = C$

This is so obvious by inspection:

$A \triangle B = (A\backslash B) \cup (B\backslash A)= (A \backslash C) \cup (C \backslash A)=A \triangle C$

But how do you prove this?
• Nov 1st 2010, 02:57 PM
Drexel28
Quote:

Originally Posted by novice
Prove $A \triangle B = A \triangle C \Rightarrow B = C$

This is so obvious by inspection:

$A \triangle B = (A\backslash B) \cup (B\backslash A)= (A \backslash C) \cup (C \backslash A)=A \triangle C$
Suppose that $B\ne C$ then we may assume WLOG that $B\not\subseteq C$ so that there is some $b\in B-C$

But how do you prove this?

Let $x\in B$. If $x\in A$ then $x\notin A\Delta B=A\Delta C$ and since $x\in A$ it follows that $x\notin A\Delta C\implies x\in C$. If $x\notin A$ then $x\in B-A\subseteq A\Delta B=A\Delta C$ and thus $x\in A\Delta C$. But, since $x\notin A$ it follows that $x\in C-A\implies x\in C$
• Nov 1st 2010, 03:34 PM
emakarov
Another way is to note that $B = (A\vartriangle B)\vartriangle A$, and similarly for $C$. This in turn can be proved by showing that $x\in (A\vartriangle B) = (x\in A)\oplus (x\in B)$ where $x\in X=1$ or $0$ depending on whether $x$ is in $X$ and $\oplus$ is exclusive or. A similar method for proving associativity of $\vartriangle$ is described in this post. If one starts with knowing that $\vartriangle$ is associative and commutative then $B = (A\vartriangle B)\vartriangle A$ is obvious.
• Nov 1st 2010, 03:46 PM
Plato
This a second way. Suppose that $B\not\subset C$.
Then $\left( {\exists t \in B\backslash C} \right)$ now either $t\notin A$ or $t\in A$.

If $t\notin A$ then because $t\in B$ then $t\in A\Delta B= A\Delta C$ .
But that means $t\in C$ which is contradiction.

If $t\in A$ because $t\notin C$ we have $t\in A\Delta C= A\Delta B$.
But that means that $t\notin B$ which is a contradiction.

So $B\subseteq C$.

Likewise we prove that $C\subseteq B$ so $B=C$.
• Nov 2nd 2010, 08:15 AM
novice
Quote:

Originally Posted by emakarov
Another way is to note that $B = (A\vartriangle B)\vartriangle A$, and similarly for $C$. This in turn can be proved by showing that $x\in (A\vartriangle B) = (x\in A)\oplus (x\in B)$ where $x\in X=1$ or $0$ depending on whether $x$ is in $X$ and $\oplus$ is exclusive or. A similar method for proving associativity of $\vartriangle$ is described in this post. If one starts with knowing that $\vartriangle$ is associative and commutative then $B = (A\vartriangle B)\vartriangle A$ is obvious.

Wow, this looks like Set Theory for graduate students. Which book covers this. What prep work do I need to learn this?
• Nov 2nd 2010, 08:30 AM
novice
Yours is so elegant.

Mine looks naive:
Part 1. Suppose $x \in (B \wedge A\triangle B = A \triangle C)$. Prove $x\in C$, so $B\subseteq C$

Part 2. Suppose $x \in (C \wedge A\triangle B = A \triangle C)$. Prove $x\in B$, so $C \subseteq B$

$(B\subseteq C) \wedge (C \subseteq B)$. Thus $B=C$

The scratch work for part 1 and 2 were long. They entire roll of toilet paper.
• Nov 2nd 2010, 12:15 PM
MoeBlee
Quote:

Originally Posted by novice
Which book covers this. What prep work do I need to learn this?

Excellent for getting a real solid grasp of mathematical proof for such subjects as set theory is 'Logic: Techniques Of Formal Reasoning' by Kalish, Montague, and Mar. Then, with that background, I'd get 'Elements Of Set Theory' by Enderton and, perhaps as a supplement to Enderton, also 'Axiomatic Set Theory' by Suppes.
• Nov 2nd 2010, 12:36 PM
MoeBlee
Quote:

Originally Posted by novice
$x \in (B \wedge A\triangle B = A \triangle C)$. Prove $x\in C$, so $B\subseteq C$

Maybe what you mean is:

Suppose A $\triangle$B = A $\triangle$C & x in B. Show x in C.

Quote:

Originally Posted by novice
Suppose $x \in (C \wedge A\triangle B = A \triangle C)$. Prove $x\in B$, so $C \subseteq B$

Maybe what you mean is:

Suppose A $\triangle$B = A $\triangle$C & x in C. Show x in B.

/

You don't have to get confused by the symbols. It's pretty simple:

Suppose A $\triangle$B = A $\triangle$C. Show B=C.
Suppose x in B.
Either x in A or x not in A.
Suppose x in A.
So x not in A $\triangle$B.
So x not in A $\triangle$C.
So, since x in A, if x were not in C then x would be in A\C so x would be in A $\triangle$C. So x in C.
Suppose x not in A.
So x in A $\triangle$B.
So x in A $\triangle$C.
So, since x not in A, we have x not in A\C, so x in C\A, so x in C.
So, whether x in A or x not in A, we have x in C.
So x in B implies x in C.
So B is a subset of C.

Then prove C is a subset of B in a similar manner.
• Nov 3rd 2010, 08:18 AM
Also sprach Zarathustra
To emakarov:

In your post #6 from oct 2009 you should also prove the following:

If $\mho \neq \O$, $\boldsymbol{F}(\mho )$ is a group of all functions from $\mho$ to $\left \{ 0,1 \right \}$, and $\boldsymbol{P}(\mho )$ is power group of $\mho$. Now if we define the transformation: $\varphi : \boldsymbol{P}(\mho )\rightarrow \boldsymbol{F}(\mho )$ such that for all $A$ in $\boldsymbol{P}(\mho )$, $\varphi (A)=\chi _A$.

So we need to prove that $\varphi$ is a injective transformation.

( $\chi$ is characteristic function)
• Nov 3rd 2010, 09:49 AM
MoeBlee
If I'm not mistaken, the proofs given so far (except I didn't work through emakarov's version), including mine, use non-intuitionistic logic. My hunch is that that is unavoidable.