Results 1 to 10 of 10

Math Help - Proof for Associative Law for Symmetric Difference

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    123

    Proof for Associative Law for Symmetric Difference

    That is, prove that A delta (B delta C) = (A delta B) delta C.

    I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,602
    Thanks
    1421
    Quote Originally Posted by h2osprey View Post
    That is, prove that A delta (B delta C) = (A delta B) delta C.

    I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?
    As long as it is a valid proof, there is no reason why it shouldn't be acceptable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by h2osprey View Post
    That is, prove that A delta (B delta C) = (A delta B) delta C.

    I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?
    it would probably be good for you to post your proof...just how lengthy is it?
    Last edited by Jhevon; January 8th 2009 at 05:33 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Quote Originally Posted by h2osprey View Post
    That is, prove that A delta (B delta C) = (A delta B) delta C.
    Here is one way to prove it, it may be similar to your way, but here goes:

    By definition, we know that A \Delta B=(A \backslash B) \cup (B \backslash A). Therefore,

    (A \Delta B) \Delta C =

    =((A \Delta B)\backslash C) \cup (C \backslash (A \Delta B))=

    =((A \Delta B)\cap (C)^c) \cup (C \cap (A \Delta B)^c)=

    =[((A \backslash B) \cup (B \backslash A))\cap (C)^c]\cup[C \cap ((A \backslash B)\cup (B \backslash A))^c]=(*)

    Now we make a little digression to simplify ((A \backslash B)\cup (B \backslash A))^c from the above expression:
    ((A \backslash B)\cup (B \backslash A))^c=
    =((A \cap B^c) \cup (B \cap A^c))^c=
    =(A \cap B^c)^c \cap (B \cap A^c)^c=
    =(A^c \cup (B^c)^c) \cap (B^c \cup (A^c)^c)=
    =(A^c \cup B) \cap (B^c \cup A)=
    =(A^c\cap B^c) \cup (A^c\cap A) \cup (B \cap B^c) \cup (B \cap A)=
    =(A^c\cap B^c) \cup (A \cap B), and then plug this into the equation above;


    (*)=[((A \cap B^c) \cup (A^c \cap B))\cap C^c]\cup[C \cap ((A^c\cap B^c) \cup (A \cap B))]=

    =[(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)]\cup[(C \cap A^c \cap B^c) \cup (C \cap A \cap B))]=

    =(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)\cup (A^c \cap B^c  \cap C) \cup (A \cap B \cap C)

    Next, if you exchange sets in the original expression ( (A \Delta B) \Delta C) in the following way: A \leftrightarrow B; B \leftrightarrow C; C \leftrightarrow A, you'll get that

    (B \Delta C) \Delta A=...=(A \cap B^c \cap C^c) \cup (A^c \cap B \cap C^c)\cup (A^c \cap B^c  \cap C) \cup (A \cap B \cap C), and from this, it follows that

    (A \Delta B) \Delta C =(B \Delta C) \Delta A=(and, because the symmetric difference is a symmetric operation, i.e. X \Delta Y= Y \Delta X, it follows that)= A \Delta (B \Delta C).

    Therefore, (A \Delta B) \Delta C =A \Delta (B \Delta C)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    Posts
    123
    Quote Originally Posted by Jhevon View Post
    it would probably be good for you to post your proof...just how lengthy is it?
    I basically gave the proof above except I didn't show that both sides were equal to the derived one; I proved it all the way with iff's.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Here is a different way to prove this, or rather to reduce it to associativity of addition \oplus modulo 2. To remind, \oplus:\{0,1\}\times\{0,1\}\to\{0,1\}; x\oplus y=x+y if at least one of x,y is 0, and 1\oplus 1=0.

    Definition. For a set A and an object x, let in(x,A)=1 if x\in A and in(x,A)=0 otherwise.

    Lemma. For all sets A, B and any object x, in(x,A{\scriptstyle\triangle} B)=in(x,A)\oplus in(x,B).

    Theorem. For all sets A,B,C, A{\scriptstyle\triangle}(B{\scriptstyle\triangle}C  )=(A{\scriptstyle\triangle}B){\scriptstyle\triangl  e}C.

    Proof. For any x, in(x,A{\scriptstyle\triangle}(B{\scriptstyle\trian  gle}C))=in(x,A)\oplus(in(x,B)\oplus in(x,C)) = (in(x,A)\oplus in(x,B))\oplus in(x,C)=in(x,(A{\scriptstyle\triangle}B){\scriptst  yle\triangle}C).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2009
    Posts
    2
    Quote Originally Posted by h2osprey View Post
    That is, prove that A delta (B delta C) = (A delta B) delta C.

    I managed a lengthy proof but only with the use of De Morgan's Laws - just checking if this is acceptable?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2009
    Posts
    2
    hi math members my name is Paul Otuoma from Nairobi,Kenya. Am a student at the University of Nairobi.Am persuing Bachelor of Science, where am taking Double maths and Physics..Am glad to join this group its superb..Let me ask how comes (A delta B) is (A\B) U (B\A)?? our teacher taught us that, (A delta B)= ( A-B) U (B-A) ??? Please help..
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    You can prove it by using characteristic function, the prove would be simpler.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    Quote Originally Posted by pol02oma View Post
    maths and Physics..Am glad to join this group its superb..Let me ask how comes (A delta B) is (A\B) U (B\A)?? our teacher taught us that, (A delta B)= ( A-B) U (B-A) ???
    A-B and A\setminus B are two different notations for the same thing: set difference. In fact, it is a good idea for people to define less-standard concepts and notations when they ask questions because there are so many variations of the same concepts around the world. I am talking in general, not so much about this particular thread because both A-B and A\setminus B are pretty standard.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetric difference is associative?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 5th 2011, 03:43 AM
  2. Symmetric difference
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 25th 2011, 10:34 PM
  3. Symmetric Difference Proof
    Posted in the Discrete Math Forum
    Replies: 21
    Last Post: January 12th 2011, 03:59 PM
  4. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 3rd 2010, 08:49 AM
  5. Symmetric difference proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2010, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum