Results 1 to 4 of 4

Math Help - Symmetric difference is associative?

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    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? 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 a \in (A \oplus (B \oplus C)) \ ((A \oplus B) \oplus C). I.e. assume that there is an element a in (A \oplus (B \oplus C)) that is not in ((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 ((A \oplus B) \oplus C). Which is a contradiction -- a cannot be in (A \oplus (B \oplus C)) without also being in ((A \oplus B) \oplus C).

    But how can I give a proof for this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Plato View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetric difference
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 7th 2010, 03:36 PM
  2. Proof for Associative Law for Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 7th 2009, 02:21 AM
  3. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2009, 04:51 PM
  4. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 5th 2009, 01:09 PM
  5. symmetric difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 27th 2009, 10:15 AM

Search Tags


/mathhelpforum @mathhelpforum