Results 1 to 11 of 11

Math Help - Symmetric difference

  1. #1
    Junior Member
    Joined
    Jul 2007
    Posts
    27

    Symmetric difference

    Show that this operation on sets is associative: for all sets: A,B,C one has (A @B)@C = A@(B@C)

    P.S. because I dont know how to type the "triangle" sign to the message, the "@" mean the "triangle" sign, the symmetric difference.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    So how do you prove it if you're in ZF set theory, and set complementation is not allowed?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Please post the first steps, then I'll help you if you get stuck.

    So what are the first steps? First, how do you ordinarily show that sets are equal? Second, upack the two sets by the definition of '@'.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Well, I'm doing Suppes' Axiomatic Set Theory. Problem 2.3.12 is the one I'm working on. It goes like this:

    We define the operation of symmetric difference by the identity:

    A\div B=(A\sim B)\cup(B\sim A).

    Prove:
    (A\div B)\div C=A\div(B\div C). (This is actually part (c) of a multi-step problem, but this is the step that has me stumped.)

    I've seen emakarov's solution on this forum, using the exclusive or function's associativity. That's nice, but I'm wondering if all that extra baggage of having to prove the relationship between the exclusive or and the symmetric difference is worth it. Then you've also introduced a whale of a lot of symbols that ZF set theory hasn't defined yet.

    If you write out the right and left sides of the identity, you get:

    (A\div B)\div C=(((A\sim B)\cup (B\sim A))\sim C)\cup(C\sim((A\sim B)\cup (B\sim A))), and

    A\div(B\div C)=(A\sim((B\sim C)\cup(C\sim B)))\cup(((B\sim C)\cup(C\sim B))\sim A).

    Now, you can show that A\sim(B\cup C)=(A\sim B)\cap(A\sim C), and that A\sim(B\cap C)=(A\sim B)\cup(A\sim C).

    Moreover, you can also show that (A\cup B)\sim C=(A\sim C)\cup(B\sim C), and (A\cap B)\sim C=(A\sim C)\cap(B\sim C). The last is technically part (d) of the problem; although I can prove it independently of part (c), it'd be great if I didn't have to use it.

    However, what I'm really looking for is a more elegant, less tedious way of showing this property. I mean, it's not even true that (((A\sim B)\cup (B\sim A))\sim C)=(A\sim((B\sim C)\cup(C\sim B))). So whatever method you use from here would have to straddle the union in the middle. Not nice at all.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Oh, and I should also point out that one thought I had as to strategy was to show that both sides equaled the following expression:

    ((A\sim B)\cap(A\sim C))\cup((B\sim A)\cap(B\sim C))\cup((C\sim A)\cap(C\sim B))\cup(A\cap B\cap C).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    There are many ways to prove this, and depending what has already been proven.

    But I'm not thinking of the most elegant or even less tedious approach. Rather, I'm thinking of the most obvious, straightforward approach - just the most obvious, basic, direct way to get the thing proven.

    That is,

    1. Assume x in A@(B@C) and show x in (A@B)@C.
    2. Asuume x in (A@B)@C and show x in A@(B@C).

    Assume 1:

    Either
    x in A and it is not the case that either ((x in B and x not in C) or (x in C and x not in B))

    or

    either ((x in B and x not in C) or (x in C and x not in B)) or x not in A.

    And you can keep breaking this down to a "table" of cases.

    Then show, by also "breaking down" (A@B)@C and taking the cases above, that x in (A@B)@C.

    Then do the converse (2.) in similar manner.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Yes, I am aware of the usual way to prove two sets are equal. The sentences you've written down are entirely equivalent to the ones I've written down. In doing it the usual way, I would think logical errors would be extremely easy to come by. Moreover, the result would barely be human-readable! This is why I'm not a fan of that approach for this problem. It's just a bit too unwieldy. I like the elegance of the exclusive or approach; if I could prove emakarov's lemma that makes the correspondence between set difference and exclusive or the bijection it needs to be, and with preferably as little extra baggage as possible, I think I'd probably go with that. Do you have any different ideas for the proof?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Do as you wish, but proving it in the "literal" way of just unpacking to a "table" of alternatives is not especially prone to logical error nor need it be unreadable. Indeed, it is utterly straightforward, airtight, convincing, and its formalization in first order logic would be routine. Personally, I wouldn't make such a big deal about this proof - looking for especially elegant ways to prove it (which ways themselves require some detour into lemmas, whatever) - but rather I'd just apply the definitions and directly prove it as suggested, then to move on in the book. (Indeed, in the time we've exchanged messages about this - about looking for a more elegant way - one could have as easily just typed out the rest of the proof I started).

    Later, of course, you'll see how this goes hand in hand with the sentential operator 'exclusive or' and the Boolean operation, etc. But for mere purposes of getting the thing proven at this point in Suppes text, I'd just go ahead and unpack the definitions and show x in one iff x in the other. But suit yourself...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Or, one could just as well write:

    Suppose x in A@(B@C).

    So

    either
    x in A and it is not the case that either ((x in B and x not in C) or (x in C and x not in B))

    or

    either ((x in B and x not in C) or (x in C and x not in B)) or x not in A.

    [Then in the same manner spell out the condition for x in (A@B)@C. Then write: "So x in (A@B)@C follows by routine sentential logic." Then do the converse. Then done.]
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Ackbeet View Post
    So how do you prove it if you're in ZF set theory, and set complementation is not allowed?
    Why the hell did you open a three year old thread? I should start doing that! Answer all the old posts that interst me!! >
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetric difference
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 25th 2011, 10:34 PM
  2. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 3rd 2010, 08:49 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