• Support PF! Buy your school textbooks, materials and every day products Here!

Proving associativity and commutativity for an operation.

  • Thread starter c0dy
  • Start date
  • #1
15
0

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

Answers and Replies

  • #2
22,097
3,277
What if you choose x=e?
 
  • #3
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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
15
0
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?
 
  • #5
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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.
 
  • #6
15
0
And for associativity:

Code:
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
And for associativity:

Code:
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.
 
  • #8
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
Actually, I take that back. How do you justify this step?

(z*y)*e = e*(y*z)
 
  • #9
15
0
Oh that's right... could I do this:
Code:
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
Oh that's right... could I do this:
Code:
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!
Code:
        = z*(e*y)
This is true because y*e = e*y (by definition of identity), but then you didn't need the previous step.
Code:
        = (e*y)*z
No, this doesn't follow from the previous step. You're assuming commutativity here.
Code:
        = (x*y)*z
 
  • #11
15
0
Sorry I forgot to mention that I have proven for commutativity.

Code:
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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
15
0
Ok, so two people have shown me this for associativity:
Code:
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
Ok, so two people have shown me this for associativity:
Code:
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.
 
  • #15
15
0
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.
 
  • #16
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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.
 

Related Threads for: Proving associativity and commutativity for an operation.

  • Last Post
Replies
7
Views
3K
Replies
5
Views
10K
Replies
5
Views
4K
Replies
3
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
1K
Top