A set has the associative property under a particular operation if the result of the operation is the same no matter how we group any sets of 3 or more elements joined by the operation. This definition will make more sense as we look at some examples.

More formally, if *x*, *y* and *z* are variables that represent **any 3 arbitrary elements** in the set we are looking at (let’s call the set we are looking at A), and the symbol # represents our operation, then the associative property for A with the operation # would be:

(*x#y*)#*z* = *x*#(*y#z*).

This means that the associative property only holds for the set A and the operation # if, **no matter what elements we take from A and put in place of x, y and z**, (

Remember that the parentheses just tell us **which pair to do first**.

Notice that with **all operations**, the operation can only act on **one pair of elements at a time**. So the expression x#y#z doesn’t make sense, unless we set up a rule that tells us to go from left to right first or to go from right to left first, because there is no way for us to know **which operation to do first**: should we do x#y first, or y#z first? When we do addition or subtraction or multiplication or division, we have a rule that tells us just to go from left to right. **But we don’t necessarily have this rule for arbitrary operations!** If we are working with any operation that is **not** addition, subtraction, multiplication, or division, then **we must have parentheses for any expression with more than two elements in it so that we know which occurrence of the operation to do first! **

First let’s look at a few infinite sets with operations that are already familiar to us:

a) The set of

natural numbersis associative under the operation ofaddition, because it is true that foranytwo natural numbers x, y, and z, (x+y)+z = x+(y+z).

b) The set of

integersisnotassociative under the operation ofdivision, because for any three integers x, y and z, there are many cases where (x ÷ y) ÷ z ≠ x ÷ (y ÷ z)! For example:(10 ÷ 5) ÷ 2 = 2 ÷ 2 = 1

10 ÷ (5 ÷ 2) = 10 ÷ 2.5 = 2

1 ≠ 2!

So (10 ÷ 5) ÷ 2 ≠ 10 ÷ (5 ÷ 2)

So (x ÷ y) ÷ z = x ÷ (y ÷ z) is

nottrue forallintegers x, y and z!

to see some more examples!

It can be a little bit more difficult, if all we have is an operation table, to tell whether or not a set has the associative property under a particular operation. To figure out how to do this,

e) Here is an operation table for the set {a,b,c} and the operation *:

* |
a |
b |
c |

a |
a |
b |
c |

b |
b |
a |
c |

c |
c |
c |
a |

To check associativity, we must check

every possible instanceof the equation (x*y)*z = x*(y*z). That means we must think of every possible combination of what x, y, and z could be.

Using the above table to write out every possible combination of elements that could go in for x, y, and z and then calculating (x*y)*z and comparing it to x*(y*z) gives us the following table:

Values of x, y, z (x*y)*z x*(y*z) Does (x*y)*z = x*(y*z)? x=a, y=a, z=a (a*a)*a = a*a = a a*(a*a) = a*a = a a = a, So (a*a)*a = a*(a*a). x=a, y=a, z=b (a*a)*b = a*b = b a*(a*b) = a*b = b b = b, So (a*a)*b = a*(a*b). x=a, y=a, z=c (a*a)*c = a*c = c a*(a*c) = a*a = c c = c, So (a*a)*c = a*(a*c). x=a, y=b, z=a (a*b)*a = b*a = b a*(b*a) = a*b = b b = b, So (a*b)*a = a*(b*a). x=a, y=b, z=b (a*b)*b = b*b = a a*(b*b) = a*a = a a = a, So (a*b)*b = a*(b*b). x=a, y=b, z=c (a*b)*c = b*c = c a*(b*c) = a*c = c c = c, So (a*b)*c = a*(b*c). x=a, y=c, z=a (a*c)*a = c*a = c a*(c*a) = a*c = c c = c, So (a*c)*a = a*(c*a). x=a, y=c, z=b (a*c)*b = c*b = c a*(c*b) = a*c = c c = c, So (a*c)*b = a*(c*b). x=a, y=c, z=c (a*c)*c = c*c = a a*(c*c) = a*a= a a = a, So (a*c)*c = a*(c*c). x=b, y=a, z=a (b*a)*a = b*a = b b*(a*a) = b*a = b b = b, So (b*a)*a = b*(a*a). x=b, y=a, z=b (b*a)*b = b*b = a b*(a*b) = b*b = a a = a, So (b*a)*b = b*(a*b). x=b, y=a, z=c (b*a)*c = b*c = c b*(a*c) = b*c = c c = c, So (b*a)*c = b*(a*c). x=b, y=b, z=a (b*b)*a = a*a = a b*(b*a) = b*b = a a = a, So (b*b)*a = b*(b*a). x=b, y=b, z=b (b*b)*b = a*b = b b*(b*b) = b*a = b b = b, So (b*b)*b = b*(b*b). x=b, y=b, z=c (b*b)*c = a*c = c b*(b*c) = b*c = c c = c, So (b*b)*c = b*(b*c). x=b, y=c, z=a (b*c)*a = c*a = c b*(c*a) = b*c = c c = c, So (b*c)*a = b*(c*a). x=b, y=c, z=b (b*c)*b = c*b = c b*(c*b) = b*c = c c = c, So (b*c)*b = b*(c*b). x=b, y=c, z=c (b*c)*c = c*c = a b*(c*c) = b*a = b a ≠ b, So (b*c)*c ≠ b*(c*c)! x=c, y=a, z=a (c*a)*a = c*a = c c*(a*a) = c*a = c c = c, So (c*a)*a = c*(a*a). x=c, y=a, z=b (c*a)*b = c*b = c c*(a*b) = c*b = c c = c, So (c*a)*b = c*(a*b). x=c, y=a, z=c (c*a)*c = c*c = a c*(a*c) = c*c = a a = a, So (c*a)*c = c*(a*c). x=c, y=b, z=a (c*b)*a = c*a = c c*(b*a) = c*b = c c = c, So (c*b)*a = c*(b*a). x=c, y=b, z=b (c*b)*b = c*b = c c*(b*b) = c*a = c c = c, So (c*b)*b = c*(b*b). x=c, y=b, z=c (c*b)*c = c*c = a c*(b*c) = c*c = a a = a, So (c*b)*c = c*(b*c). x=c, y=c, z=a (c*c)*a = a*a = a c*(c*a) = c*c = a a = a, So (c*c)*a = c*(c*a). x=c, y=c, z=b (c*c)*b = a*b = b c*(c*b) = c*c = a b ≠ a, So (c*c)*b ≠ c*(c*b)! x=c, y=c, z=c (c*c)*c = a*c = c c*(c*c) = c*a = c c = c, So (c*c)*c = c*(c*c).

So the set {a,b,c} under the operation * is

notassociative because we haveat least oneexample where (x*y)*z ≠ x*(y*z)! In fact we havetwoexamples when this fails: (b*c)*c ≠ b*(c*c) and (c*c)*b ≠ c*(c*b)! When x is b and y is c and z is c, (x*y)*z ≠ x*(y*z)! And when x is c and y is c and z is b (x*y)*z ≠ x*(y*z)!

While there is really no good shortcut you can use to try to see if a set under an operation given by an operation table is associative, there are a few things you can look for which may cut down the number of instances you need to check:If a set has an

identity, then we don't need to check any instances which include the identity. Why? Let's take a look at what happens if we compute an instance which contains the identity. For this purpose, we will let e represent the identity element of our set, and we will letxandyrepresent any two elements of our set.Let's see if (e*

x)*y= e*(x*y) is true.First we will compute (e*

x)*y. Since the identity by definition does not change elements when it acts on them with the operation, we must have e*x=x. So (e*x)*y=x*y.Now we will compute e*(

x*y). Again, since the identity by definition does not change elements when it acts on them with the operation, we must have e*(x*y)=x*y. So (e*x)*y= e*(x*y) is true.We can use similar reasoning to see that (

x*e)*y=x*(e*y) is true and that (x*y)*e=x*(y*e) is true.

So expressions which contain the identity will always be associative. This means that in order to check whether or not a set has the associative property, we need only check expressions which contain only elements which are NOT the identity.This can cut down considerably on the number of items we check. To see this, let's look at our example again:

## Example:

Here is an operation table for the set {a,b,c} and the operation *:

*

a

b

c

a

a

b

c

b

b

a

c

c

c

c

a

Notice that this set has an identity: a, because whenever a is multiplied by

anyelement in the set on either the right or the left, it leaves that element unchanged.So, to check associativity, we must check

every possible instanceof the equation (x*y)*z = x*(y*z) which does not include a (becuase a is the identity, and we don't need to check combinations which include the identity).

Values of x, y, z (x*y)*z x*(y*z) Does (x*y)*z = x*(y*z)? x=b, y=b, z=b (b*b)*b = a*b = b b*(b*b) = b*a = b b = b, So (b*b)*b = b*(b*b). x=b, y=b, z=c (b*b)*c = a*c = c b*(b*c) = b*c = c c = c, So (b*b)*c = b*(b*c). x=b, y=c, z=b (b*c)*b = c*b = c b*(c*b) = b*c = c c = c, So (b*c)*b = b*(c*b). x=b, y=c, z=c (b*c)*c = c*c = a b*(c*c) = b*a = b a ≠ b, So (b*c)*c ≠ b*(c*c)! x=c, y=b, z=b (c*b)*b = c*b = c c*(b*b) = c*a = c c = c, So (c*b)*b = c*(b*b). x=c, y=b, z=c (c*b)*c = c*c = a c*(b*c) = c*c = a a = a, So (c*b)*c = c*(b*c). x=c, y=c, z=b (c*c)*b = a*b = b c*(c*b) = c*c = a b ≠ a, So (c*c)*b ≠ c*(c*b)! x=c, y=c, z=c (c*c)*c = a*c = c c*(c*c) = c*a = c c = c, So (c*c)*c = c*(c*c).Notice that by only checking the instances which

do not contain the identity a, we have narrowed down the number of combinations we need to check from 27 to 8! This is a big improvement!

Be careful! Many students make the mistake of concluding that a set is associative by checking just a few examples. You CANNOT do this! To determine whether or not a set is associative, YOU MUST CHECK EVERY SINGLE COMBINATION OF 3 ELEMENTS, unless you have a good general argument for why all combinations will be associative or you have a good reason (such as the existence of an identity element) for limiting the number of cases you must check.(Notice that even when you have the existence of an identity element, you still have to check ALL the cases which do not include the identity element.)

Now return to Blackboard to answer Group Lecture Questions 6: Associativity!