1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving associativity and commutativity for an operation.

  1. Sep 13, 2012 #1
    1. The problem statement, all variables and given/known data
    Assume that * is an operation on S with identity element e and that,

    x * (y * z) = (x * z) * y

    for all x,y,z [itex]\in[/itex] S. Prove that * is commutative and associative.

    2. The attempt at a solution
    I want to prove commutativity first as that may make it easier to prove associativity. I have made a few Cayley tables proving this, but I am not sure if that is a real proof. For example, having x*z = e, y*z = x, and x*x = y. These are arbitrary selections as long as no two elements are in the same row or column (and LHS = RHS). After that, I can fill in the table one and only one way regardless of my above selections within those two parameters. Here is a picture of what I mean:


    *|e x y z
    ---------
    e|e x y z
    x|x y _ _
    y|y _ _ _
    z|z e x _


    Filling in the rest of the table, I will get symmetry along the diagonal implying that * is commutative (and associative also).

    However, I want to prove this without a table using the identity given. My brain is kind of tired right now and I feel it is very obvious. But for commutativity, I must get rid of one of the elements since commutativity is only between two elements. Can I assume, as I did with the table, that an arbitrary selection of two elements will equal the identity element, e.g. x*z = e? Even if I do, I can't seem to 'remove' an element... I guess I need a break. Thanks in advance.
     
  2. jcsd
  3. Sep 13, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    What if you choose x=e?
     
  4. Sep 13, 2012 #3

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There's no need to play around with tables, and in any case your table assumes that S contains only four elements, so it can't constitute a general proof. Also, assuming that x*z = e for some x and z is NOT an arbitrary selection. I see nothing in the problem statement justifying such an assumption.

    Instead, I suggest working with the given assumption:

    x * (y * z) = (x * z) * y for ALL choices of x, y, and z. Thus in particular it's true for some specific choice, e.g. x = e seems like a useful choice to start with.
     
  5. Sep 13, 2012 #4
    Hm, that is a good point. I didn't know I could let x = e. I can let x = e because any arbitrary element in S could be the identity element?
     
  6. Sep 13, 2012 #5

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, you are given that the equation is true no matter how you choose x, y, and z. So the goal is to make particular choices that allow you to conclude associativity and commutativity.
     
  7. Sep 13, 2012 #6
    And for associativity:

    Code (Text):

    x*(y*z) = (z*x)*y
            = (z*e)*y
            = z*y
            = (z*y)*e
            = e*(y*z)
            = x*(y*z)
     
    Quite verbose I know, but is this legal?
     
  8. Sep 13, 2012 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It's legal as long as it's understood that x = e throughout. But what does it prove? It seems that you have shown that x*(y*z) equals itself. It's true, but not very interesting.
     
  9. Sep 13, 2012 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Actually, I take that back. How do you justify this step?

    (z*y)*e = e*(y*z)
     
  10. Sep 13, 2012 #9
    Oh that's right... could I do this:
    Code (Text):

    x*(y*z) = (z*x)*y
            = (z*e)*y
            = z*y
            = z*y*e
            = z*(y*e)
            = z*(e*y)
            = (e*y)*z
            = (x*y)*z
     
     
  11. Sep 13, 2012 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Be careful here. It's true that y = y * e and therefore z*y = z*(y*e), but the intermediate step z*y*e is meaningful only if you assume associativity. But that's one of the things you're trying to prove!
    This is true because y*e = e*y (by definition of identity), but then you didn't need the previous step.
    No, this doesn't follow from the previous step. You're assuming commutativity here.
     
  12. Sep 13, 2012 #11
    Sorry I forgot to mention that I have proven for commutativity.

    Code (Text):

    Let x = e,

    x*(y*z) = (z*x)*y
    e*(y*z) = (z*e)*y
    y*z = z*y

    Therefore, * is commutative.
     
    And the part you warned me about I did feel as if it was not right... but as of right now I don't know how I could introduce parenthesis to form the LHS or if I have to use a different approach.
     
  13. Sep 13, 2012 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, if you've proven commutativity, then proving associativity is much easier than what you are doing. Hint: try applying commutativity directly to the given equation:

    x * (y * z) = (x * z) * y
     
  14. Sep 14, 2012 #13
    Ok, so two people have shown me this for associativity:
    Code (Text):

    x*(y*z) = (z*x)*y
            = (x*z)*y
            = y*(z*x)
            = (y*x)*z     <- How?
            = (x*y)*z
     
    Is that step assuming associativity? I do not know why 'x' can be brought into the parenthesis and taking out y', such as y*(z*x) = (y*x)*z. The rest of the steps I see as applying commutative law.
     
  15. Sep 14, 2012 #14

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I agree, I don't see how that step can be justified. Once again, that procedure looks more complicated than it needs to be. If you have already proved commutativity, then simply apply it to the given equation.

    x * (y * z) = (x * z) * y

    Hint: apply it to the left hand side of this equation. This will give you a one-line proof.
     
  16. Sep 14, 2012 #15
    Wow, you know how dumb I feel right now? Thanks a lot for your help + patience. I've had a history of over-complicating problems because I never look for obvious things. Be sure I'll have more problems as I'm taking Analysis, Abstract Algebra and a calc-based Statistics course, but I'm not worried about the Stats so much.
     
  17. Sep 14, 2012 #16

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No problem. With more experience/practice, you'll develop a better instinct for how to proceed with proofs. I'm sure I would laugh at the longwindedness if I could look back at my homework assignments from my first analysis class.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving associativity and commutativity for an operation.
  1. Prove commutative (Replies: 5)

  2. Operators commute? (Replies: 6)

Loading...