Results 1 to 4 of 4

Thread: symmetric difference of sets

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    37

    symmetric difference of sets

    prove that for sets $\displaystyle A,B,C,D$
    $\displaystyle A \Delta B = C \Delta D$ if and only if $\displaystyle A \Delta C = B \Delta D$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by santiagos11 View Post
    prove that for sets $\displaystyle A,B,C,D$
    $\displaystyle A \Delta B = C \Delta D$ if and only if $\displaystyle A \Delta C = B \Delta D$
    What have you tried? Although there are many I think that the definition of symmetric difference best suited to this case is $\displaystyle A\Delta B=\left(A\cup B\right)-\left(A\cap B\right)$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    There is also a different way to solve this that sometimes works very well with symmetric difference.

    Define the function $\displaystyle in$ by $\displaystyle in(x,A)=1$ if $\displaystyle x\in A$ and $\displaystyle in(x,A)=0$ if $\displaystyle x\notin A$. Here $\displaystyle A$ is any set and $\displaystyle x$ is any object.

    Also, define the function $\displaystyle \oplus:\{0,1\}\times\{0,1\}\to\{0,1\}$ as follows:
    $\displaystyle 0\oplus0=0$
    $\displaystyle 0\oplus1=1$
    $\displaystyle 1\oplus0=1$
    $\displaystyle 1\oplus1=0$
    (If we associate 1 with True and 0 with False, then $\displaystyle x\oplus y=\neg(x\leftrightarrow y)$. Also, $\displaystyle \oplus$ is addition modulo 2.) One can check that $\displaystyle \oplus$ is commutative and associative.

    Show that $\displaystyle in(x,A\triangle B)=in(x,A)\oplus in(x,B)$ for all $\displaystyle A$, $\displaystyle B$, and $\displaystyle x$.

    The part above was generic; it applies to any problem with symmetric difference and has to be done only once.

    Now, from this problem's assumption and the fact above we have $\displaystyle in(x,A)\oplus in(x,B)=in(x,C)\oplus in(x,D) $ for all $\displaystyle x$. We can add (using $\displaystyle \oplus$) an expression $\displaystyle in(x,E)$ to both sides where $\displaystyle E$ is $\displaystyle A$, $\displaystyle B$, $\displaystyle C$, or $\displaystyle D$. E.g., if we add $\displaystyle in(x,B)$ to both sides, we get $\displaystyle in(x,A)$=$\displaystyle in(x, C)\oplus in(x,D)\oplus in(x,B)$. From here it is easy to show the desired equation.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello santiagos11
    Quote Originally Posted by santiagos11 View Post
    prove that for sets $\displaystyle A,B,C,D$
    $\displaystyle A \Delta B = C \Delta D$ if and only if $\displaystyle A \Delta C = B \Delta D$
    I think this is easiest to prove by re-writing it as the equivalent statement using logical propositions. In other words:
    Prove that if $\displaystyle a, b,c, d$ are logical propositions, then $\displaystyle a \oplus b \equiv c \oplus d$ if and only if $\displaystyle a \oplus c \equiv b \oplus d$, where $\displaystyle \oplus$ denotes 'exclusive or'.
    This is quite straightforward if you use a Truth Table for each of the compound propositions and show that each table produces an identical output.

    The attached diagram shows the truth table for $\displaystyle a \oplus b \equiv c \oplus d$. It is a simple matter to show that the table for $\displaystyle a \oplus c \equiv b \oplus d$ produces the same result.

    Grandad
    Attached Thumbnails Attached Thumbnails symmetric difference of sets-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Nov 3rd 2010, 08:49 AM
  2. Symmetric difference
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Jun 7th 2010, 03:36 PM
  3. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 30th 2009, 04:51 PM
  4. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 5th 2009, 01:09 PM
  5. symmetric difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 27th 2009, 10:15 AM

Search Tags


/mathhelpforum @mathhelpforum