2

Prove that if $A \oplus B = A \oplus C$, then $B=C$

Note: $ A\oplus B= (A \cup B) \setminus (A \cap B)= (A \setminus B) \cup (B \setminus A)$

This is what I have done so far:

Claim: B=C

Proof: Case 1: show that $B \subseteq C$

Case 2: Show that $C \subseteq B$

Case 1: Let $x \in B$, either $x \in A$ or $x \notin A$.

If $x \in A$, then $x \in A \cup B$ $\Rightarrow x \in C \cup A $ (because $A \oplus B = B \oplus A$) Hence, $x \in C \setminus A \Rightarrow x\in C$.

If $x \notin A \Rightarrow x \in B\setminus A$. Hence, either $ x \in A \setminus C$ or $ x \in C \setminus A $. But, $ x \in C \setminus A$ since $ x \notin A$.

Is this thinking process correct? Any help is appreciated.

Lily
  • 395

3 Answers3

2

Assuming that (in addition to commutativity) you know the other symmetric difference properties:

  • $A \oplus \emptyset = A$

  • $A \oplus A = \emptyset$

  • $A \oplus (B \oplus C) = (A\oplus B)\oplus C$

the result follows directly from:

$$B = B \oplus \emptyset = B \oplus (A \oplus A) = (B \oplus A) \oplus A \;\;=\;\; (C \oplus A) \oplus A = C \oplus(A \oplus A)= C \oplus \emptyset = C$$

dxiv
  • 76,497
1

Because the statement is symmetric in $B$ and $C$. It is sufficient to show that $B \subseteq C$. The proof for $C \subseteq B$ would be a verbatim repetition with the obvious changes.

So let $x \in B$ and $x \in A$. Then $x \notin A \oplus B$ and hence $x \notin A \oplus C$ (because $A \oplus B = A \oplus C$) and hence $x \in C$ because if $x \notin C$, this would imply $x \in A \oplus C$.

Now let $x \in B$ and $x \notin A$. Then $x \in A \oplus B$ and hence $x \in A \oplus C$ and hence $x \in C$ by the same argument as above.

The problem with your argument is that $A \oplus B = A \oplus C$ does not immediatly imply $A \cup B \subseteq A \cup C$.

Martins Bruveris
  • 1,620
0

Not quite. The important thing to realize is that $A \oplus B$ is all the elements in $A$ but not in $B$, and vice verse. In other words, for any element $x \in A \oplus B$: $x \in A$ iff $ x \notin B$

So try this:

case 1:

Suppose $x \in B$.

$x \in A$ or $x \notin A$.

If $x \in A$, then $x \notin A \oplus B$ (since $x \in B$). Hence (since $A \oplus B = A \oplus C$) $ x \notin A \oplus C $. Hence (since $x \in A$) $ x\in C$.

If $x \notin A $ then $x \in A \oplus B$ (since $x \in B$). Hence (since $A \oplus B = A \oplus C$) $ x \in A \oplus C $. Hence (since $x \notin A$) $ x\in C$.

case 2 is of course completely symmetrical.

Bram28
  • 100,612
  • 6
  • 70
  • 118