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

Question

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.

Answer 1

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$

Answer 2

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

Answer 3

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)