Results 1 to 10 of 10

Math Help - Symmetric Difference

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Symmetric Difference

    Prove A \triangle B = A \triangle C \Rightarrow B = C

    This is so obvious by inspection:

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

    But how do you prove this?
    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
    21
    Quote Originally Posted by novice View Post
    Prove A \triangle B = A \triangle C \Rightarrow B = C

    This is so obvious by inspection:

    A \triangle B = (A\backslash B) \cup (B\backslash A)= (A \backslash C) \cup (C \backslash A)=A \triangle C
    Suppose that B\ne C then we may assume WLOG that B\not\subseteq C so that there is some b\in B-C

    But how do you prove this?
    Let x\in B. If x\in A then x\notin A\Delta B=A\Delta C and since x\in A it follows that x\notin A\Delta C\implies x\in C. If x\notin A then x\in B-A\subseteq A\Delta B=A\Delta C and thus x\in A\Delta C. But, since x\notin A it follows that x\in C-A\implies x\in C
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Another way is to note that B = (A\vartriangle B)\vartriangle A, and similarly for C. This in turn can be proved by showing that x\in (A\vartriangle B) = (x\in A)\oplus (x\in B) where x\in X=1 or 0 depending on whether x is in X and \oplus is exclusive or. A similar method for proving associativity of \vartriangle is described in this post. If one starts with knowing that \vartriangle is associative and commutative then B = (A\vartriangle B)\vartriangle A is obvious.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    This a second way. Suppose that B\not\subset C.
    Then \left( {\exists t \in B\backslash C} \right) now either t\notin A or t\in A.

    If t\notin A then because t\in B then t\in A\Delta B= A\Delta C .
    But that means t\in C which is contradiction.

    If t\in A because t\notin C we have t\in A\Delta C= A\Delta B.
    But that means that t\notin B which is a contradiction.

    So B\subseteq C.

    Likewise we prove that C\subseteq B so B=C.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by emakarov View Post
    Another way is to note that B = (A\vartriangle B)\vartriangle A, and similarly for C. This in turn can be proved by showing that x\in (A\vartriangle B) = (x\in A)\oplus (x\in B) where x\in X=1 or 0 depending on whether x is in X and \oplus is exclusive or. A similar method for proving associativity of \vartriangle is described in this post. If one starts with knowing that \vartriangle is associative and commutative then B = (A\vartriangle B)\vartriangle A is obvious.
    Wow, this looks like Set Theory for graduate students. Which book covers this. What prep work do I need to learn this?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Yours is so elegant.

    Mine looks naive:
    Part 1. Suppose x \in (B \wedge A\triangle B = A \triangle C). Prove x\in C, so B\subseteq C

    Part 2. Suppose x \in (C \wedge A\triangle B = A \triangle C). Prove x\in B, so C \subseteq B

    (B\subseteq C) \wedge (C \subseteq B). Thus B=C

    The scratch work for part 1 and 2 were long. They entire roll of toilet paper.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by novice View Post
    Which book covers this. What prep work do I need to learn this?
    Excellent for getting a real solid grasp of mathematical proof for such subjects as set theory is 'Logic: Techniques Of Formal Reasoning' by Kalish, Montague, and Mar. Then, with that background, I'd get 'Elements Of Set Theory' by Enderton and, perhaps as a supplement to Enderton, also 'Axiomatic Set Theory' by Suppes.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by novice View Post
    x \in (B \wedge A\triangle B = A \triangle C). Prove x\in C, so B\subseteq C
    Maybe what you mean is:

    Suppose A \triangleB = A \triangleC & x in B. Show x in C.

    Quote Originally Posted by novice View Post
    Suppose x \in (C \wedge A\triangle B = A \triangle C). Prove x\in B, so C \subseteq B
    Maybe what you mean is:

    Suppose A \triangleB = A \triangleC & x in C. Show x in B.

    /

    You don't have to get confused by the symbols. It's pretty simple:

    Suppose A \triangleB = A \triangleC. Show B=C.
    Suppose x in B.
    Either x in A or x not in A.
    Suppose x in A.
    So x not in A \triangleB.
    So x not in A \triangleC.
    So, since x in A, if x were not in C then x would be in A\C so x would be in A \triangleC. So x in C.
    Suppose x not in A.
    So x in A \triangleB.
    So x in A \triangleC.
    So, since x not in A, we have x not in A\C, so x in C\A, so x in C.
    So, whether x in A or x not in A, we have x in C.
    So x in B implies x in C.
    So B is a subset of C.

    Then prove C is a subset of B in a similar manner.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    To emakarov:

    In your post #6 from oct 2009 you should also prove the following:

    If \mho \neq \O , \boldsymbol{F}(\mho ) is a group of all functions from \mho to \left \{ 0,1 \right \}, and \boldsymbol{P}(\mho ) is power group of \mho. Now if we define the transformation: \varphi : \boldsymbol{P}(\mho )\rightarrow \boldsymbol{F}(\mho ) such that for all A in \boldsymbol{P}(\mho ),  \varphi (A)=\chi _A.

    So we need to prove that \varphi is a injective transformation.

    ( \chi is characteristic function)
    Last edited by Also sprach Zarathustra; November 3rd 2010 at 08:36 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    If I'm not mistaken, the proofs given so far (except I didn't work through emakarov's version), including mine, use non-intuitionistic logic. My hunch is that that is unavoidable.
    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, 11:34 PM
  2. Symmetric difference
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 7th 2010, 04:36 PM
  3. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 30th 2009, 05:51 PM
  4. Symmetric Difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 5th 2009, 02:09 PM
  5. symmetric difference
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 27th 2009, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum