Articles

Commutative, but not associative

In Maths on December 28, 2008 by Matt Giuca Tagged:

I’ve been wondering for awhile if commutativity implies associativity in mathematics. That is, for any given binary operation, if it is commutative, is it also associative?

I’ve never seen this implication stated, but I’ve also never thought of a counter-example. Until now! So I thought I’d quickly share it.

First, to state the problem – every commutative operation I’ve seen is also associative. This means that if a * b = b * a, for any given operation *, then it’s also true that a * (b * c) = (a * b) * c.

It somehow makes intuitive sense that commutativity be a “more powerful” property than associativity. After all, if an operation can have its terms switched, and survive intact, surely it can weather a little order-of-operations rearrangement!

In any event, I came up with this function which is commutative, but not associative. In Haskell:

f :: Ord a => [a] -> [a] -> [a]
f x y = if x < y then x ++ y else y ++ x

It takes two lists, and concatenates them in sorted order. Thus, swapping the operands has no effect on the outcome, but the operation (like regular concatenation) is inherently non-associative.

[2] `f` ([1] `f` [3]) == [1,3,2]
([1] `f` [3]) `f` [2] == [1,3,2] (commutes)
([2] `f` [1]) `f` [3] == [1,2,3] (does not associate)
Advertisements

6 Responses to “Commutative, but not associative”

  1. Another nice example of an operation that is commutative but not associative is x*y defined by x*y = x+y – xy, for each x and y in R (the reals).

    The arithmetic mean is another example: x*y = (x+y)/2 for each x,y in R.

    A slight generalization of the mean would be to start with an operation, call it ., that is both commutative and associative and another operation, call it @, that is non-associative. Fix and element a in your group that is not a right-identity for @, and define * by x*y = (x.y)@a. This is clearly commutative, but it generally won’t be associative. At the very least, it can be used as a nice “jumping off point” to build some accessible operations that are commutative but not associative.

    Rather than fix an element a, you can introduce a third operation that is both commutative and associative, call it #, and use the . and @ above to define another * as x*y = (x.y)@(x#y). This is more akin to the first example.

  2. Whoops! I should have said x*y = xy – (x+y) for that first example.

  3. Another commutative but non associative function you may have seen is “Given two Rock-Paper-Scissors hands, which one wins?” Obviously it doesn’t matter which order you give it a particular pair of hands, but the order in which you evaluate pairs certainly does matter.

  4. @pez True. I’ve been thinking only about operations where the output actually has the same “type” as the inputs. In the case of your example, the output is NOT a rock-paper-scissors hand (it is a boolean). So it doesn’t make sense to talk about (a * b) * c at all when * is “which one wins”. Non-associative indeed!

    But if we’re going to talk about such operations, there is a much simpler one than rock-paper-scissors: == (equality). (a == b) equals (b == a), but clearly, (a == b) == c does not equal a == (b == c), because (a == b) == c is meaningless unless c is a boolean value.

    • @matt: pez is correct. Given set H, with elements r, p and s, operation * maps an ordered pair of elements from H to an element of H. For example, the answer to r * s is r, because rock beats scissors. The answer isn’t true or false.

  5. Matt, I had thoughts about commutativity vs. associativity too, and agree with your first 4 paragraphs.

    A very simple example I encountered is the NAND function – it’s commutative but not associative. Hope that helps!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: