1. Symmetric difference is associative?

Is the symmetric difference associative? I'd like to be able to give a proof for it.

I.e. is the following true? $\displaystyle A \oplus (B \oplus C) = (A \oplus B) \oplus C$, where A, B, and C are sets.

To me it seems this is the case, i.e. that the symmetric difference is associative.

Let $\displaystyle a \in (A \oplus (B \oplus C))$ \ $\displaystyle ((A \oplus B) \oplus C)$. I.e. assume that there is an element a in $\displaystyle (A \oplus (B \oplus C))$ that is not in $\displaystyle ((A \oplus B) \oplus C).$
This implies that a must be in only one of A, B or C for this to be true.
But if a is in either A, B or C, but not in two or more; then by definition of the symmetric difference, it must also be in $\displaystyle ((A \oplus B) \oplus C).$ Which is a contradiction -- a cannot be in $\displaystyle (A \oplus (B \oplus C))$ without also being in $\displaystyle ((A \oplus B) \oplus C).$

But how can I give a proof for this?

2. Having taught this for many, many years I still consider this the most difficult 'simple proofs' there is. Here is a web reference for you.
I have found that a proof using characteristic functions is the easiest to follow.

3. Originally Posted by Plato
Having taught this for many, many years I still consider this the most difficult 'simple proofs' there is. Here is a web reference for you.
I have found that a proof using characteristic functions is the easiest to follow.

This is one of the two instances I know of a group operation for which the hardest thing to prove, and

by far, is associativity, the other one being the Poincare´s group operation on an elliptic curve, yet

in this case is probably harder since this deals with a basic example both in set and group theory, whereas

the other one is more advanced stuff.

Tonio

4. Originally Posted by Plato
Having taught this for many, many years I still consider this the most difficult 'simple proofs' there is. Here is a web reference for you.
I have found that a proof using characteristic functions is the easiest to follow.
Emakarov posted the outline of a proof using characteristic functions and the boolean exclusive or. Once you've proven all the bijections necessary, it works very smoothly, and is, like Plato said, the easiest to follow that I've ever seen.

,

,

,

,

,

,

,

,

,

determine whether the symmetric difference is associative that is if a b and c are sets

Click on a term to search for related topics.