The shuffle trick, or how to eliminate commutativity and associativity, for the benefit of better self-multiplication

 On a set with an operation which has a neutral element, there is an algebraic axiom which is equivalent with both associativity and commutativity of the operation. I call it the shuffle (does it have a name?).
It is this one:

 

(ab)(cd) = (ac)(bd)

 

so the middle terms b and c switch their position.

Of course, by duality, that means that there is an axiom which is equivalent with both co-associativity and co-commutativity, in an algebra with co-unit.

This is a justification for the existence of TWO fanout nodes in chemlambda, called FO and FOE. The graphical representation of the shuffle, called now the shuffle trick, is simply a combination of two graph rewrites, as shown in the demo on the shuffle trick.
On this blog the shuffle trick is mentioned several times, and the “shuffle move” is proposed as various compositions of moves from graphic lambda calculus.
But the CO-COMM and CO-ASSOC moves from graphic lambda calculus are no longer needed, being replaced by FO-FOE and FI-FOE (aka fan-in) moves. This is good because the graph rewrites which express the associativity and commutativity are too symmetric, they don’t have a natural direction of application, therefore any choice of a preferred direction would be artificial.
The shuffle trick is essential for self-multiplication, where there has to be a way to multiply trees made by FO nodes, in such a way so that the leaves of the copies of the tree are not entangled, see this demo.
________________________________________________
Advertisements

2 thoughts on “The shuffle trick, or how to eliminate commutativity and associativity, for the benefit of better self-multiplication”

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