Results 1 to 10 of 10

Thread: Symmetric Difference

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Symmetric Difference

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

    This is so obvious by inspection:

    $\displaystyle 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
    22
    Quote Originally Posted by novice View Post
    Prove $\displaystyle A \triangle B = A \triangle C \Rightarrow B = C$

    This is so obvious by inspection:

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

    But how do you prove this?
    Let $\displaystyle x\in B$. If $\displaystyle x\in A$ then $\displaystyle x\notin A\Delta B=A\Delta C$ and since $\displaystyle x\in A$ it follows that $\displaystyle x\notin A\Delta C\implies x\in C$. If $\displaystyle x\notin A$ then $\displaystyle x\in B-A\subseteq A\Delta B=A\Delta C$ and thus $\displaystyle x\in A\Delta C$. But, since $\displaystyle x\notin A$ it follows that $\displaystyle 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,577
    Thanks
    790
    Another way is to note that $\displaystyle B = (A\vartriangle B)\vartriangle A$, and similarly for $\displaystyle C$. This in turn can be proved by showing that $\displaystyle x\in (A\vartriangle B) = (x\in A)\oplus (x\in B)$ where $\displaystyle x\in X=1$ or $\displaystyle 0$ depending on whether $\displaystyle x$ is in $\displaystyle X$ and $\displaystyle \oplus$ is exclusive or. A similar method for proving associativity of $\displaystyle \vartriangle$ is described in this post. If one starts with knowing that $\displaystyle \vartriangle$ is associative and commutative then $\displaystyle B = (A\vartriangle B)\vartriangle A$ is obvious.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

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

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

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

    So $\displaystyle B\subseteq C$.

    Likewise we prove that $\displaystyle C\subseteq B$ so $\displaystyle 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 $\displaystyle B = (A\vartriangle B)\vartriangle A$, and similarly for $\displaystyle C$. This in turn can be proved by showing that $\displaystyle x\in (A\vartriangle B) = (x\in A)\oplus (x\in B)$ where $\displaystyle x\in X=1$ or $\displaystyle 0$ depending on whether $\displaystyle x$ is in $\displaystyle X$ and $\displaystyle \oplus$ is exclusive or. A similar method for proving associativity of $\displaystyle \vartriangle$ is described in this post. If one starts with knowing that $\displaystyle \vartriangle$ is associative and commutative then $\displaystyle 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 $\displaystyle x \in (B \wedge A\triangle B = A \triangle C)$. Prove $\displaystyle x\in C$, so $\displaystyle B\subseteq C$

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

    $\displaystyle (B\subseteq C) \wedge (C \subseteq B)$. Thus $\displaystyle 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
    470
    Thanks
    6
    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
    470
    Thanks
    6
    Quote Originally Posted by novice View Post
    $\displaystyle x \in (B \wedge A\triangle B = A \triangle C)$. Prove $\displaystyle x\in C$, so $\displaystyle B\subseteq C$
    Maybe what you mean is:

    Suppose A$\displaystyle \triangle$B = A$\displaystyle \triangle$C & x in B. Show x in C.

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

    Suppose A$\displaystyle \triangle$B = A$\displaystyle \triangle$C & x in C. Show x in B.

    /

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

    Suppose A$\displaystyle \triangle$B = A$\displaystyle \triangle$C. 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$\displaystyle \triangle$B.
    So x not in A$\displaystyle \triangle$C.
    So, since x in A, if x were not in C then x would be in A\C so x would be in A$\displaystyle \triangle$C. So x in C.
    Suppose x not in A.
    So x in A$\displaystyle \triangle$B.
    So x in A$\displaystyle \triangle$C.
    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 $\displaystyle \mho \neq \O $, $\displaystyle \boldsymbol{F}(\mho )$ is a group of all functions from $\displaystyle \mho$ to $\displaystyle \left \{ 0,1 \right \}$, and $\displaystyle \boldsymbol{P}(\mho ) $ is power group of $\displaystyle \mho$. Now if we define the transformation: $\displaystyle \varphi : \boldsymbol{P}(\mho )\rightarrow \boldsymbol{F}(\mho )$ such that for all $\displaystyle A$ in $\displaystyle \boldsymbol{P}(\mho )$, $\displaystyle \varphi (A)=\chi _A$.

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

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

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    470
    Thanks
    6
    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: Jan 25th 2011, 10:34 PM
  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