Results 1 to 10 of 10

Math Help - commutative operation

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    commutative operation

    Here's a question:


    For part (a) is it sufficient to show using the commutative law of union and the commutative law of intersection that:

    (A \star B) = (A \cup B) \backslash (A \cap B)

     = (B \cup A) \backslash (B \cap A) = (B \star A)

    Or do I need to show some other steps?

    Also, could anyone please show me how to prove that:

    (A \star B) \star C = (A \cap B \cap C) \cup (C \backslash (A \cup B)) \cup (A \backslash (B \cup C)) \cup (B \backslash (A \cap C))

    P.S.: is that a simplification of:
    (A \star B) \star C = (((A \cup B) \backslash (A \cap B)) \cup C) \backslash (((A \cup B) \backslash (A \cap B)) \cap C) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    You're dealing with the symmetric difference there. By far the slickest way I've seen to prove associativity is by emakarov here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    225
    So, did I show the commutativity correctly??

    And I know this is about symmetric difference but I didn't understand emakarov's post. Is there a more simple way of showing that it holds?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    I wasn't able to show associativity any other way. I showed the correspondence between the symmetric difference and the boolean xor function, showed the xor function was associative by the use of truth tables, and then I was done, essentially. Perhaps it was laziness: I didn't want to slog through all the boolean logic I would have had to do anyway.

    I think your commutativity proof is fine.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2009
    Posts
    225
    Quote Originally Posted by Ackbeet View Post
    I wasn't able to show associativity any other way. I showed the correspondence between the symmetric difference and the boolean xor function, showed the xor function was associative by the use of truth tables, and then I was done, essentially. Perhaps it was laziness: I didn't want to slog through all the boolean logic I would have had to do anyway.

    I think your commutativity proof is fine.
    So how would you show that the following holds

    (A \star B) \star C = (A \cap B \cap C) \cup (C \backslash (A \cup B)) \cup (A \backslash (B \cup C)) \cup (B \backslash (A \cap C))

    ? We didn't study anything about "boolean xor function"...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    I think you have a typo there: in your last unionand, you should have B\setminus(A\cup C).

    Proving this identity, with which I definitely agree, is probably just a matter of using DeMorgan's laws and other identities multiple times. You could start out with this:

    (A\star B)\star C\equiv ((A\cup B)\setminus(A\cap B))\star C
    \equiv (((A\cup B)\setminus(A\cap B))\cup C)\setminus(((A\cup B)\setminus(A\cap B))\cap C).

    There are some identities you'll need here, which you should prove if you haven't already:

    1. A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C).
    2. A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C).
    3. \;(B\setminus A)\cap C=(B\cap C)\setminus A=B\cap(C\setminus A).
    4. (B\setminus A)\cup C=(B\cup C)\setminus(A\setminus C).

    Another important identity you should know is that

    A\star B=(A\cup B)\setminus(A\cap B)=(A\setminus B)\cup(B\setminus A).

    You can see here for a nice Venn diagram of the symmetric difference as you've written it. That might help direct your proof.

    I should point out that I'm giving suggestions here. I haven't proven it the way you are proposing. I got too bogged down in the details. There are more than one thread in this forum dealing with the symmetric difference of sets. You can search for them. They might give you some more ideas.

    Like I said, though, the boolean exclusive or function approach is the easiest approach, in my opinion:

    1. Define the characteristic function \chi_{X}:X\to\{0,1\} by
    \chi_{X}(x)=\begin{cases}1\quad x\in X\\ 0\quad x\not\in X\end{cases}.
    2. Prove this Lemma: x\in X if and only if \chi_{X}(x)=1.
    3. Corollary: x\not\in X if and only if \chi_{X}(x)=0.
    4. Prove this Lemma: \chi_{X\star Y}=\chi_{X}\otimes\chi_{Y}. The \otimes symbol there is for exclusive or.
    5. Show that the exclusive or function is associative by using a truth table.
    6. Then you show that x\in(A\star B)\star C if and only if x\in A\star(B\star C). This is easy, because you just run through the logic you've just proven in the previous steps. You're done.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Dec 2009
    Posts
    225
    To prove this question I must use the set-theoretic way, and not any other way. I tried to use the identities you showed me. But I need some more help here:

    (A\star B)\star C = ((A\cup B)\setminus(A\cap B))\star C

    =(((A\cup B)\setminus(A\cap B))\cup C)\setminus(((A\cup B)\setminus(A\cap B))\cap C)

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

    =((A \setminus B) \cup C \cup (B \cup C) \setminus (A \setminus C)) \setminus (((A \setminus B) \cap C) \cup (B \setminus A) \cap C))

    =(A \cup C) \setminus (B \setminus C) \cup (B \cup C) \setminus (A \setminus C) \setminus (((A \setminus B) \cap C) \cup (B \setminus A) \cap C))

    So, I'm kind of stuck here... What can I do?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    If you're allowed to use compliments, then try this proof. Or here.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Dec 2009
    Posts
    225
    Quote Originally Posted by Ackbeet View Post
    If you're allowed to use compliments, then try this proof. Or here.
    I'm not getting how to use the compliments here and there isn't much time for me, so could you maybe help me to prove this without using the compliments?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Well, instead of set compliments, you could use some envelope set. That is, define set S as

    \displaystyle{S\equiv A\cup B\cup C}.

    Then, everywhere these proofs use a set compliment, you could use instead the symbol S\setminus A. That is, you insert S\setminus A for A' or A^{c}.

    So, for the proof here, you could start out as follows:

    By definition, we know that

    A\Delta B=(A\setminus B)\cup(B\setminus A). Therefore,

    (A\Delta B)\Delta C=((A\Delta B)\setminus C)\cup(C\setminus(A\Delta B))
    =((A \Delta B)\cap (S\setminus C)) \cup (C \cap (S\setminus(A \Delta B)))
    =(((A\setminus B)\cup(B\setminus A))\cap (S\setminus C)) \cup (C \cap (S\setminus((A\setminus B)\cup(B\setminus A)))).

    Then you continue with the development in the link.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Operation of convoulution is commutative
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: January 22nd 2011, 01:34 PM
  2. Operation @
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: April 2nd 2010, 12:10 AM
  3. Operation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 24th 2010, 08:20 PM
  4. Commutative Operation 71.10
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 28th 2009, 11:06 AM
  5. row operation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 17th 2007, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum