Results 1 to 3 of 3

Thread: 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,577
    Thanks
    790

    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
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: Proof of the Associative Law of Symetric Difference

    Could do this "directly" via intersection/union/complement manipulations using $\displaystyle 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 $\displaystyle (A \Delta B) \Delta C \subset A \Delta (B \Delta C)$
    Let $\displaystyle x \in (A \Delta B) \Delta C$.

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

    Have show that $\displaystyle x \in (A \Delta B) \Delta C$ implies:
    $\displaystyle x \in A, x \notin B, x \notin C$ (Part 1, Case 1.1)
    OR $\displaystyle x \notin A, x \in B, x \notin C$ (Part 1, Case 1.2)
    OR $\displaystyle x \in A, x \in B, x \in C$ (Part 1, Case 2.1)
    OR $\displaystyle 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, $\displaystyle 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 $\displaystyle 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 $\displaystyle x \in A, x \notin B, x \notin C$ (Part 1, Case 1.1), then $\displaystyle x \notin B \Delta C$, and $\displaystyle x \in A$. Therefore $\displaystyle x \in A \Delta (B \Delta C)$.

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

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

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

    Therefore, have proven Part 1: $\displaystyle x \in (A \Delta B) \Delta C \Rightarrow x \in A \Delta (B \Delta C)$, so have proven that $\displaystyle (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 $\displaystyle A \Delta (B \Delta C) \subset (A \Delta B) \Delta C$. The rest would look like:

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

Similar Math Help Forum Discussions

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

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum