Commutativity: Intuition

Com­mu­ta­tivity as an ar­ti­fact of notation

In­stead of think­ing of a com­mu­ta­tive func­tion \(f(x, y)\) as a func­tion that takes an or­dered pair of in­puts, we can think of \(f\) as a func­tion that takes an un­ordered bag of in­puts, and there­fore can’t de­pend on their or­der. On this in­ter­pre­ta­tion, the fact that func­tions are always given in­puts in a par­tic­u­lar or­der is an ar­ti­fact of our defi­ni­tions, not a fun­da­men­tal prop­erty of func­tions them­selves. If we had no­ta­tion for func­tions ap­plied to ar­gu­ments in no par­tic­u­lar or­der, then com­mu­ta­tive func­tions would be the norm, and non-com­mu­ta­tive func­tions would re­quire ad­di­tional struc­ture im­posed on their in­puts.

In a world of lin­ear left-to-right no­ta­tion, where \(f(x, y)\) means “$f$ ap­plied to \(x\) first and \(y\) sec­ond”, com­mu­ta­tivity looks like a con­straint. In an al­ter­na­tive world where func­tions are ap­plied to their in­puts in par­allel, with none of them dis­t­in­guished as “first” by de­fault, com­mu­ta­tivity is the nat­u­ral state of af­fairs.

Com­mu­ta­tivity as sym­me­try in the output

Com­mu­ta­tivity can be seen as a form of sym­me­try in the out­put of a bi­nary func­tion. Imag­ine a bi­nary func­tion as a phys­i­cal mechanism of wheels and gears, that takes two in­puts in along con­veyer belts (one on the left, one on the right), ma­nipu­lates those in­puts (us­ing me­chan­i­cal sen­sors and ma­nipu­la­tors and tools), and pro­duces a re­sult that is placed on an out­go­ing con­veyer belt.

The out­put of a com­mu­ta­tive func­tion is sym­met­ric in the way it re­lates to the in­puts. Con­sider a func­tion that takes two wooden blocks and glues them to­gether. The func­tion might ma­nipu­late them in a sym­met­ric fash­ion (if both blocks are picked up si­mul­ta­neously, and have glue ap­plied si­mul­ta­neously, and are pushed to­gether si­mul­ta­neously), but the out­put is not sym­met­ric: If a red block comes in on the left and a blue block comes in on the right, then the re­sult­ing block is red on the left and blue on the right, and the func­tion is not com­mu­ta­tive (though it is as­so­ci­a­tive).

By con­trast, a func­tion that mixes the red and blue to­gether — pro­duc­ing, for ex­am­ple, the uniform color pur­ple or the un­ordered set \(\{b, d, e, l, u, r\}\) — would be com­mu­ta­tive, be­cause the way that the out­put re­lates to each in­put is in­de­pen­dent of which side the in­put came in on.

A func­tion is prob­a­bly com­mu­ta­tive if you can vi­su­al­ize the out­put it­self as left/​right sym­met­ric, even if the left in­put was very differ­ent from the right in­put. For ex­am­ple, we can use the fol­low­ing vi­su­al­iza­tion to show that mul­ti­pli­ca­tion is com­mu­ta­tive. Imag­ine a func­tion that takes in two stacks of poker chips, one on the left con­veyer belt and one on the right con­veyer belt. The func­tion has a square of wet plas­ter in the mid­dle. On each con­veyer belt, an arm re­moves chips from the stack of poker chips un­til the stack only has one chip left, and for each chip that is re­moved, a per­pen­dicu­lar cut is put in the plas­ter (as in the di­a­gram be­low). The plas­ter is then al­lowed to set, and the plas­ter pieces are then shaken out into a big bag. A third arm re­moves plas­ter pieces from the bag one at a time, and adds a poker chip to the out­go­ing con­veyer belt for each one. To vi­su­al­ize this, see the di­a­gram be­low:

Why multiplication commutes

If the in­put con­veyer belts had 4 and 6 poker chips on them (re­spec­tively), then the out­put belt will have 24 chips on it (be­cause 24 differ­ent chunks of plas­ter will have fallen into the bag), but the chips don’t nec­es­sar­ily come from any one par­tic­u­lar side: The out­put re­lates to each in­put in a man­ner that doesn’t de­pend on which side they came in.

knows-req­ui­site(Math 2): In math­e­mat­ics, a sym­me­try is some struc­ture on a set that is pre­served un­der some trans­for­ma­tion of that set. In our case, the struc­ture is the value of the out­put, which is pre­served un­der the trans­for­ma­tion of chang­ing which side the in­puts come in on. For­mally, let \(X^2\) be the set of all pairs of two val­ues from the set \(X;\) each point in \(X^2\) is a pair \((x_1, x_2).\) \(X^2\) can be vi­su­al­ized as an \(|X|\) by \(|X|\) grid. Con­sider a func­tion \(f : X^2 \to Y\) as a struc­ture on \(X^2\) that as­signs a value \(f(x_1, x_2)\) to each point \((x_1, x_2);\) this can be vi­su­al­ized as a ter­rain atop \(X^2\) in­duced by \(f\). Con­sider the trans­for­ma­tion \(\operatorname{swap} : X^2 \to X^2\) that maps \((x_1, x_2)\) to \((x_2, x_1),\) and the set \(\operatorname{swap}(X^2)\) gen­er­ated by ap­ply­ing \(\operatorname{swap}\) to all points in \(X^2\). This can be vi­su­al­ized as re­flect­ing \(X^2\) along a di­ag­o­nal.\(f\) also in­duces a struc­ture on \(\operatorname{swap}(X^2).\) If the struc­ture of \(f\) on \(X^2\) is iden­ti­cal to the struc­ture of \(f\) on \(\operatorname{swap}(X^2),\) then \(f\) is a sym­me­try of \(X^2\) un­der the trans­for­ma­tion \(\operatorname{swap}\). This oc­curs ex­actly when \(f(x_1, x_2)=f(x_2, x_1)\) for all \((x_1, x_2)\) pairs, which is the for­mal defi­ni­tion of com­mu­ta­tivity.