# Homework Help: Proving associativity and commutativity for an operation.

1. Sep 13, 2012

### c0dy

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 $\in$ 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. Sep 13, 2012

### micromass

What if you choose x=e?

3. Sep 13, 2012

### jbunniii

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.

4. Sep 13, 2012

### c0dy

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?

5. Sep 13, 2012

### jbunniii

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.

6. Sep 13, 2012

### c0dy

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?

7. Sep 13, 2012

### jbunniii

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.

8. Sep 13, 2012

### jbunniii

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

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

9. Sep 13, 2012

### c0dy

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

10. Sep 13, 2012

### jbunniii

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.

11. Sep 13, 2012

### c0dy

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.

12. Sep 13, 2012

### jbunniii

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

13. Sep 14, 2012

### c0dy

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.

14. Sep 14, 2012

### jbunniii

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.

15. Sep 14, 2012

### c0dy

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.

16. Sep 14, 2012

### jbunniii

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.