Proving associativity and commutativity for an operation.

[c0dy]

Homework Statement

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.

 

[micromass]

What if you choose x=e?

 

[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.

 

[c0dy]

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.

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?

 

[jbunniii]

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?

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.

 

[c0dy]

And for associativity:

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?

 

[jbunniii]

And for associativity:

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?

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.

 

[jbunniii]

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

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

 

[c0dy]

Oh that's right... could I do this:

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

 

[jbunniii]

Oh that's right... could I do this:

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

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!

        = z*(e*y)

This is true because y*e = e*y (by definition of identity), but then you didn't need the previous step.

        = (e*y)*z

No, this doesn't follow from the previous step. You're assuming commutativity here.

        = (x*y)*z

 

[c0dy]

Sorry I forgot to mention that I have proven for commutativity.

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.

 

[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

 

[c0dy]

Ok, so two people have shown me this for associativity:

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.

 

[jbunniii]

Ok, so two people have shown me this for associativity:

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.

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.

 

[c0dy]

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.

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.

 

[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.