Results 1 to 3 of 3

Math Help - Proof of the Associative Law of Symetric Difference

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    oxford,ms
    Posts
    3

    Proof of the Associative Law of Symetric Difference

    Hi there,
    I have to prove using Element Chasing that (A delta B) delta C = A delta ( B delta C)
    I have the Venn drawn, and was told to start with:
    let x be an element of (A delta B) delta C
    if x is an element of (A delta B) union(and) C but not in x element (A delta B) intersection(or) C


    I am not just sure really where to go next in the proof.
    The help would be ever so appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Proof of the Associative Law of Symetric Difference

    Note the following.

    For all sets X and Y, x belongs to X ∆ Y iff x belongs to precisely one of X and Y; correspondingly, x does not belong to X ∆ Y iff x belongs to either both X and Y or none of them. (*)

    There are 2 = 8 cases for whether x belongs to each of A, B and C. You can decide to be patient and go through all of them checking for each case whether x belongs to either side of the equality using (*).

    Another way is to prove first that x belongs to (A ∆ B) ∆ C iff x belongs to an odd number of sets (either one or three). For any set X, define in(x, X) = 1 if x ∈ X and in(x, X) = 0 if x ∉ X. Then we want to prove the following.

    For all sets A, B and C, x ∈ (A ∆ B) ∆ C iff in(x, A) + in(x, B) + in(x, C) is odd. (**)

    Note that (*) says the same thing, but about two instead of three sets. To show (**), note that x ∈ (A ∆ B) ∆ C iff either (1) x ∈ A ∆ B and x ∉ C or (2) x ∉ A ∆ B and x ∈ C. In (1), in(x, A) + in(x, B) is odd and in(x, C) = 0, so in(x, A) + in(x, B) + in(x, C) is odd. In (2), in(x, A) + in(x, B) is even and in(x, C) = 1, so again in(x, A) + in(x, B) + in(x, C) is odd. (Note that this proof of (**) can be used in a proof by induction of the generalization of (**) for n sets.)

    Now, given specific sets A', B', C', we can instantiate A = B', B = C' and C = A' in (**) to get

    x ∈ (B' ∆ C') ∆ A' iff in(x, B') + in(x, C') + in(x, A') is odd. (***)

    But (B' ∆ C') ∆ A' = A' ∆ (B' ∆ C'), so (***) gives

    x ∈ A' ∆ (B' ∆ C') iff in(x, A') + in(x, B') + in(x, C') is odd, (****)

    which together with (**) proves associativity. Alternatively, (****) can be shown similarly to (**).

    See also this thread.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Proof of the Associative Law of Symetric Difference

    Could do this "directly" via intersection/union/complement manipulations using A \Delta B = (A \cup B ) \cap ( \ (A \cap B)^c \ ), but I assume that's not "element chasing".

    The general technique of showing that two sets are equal is to show that each is a subset of the other. Thus it's a two part process, one for each direct of subset inclusion. For this problem, it's largely a book-keeping problem of being systematic. Here's how it might be done:

    Part 1: Show (A \Delta B) \Delta C \subset A \Delta (B \Delta C)
    Let x \in (A \Delta B) \Delta C.

    Then either x \in (A \Delta B), x\notin C, or x \in C, x \notin (A \Delta B). Thus the possiblities split into:
    Part 1, Case 1: x \in (A \Delta B) and x \notin C.
    Part 1, Case 2: x \in C and x \notin (A \Delta B).
    For Part 1, Case 1: x \in (A \Delta B) and x \notin C, so:
    Since x \in (A \Delta B), either x \in A and x \notin B, or x \in B and x \notin A.
    Part 1, Case 1.1: x \in A, x \notin B, x \notin C
    Part 1, Case 1.2: x \notin A, x \in B, x \notin C
    For Part 1, Case 2: x \in C and x \notin (A \Delta B), so:
    Since x \notin (A \Delta B), either x \notin A \cup B or x \in A \cap B. Thus this splits into 2 cases:
    Part 1, Case 2.1: x \in A, x \in B, x \in C
    Part 1, Case 2.2: x \notin A, x \notin B, x \in C.

    Have show that x \in (A \Delta B) \Delta C implies:
    x \in A, x \notin B, x \notin C (Part 1, Case 1.1)
    OR x \notin A, x \in B, x \notin C (Part 1, Case 1.2)
    OR x \in A, x \in B, x \in C (Part 1, Case 2.1)
    OR x \notin A, x \notin B, x \in C (Part 1, Case 2.2).

    Now that Part 1 is broken up into its components, must show that, in each of those case, x \in A \Delta (B \Delta C).
    (There another way to do this problem. There's a trick that could be used here: show that examining Part 2, where x \in A \Delta (B \Delta C), also breaks down into those 4 same cases. If you could do that, you'd be done. However, I'll proceed doing it the "direct" way.)

    If x \in A, x \notin B, x \notin C (Part 1, Case 1.1), then x \notin B \Delta C, and x \in A. Therefore x \in A \Delta (B \Delta C).

    If x \notin A, x \in B, x \notin C (Part 1, Case 1.2), then x \in B \Delta C, and x \notin A. Therefore x \in A \Delta (B \Delta C).

    If x \in A, x \in B, x \in C (Part 1, Case 2.1), then x \notin B \Delta C, and x \in A. Therefore x \in A \Delta (B \Delta C).

    If x \notin A, x \notin B, x \in C (Part 1, Case 2.2), then x \in B \Delta C, and x \notin A. Therefore x \in A \Delta (B \Delta C).

    Therefore, have proven Part 1: x \in (A \Delta B) \Delta C \Rightarrow x \in A \Delta (B \Delta C), so have proven that (A \Delta B) \Delta C \subset A \Delta (B \Delta C).

    Now do the exact same procedure for Part 2, which will examine, and then prove, that A \Delta (B \Delta C) \subset (A \Delta B) \Delta C. The rest would look like:

    Part 2: Show A \Delta (B \Delta C) \subset (A \Delta B) \Delta C
    Let x \in A \Delta (B \Delta C).
    Then... blah... blah... blah...
    ...
    Therefore have proven Part 2: x \in A \Delta (B \Delta C) \Rightarrow x \in (A \Delta B) \Delta C, so have proven that A \Delta (B \Delta C) \subset (A \Delta B) \Delta C.
    Therefore, Part 1 and Part 2 together have proven that A \Delta (B \Delta C) = (A \Delta B) \Delta C.
    QED
    Last edited by johnsomeone; September 12th 2012 at 07:10 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 6th 2012, 12:01 AM
  2. Symmetric difference is associative?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 5th 2011, 03:43 AM
  3. Replies: 2
    Last Post: July 29th 2010, 05:31 AM
  4. Proof for Associative Law for Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 7th 2009, 02:21 AM
  5. symetric difference
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 19th 2007, 09:34 PM

Search Tags


/mathhelpforum @mathhelpforum