# Associativity: Examples

## Pos­i­tive examples

$$(x + y) + z = x + (y + z)$$ for all num­bers $$x, y,$$ and $$z.$$ Thus, ad­di­tion as­so­ci­ates. One easy way to see this fact is to con­sider a phys­i­cal sys­tem that im­ple­ments ad­di­tion, e.g., by tak­ing two piles of poker chips (where a poker chip with $$n$$ chips rep­re­sents the num­ber $$n$$) in on two in­put belts, and pro­duc­ing a pile of poker chips on the out­put belt. This func­tion can be im­ple­mented by sim­ply shov­ing both in­put piles onto the out­put pile. Clearly, when com­bin­ing three piles, it doesn’t mat­ter which piles get shoved onto the out­put tape in which or­der, so ad­di­tion is as­so­ci­a­tive.

### Multiplication

$$(x \times y) \times z = x \times (y \times z)$$ for all num­bers $$x, y,$$ and $$z.$$ Thus, mul­ti­pli­ca­tion as­so­ci­ates. It is, how­ever, a lit­tle harder to see why this must be the case for mul­ti­pli­ca­tion.

Imag­ine a phys­i­cal sys­tem im­ple­ment­ing mul­ti­pli­ca­tion, by tak­ing stacks of poker chips as in­put (where stacks with $$n$$ chips in them rep­re­sents the num­ber $$n$$), and pro­duc­ing an out­put by putting a copy of the left stack on the out­put tape for ev­ery chip in the right stack. Imag­ine us­ing this func­tion to com­bine three stacks of poker chips, a blue stack (rep­re­sent­ing $$x$$), a yel­low stack (rep­re­sent­ing $$y$$), and a red stack (rep­re­sent­ing $$z$$). We can ei­ther calcu­late $$(x \times y) \times z$$ or $$x \times (y \times z).$$ In both cases, the re­sult will be a bunch of copies of the origi­nal blue $$x$$ stack. The ques­tion is, how many copies will there be in each case?

In the first case, the ma­chine first puts $$y$$ copies of the blue stack in a line, and then makes $$z$$ copies of that line. In the sec­ond case, the ma­chine first makes $$z$$ copies of the yel­low stack. Each of those yel­low stacks cor­re­sponds to one of the lines from the first case, and each yel­low chip on each yel­low stack cor­re­sponds to one of the blue stacks in the first case. A blue stack is placed on the out­put in the sec­ond case for each of those yel­low chips, so the num­ber of blue stacks in each case is the same.

### Concatenation

The con­cate­na­tion of strings is an­other as­so­ci­a­tive func­tion: concat("a",concat("b","c")) = concat(concat("a","b"),"c") = "abc".

Con­cate­na­tion is an ex­am­ple of an as­so­ci­a­tive func­tion that is not com­mu­ta­tive: When re­duc­ing a list of strings to a sin­gle string, it doesn’t mat­ter what or­der you com­bine ad­ja­cent el­e­ments in, but it does mat­ter that you leave the el­e­ments in their origi­nal or­der.

In fact, any func­tion that just sticks its in­puts to­gether (pos­si­bly with some ex­tra stuff in the mid­dle) is as­so­ci­a­tive: A func­tion which takes wooden blocks as in­put, and glues them to­gether (with a small white block in the mid­dle) is as­so­ci­a­tive, be­cause if you put in blue, yel­low, and red blocks then you get a blue-white-yel­low-white-red block out the end, re­gard­less of the or­der you com­bine ad­ja­cent blocks in.

## Nega­tive examples

### Func­tions with a history

The func­tion xconcat that con­cate­nates its in­puts and puts an “x” on the front: xconcat("A", xconcat("B","C")) = "xAxBC", but xconcat(xconcat("A", "B"), "C") = "xxABC". The prob­lem in this case is that the out­put car­ries a trace of which ad­ja­cent el­e­ments were com­bined in which or­der, which makes the func­tion non-as­so­ci­a­tive.

In fact, any func­tion that car­ries a his­tory of the ap­pli­ca­tion or­der with it can’t be as­so­ci­a­tive. Thus, if the in­puts carry his­tory about which in­puts were com­bined with which other in­puts, and the out­put pre­serves (and adds to) that his­tory, the func­tion can’t be as­so­ci­a­tive. As­so­ci­a­tivity is, fun­da­men­tally, about the out­put not de­pend­ing on which path was taken to get to it.

### Subtraction

Sub­trac­tion does not as­so­ci­ate, as $$(5-3)-2=0$$ but $$5-(3-2)=4.$$ To see what went wrong, first no­tice that all in­puts con­tribute ei­ther pos­i­tively or nega­tively to the re­sult. La­bel all in­puts (in their origi­nal pos­i­tive states) with up-ar­rows; we will track whether that in­put has a pos­i­tive or nega­tive im­pact on the fi­nal out­put. Sub­trac­tion flips its right-hand in­put up­side down be­fore com­bin­ing it with its left-hand in­put, so given in­puts la­beled $$\uparrow$$ and $$\uparrow$$ we should la­bel its out­put $$\uparrow\downarrow.$$ When com­bin­ing three in­puts, we can ei­ther com­bine the left two first or the right two first. If we com­bine the left two first, then the sec­ond sub­trac­tion is run on in­puts la­beled $$\uparrow\downarrow$$ and $$\uparrow,$$ and pro­duces an out­put $$\uparrow\downarrow\downarrow,$$ in which the first in­put con­tributes pos­i­tively and the other in­puts con­tribute nega­tively. But if we com­bine the right two in­puts first, then the sec­ond sub­trac­tion is run on in­puts la­beled $$\uparrow$$ and $$\uparrow\downarrow,$$ and pro­duces an out­put $$\uparrow\downarrow\uparrow,$$ in which the first and third in­puts con­tribute pos­i­tively and the sec­ond con­tributes nega­tively. Thus, the con­tri­bu­tion of the third in­put de­pends on which ad­ja­cent el­e­ments are com­bined in which or­der, so sub­trac­tion does not as­so­ci­ate.

### Cycli­cal preferences

Con­sider a per­son who is play­ing a game that works as fol­lows. The board has three po­si­tions: red, green, and blue. The player’s ob­jec­tive is to com­plete as many clock­wise red-green-blue cy­cles as pos­si­ble, with­out ever back­track­ing in the counter-clock­wise di­rec­tion. Each turn, the game offers them a choice of one of the three spaces, and they get to choose whether or not to travel to that square or stay where they are. Clearly, their prefer­ences de­pend on where they cur­rently are: If they’re on “red”, “green” is a good move and “blue” is a bad one; but if they’re on “blue” then choos­ing “green” is ill-ad­vised.

We can con­sider a bi­nary op­er­a­tion $$?$$ which takes their cur­rent po­si­tion on the left and the pro­posed po­si­tion on the right, and re­turns the po­si­tion that the player prefers. Speci­fi­cally:

\be­gin{al­ign} & red \ ?\ red \ &= red\ & red \ ?\ green \ &= green\ & red \ ?\ blue \ &= red\ \end{al­ign} \be­gin{al­ign} & green \ ?\ red \ &= green\ & green \ ?\ green \ &= green\ & green \ ?\ blue \ &= blue\ \end{al­ign} \be­gin{al­ign} & blue \ ?\ red \ &= red\ & blue \ ?\ green \ &= blue\ & blue \ ?\ blue \ &= blue \end{al­ign}

This func­tion does not as­so­ci­ate, be­cause $$(red\ ?\ green)\ ?\ blue = blue$$ but $$red\ ?\ (green\ ?\ blue)=red.$$ To show that a func­tion is not as­so­ci­a­tive, it is suffi­cient to sim­ply do out the whole func­tion table and then find any one case that vi­o­lates the ax­iom of as­so­ci­a­tivity, as above.