# $A \oplus B = A \oplus C$ imply $B = C$?

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving problems with them or proving equalities I have no idea how to use $\oplus$.

For example: I'm trying to do a problem in which I have to prove or disprove with a counterexample whether or not $A \oplus B = A \oplus C$ implies $B = C$ is true.

I know that the venn diagram of $\oplus$ in this case includes the regions of A and B excluding the areas they overlap. And similarly it includes regions of A and C but not the areas they overlap. It would look something like this: I feel the statement above would be true just by looking at the venn diagram since the area ABC is included in the $\oplus$, but I'm not sure if that's an adequate enough proof. On the other hand, I could be completely wrong about my reasoning.

Also just for clarity's sake: Would $A\cup B = A \cup C$ and $A \cap B = A \cap C$ be proven in a similar way to show whether or not the conditions imply $B = C$? A counterexample/ proof of this would be appreciated as well.

• For still more fun show that the power set of a set $X$, together with the xor operation, is a group. And, of course, groups have the cancellation law you ask about. – GEdgar Oct 23 '13 at 17:41
• The xor being, in that case, called the symmetric difference. @user101279 : By the way, $\oplus$ is addition modulo $2$. – xavierm02 Oct 23 '13 at 18:04
• Remark also that xor is the addition operation when we regard a Boolean algebra as essentially the same as a Boolean ring. – user43208 Oct 23 '13 at 18:05
• Think of $\oplus$ as $\neq$. – copper.hat Oct 23 '13 at 18:06
• If we omit the question about intersection and union in the last paragraph, this is the same as math.stackexchange.com/questions/294460/… – Martin Sleziak Aug 30 '14 at 15:30

## 5 Answers

Think of $\oplus$ as $\neq$. That is $A \oplus B$ iff $A \neq B$.

Note that $A \oplus A$ is always false, and $\text{False}\oplus A = A$.

Then $A \oplus (A \oplus B) = (A \oplus A) \oplus B = \text{False} \oplus B = B$.

Similarly, $A \oplus (A \oplus C) = C$, hence $B=C$.

Aside: A 'cute' (as in amusing but not of any practical significance) use of $\oplus$ is to swap the values of two bit variables in a programming language without using an intermediate variable: \begin{eqnarray} x = y \oplus x \\ y = y \oplus x \\ x = y \oplus x \\ \end{eqnarray} Show that the values of $x,y$ are swapped!

Hint: $A\oplus(A\oplus B)=(A\oplus A)\oplus B = B$.

And of course $A\cup B=A\cup C$ does not imply $B=C$ (consider the case $B=A\ne \emptyset = C$). And $A\cap B=A\cap C$ does not imply $B=C$ either (consider the case $A=\emptyset$)

Hint: $\oplus$ is associative with unit $\emptyset$, and $A \oplus A = \emptyset$. Does this give you an idea for canceling?

This can be done using a simple calculation. But I don't know how to interpret your question, so I'll give two answers. :-)

I'm assuming $\;A,B,C\;$ are booleans. I will write $\;\not\equiv\;$ instead of $\;\oplus\;$, and $\;\equiv\;$ instead of $\;=\;$ on booleans.

First, note that $\;\equiv\;$ and $\;\not\equiv\;$ are not only both associative, but they are also mutually associative. Therefore no parentheses are needed in the following calculation.

We can now simplify $\;A \oplus B = A \oplus C\;$ as follows: \begin{align} & A \not\equiv B \equiv A \not\equiv C \\ \equiv & \;\;\;\;\;\text{"rearrange"} \\ & A \not\equiv A \equiv B \not\equiv C \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{false} \equiv B \not\equiv C \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & B \equiv C \\ \end{align}

If instead $\;A,B,C\;$ are sets, and your $\;\oplus\;$ is the symmetric difference of two sets (which is normally written as $\;\triangle\;$), then the proof is slightly longer, but with essentially the same structure.

The simplest definition of symmetric difference is $$x \in A \oplus B \equiv x \in A \not\equiv x \in B$$

We can expand the definitions and simplify using logic, as follows: \begin{align} & A \oplus B = A \oplus C \\ \equiv & \;\;\;\;\;\text{"set extensionality; definition of $\;\oplus\;$, twice"} \\ & \langle \forall x :: x \in A \not\equiv x \in B \equiv x \in A \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: rearrange"} \\ & \langle \forall x :: x \in A \not\equiv x \in A \equiv x \in B \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: \text{false} \equiv x \in B \not\equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: x \in B \equiv x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & B = C \\ \end{align}

In both cases, we have found a stronger conclusion than was asked: we proved equivalence of the two expressions.

You asked this additional question in the last paragraph:

Also just for clarity's sake: Would $A\cup B = A \cup C$ and $A \cap B = A \cap C$ be proven in a similar way to show whether or not the conditions imply $B = C$? A counterexample/ proof of this would be appreciated as well.

$A\cup B=A\cup C$ $\Rightarrow$ $B=C$ is not true in general.

Counterexample: Take any non-empty set $A$ and also take $B=A$ and $C=\emptyset$. Then $A\cup B=A\cup C=A$, but $B\ne C$.

$A\cap B=A\cap C$ $\Rightarrow$ $B=C$ is not true in general.

Take some element $x\notin A$ and put $B=A$, $C=A\cup\{x\}$. Then $A\cap B=A\cap C=A$, but $B\ne C$.