# For all sets $A, B, C$, If $A \Delta B = A \Delta C$, then $B \subseteq C$

I get the general reason as to why this is True. I'm just having trouble trying to formulate this into a logically correct proof. My approach was:

(1) Assume $A \Delta B = A\Delta C$

(2) Let $x$ be an interger such that $x \subseteq A \Delta B$ and $x \subseteq A \Delta C$,

then

$x \subseteq A \cup B$ and $x \subseteq A \cup C$

(3) Seperate into cases, where either $x \subseteq A$, or $x \not\subset A$

And this is where I get stuck. I'm not sure if separating into cases is the right approach. Im stuck on linking $A \Delta B = A\Delta C$ with the fact that if they have the same elements after taking the symmetric difference, all the elements of B must also be in C.

• I suppose that $\Delta$ means symmetric difference here, and that somehow you are not allowed to do any algebra to obtain the result? (Because with algebra it is a one-liner.) Also, something is wrong with a formula $x\subseteq\cdots$ when $x$ is an integer. Did you mean $x\in\cdots$ instead? – Marc van Leeuwen May 20 at 13:57

It's easier to prove the contrapositive instead:

If $B \not\subseteq C$, then $A \Delta B \neq A \Delta C$.

To this end, suppose that there exists some $x \in C$ such that $x \notin B$. Then there are two cases to consider:

• Case 1: Suppose that $x \in A$. Then $x \in A \Delta B$ but $x \notin A \Delta C$
• Case 2: Suppose that $x \notin A$. Then $x \in A \Delta C$ but $x \notin A \Delta B$.

In either case, we conclude that $A \Delta B \neq A \Delta C$, as desired. $~~\blacksquare$

• This was much easier to wrap my head around. Thank you. – DavidM Feb 16 '18 at 7:31

Another possibility is to show that $A\triangle(A\triangle B)=B$. Then obviously we have $$A\triangle B = A\triangle C \implies B = A\triangle(A\triangle B) = A\triangle(A\triangle C) = C$$ And of course $B=C \implies B\subseteq C$.

If you have already proved that the symmetric difference is associative, then the proof of the first relation is a one-liner: $$A\triangle(A\triangle B) = (A\triangle A)\triangle B = \emptyset\triangle B=B$$

Below, a direct proof in natural deduction style ( incomplete though, since I have omitted to indicate the rules I used).

The stategy is as follows (1) assuming as hypothesis the equality of A Delta B and of A Delta C (2) assuming x belongs to B (3) using v-elim to derive that x belongs to C.

• Here, I use the following definition of X Δ Y :

x ∈ X Δ Y iff [ (x ∈ X v x ∈ Y) & ~ (x ∈ X & x ∈ Y) ]

• I use at some places v-Intro and DeMorgan’s rule to go from ~P to ~ ( P&Q) 