1. ## Symmetric Difference

Prove $\displaystyle A \triangle B = A \triangle C \Rightarrow B = C$

This is so obvious by inspection:

$\displaystyle 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?

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

This is so obvious by inspection:

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

But how do you prove this?
Let $\displaystyle x\in B$. If $\displaystyle x\in A$ then $\displaystyle x\notin A\Delta B=A\Delta C$ and since $\displaystyle x\in A$ it follows that $\displaystyle x\notin A\Delta C\implies x\in C$. If $\displaystyle x\notin A$ then $\displaystyle x\in B-A\subseteq A\Delta B=A\Delta C$ and thus $\displaystyle x\in A\Delta C$. But, since $\displaystyle x\notin A$ it follows that $\displaystyle x\in C-A\implies x\in C$

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

4. This a second way. Suppose that $\displaystyle B\not\subset C$.
Then $\displaystyle \left( {\exists t \in B\backslash C} \right)$ now either $\displaystyle t\notin A$ or $\displaystyle t\in A$.

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

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

So $\displaystyle B\subseteq C$.

Likewise we prove that $\displaystyle C\subseteq B$ so $\displaystyle B=C$.

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

6. Yours is so elegant.

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

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

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

The scratch work for part 1 and 2 were long. They entire roll of toilet paper.

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

8. Originally Posted by novice
$\displaystyle x \in (B \wedge A\triangle B = A \triangle C)$. Prove $\displaystyle x\in C$, so $\displaystyle B\subseteq C$
Maybe what you mean is:

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

Originally Posted by novice
Suppose $\displaystyle x \in (C \wedge A\triangle B = A \triangle C)$. Prove $\displaystyle x\in B$, so $\displaystyle C \subseteq B$
Maybe what you mean is:

Suppose A$\displaystyle \triangle$B = A$\displaystyle \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$\displaystyle \triangle$B = A$\displaystyle \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$\displaystyle \triangle$B.
So x not in A$\displaystyle \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$\displaystyle \triangle$C. So x in C.
Suppose x not in A.
So x in A$\displaystyle \triangle$B.
So x in A$\displaystyle \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.

9. To emakarov:

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

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

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

( $\displaystyle \chi$ is characteristic function)

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