Associativity: Examples

Pos­i­tive examples

Addition

\((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: con­cat(“a”,con­cat(“b”,”c”)) = con­cat(con­cat(“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 xcon­cat that con­cate­nates its in­puts and puts an “x” on the front: xcon­cat(“A”, xcon­cat(“B”,”C”)) = “xAxBC”, but xcon­cat(xcon­cat(“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.

3-cycle board

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.

Parents: