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


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

  • $\begingroup$ 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? $\endgroup$ – 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$

  • $\begingroup$ This was much easier to wrap my head around. Thank you. $\endgroup$ – 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)

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.