Notation that sings 
[May. 9th, 200805:08 pm]
pozorvlak

Some Actual Maths for a change. Some of it assumes some mathematical sophistication, but the core idea should be accessible to anybody. Have you ever been an arts student? I'm looking at you. Skate over the words you don't know, they're not important  they're just there to explain how the central result connects to more sophisticated and deeper areas of mathematics.
Over at the Comonad.Reader, Edward Kmett's been writing about socalled "abiding" pairs of binary operations: we say that * and + abide if (a+b)*(c+d) = (a*c)+(b*d) for all a, b, c and d. The term's a portmanteau of "above and beside", and comes from the following rather lovely notation:ac = (a*b)+(c*d)

bd
ac = (a+c)*(b+d)

bd We write * by stacking things vertically, and + by putting them sidebyside: then + and * abide if we can remove the lines without introducing ambiguity. By the way, + and * don't necessarily stand for ordinary addition and multiplication  in fact, they can't, because addition and multiplication don't abide! Just think of them as two machines: you feed two things into either of them, and get one thing out of the other end. We require the things we get back to satisfy the equation above (and yes, there are examples).
Why would we want to consider such a thing? Well, suppose (A,+,0) is a monoid: then one of the conditions we need for * to be a monoid homomorphism AxA > A is that * and + abide. Generalise that example as far as you wish :)
Though neither Edward's post nor the thesis he links to say so, this notation is related to the rather beautiful EckmannHilton argument. I tried to say as much in a comment, but the proof works best in two dimensions, and his comment form strips <pre> tags. Fortunately, however, I have no such restriction here :)
Theorem (EckmannHilton): Let +, * be a pair of abiding binary operations on a set A, with units 0 and 1 respectively (so a+0 = a = 0+a and a*1 = a = 1*a for all a). Then 0 = 1, + = *, and + (and hence *) is commutative. Proof:0 = 00 = 10 = 10 = 1 = 1
  
01 01 1
xy = 1y = 1y = y = y1 = y1 = yx = 1x = 1x = x
       
x1 x1 x 1x 1x y1 y1 y QED.
You'll note that this chain of equations can be continued so that it loops round back to x+y again. If you do that, and arrange the stages in the proof in a circle, you get the "EckmannHilton clock".
This, by the way, is the kind of thing I mean when I say I do "higherdimensional algebra": some arguments naturally live in more than one dimension. In 2d we're OK, because we can draw pictures on paper, but 3d and higher rapidly gets hard to think about.
The EckmannHilton argument originally arose in algebraic topology: it's how you prove that the higher homotopy groups π_{2}, π_{3} must be commutative (the notation now has a geometric interpretation: we can literally lay out homotopies and morph them around each other as in the proof). In category theory, the argument is widespread, and it's related to the Stabilization Hypothesis (scroll down until you see the table, then read the paragraph or two above for the gist). A further example is the theorem that a monoid object in the category of monoids is a commutative monoid (because, as mentioned above, a monoid homomorphism AxA>A must abide with the binary operation on A).
I first encountered the EckmannHilton argument in Joachim Kock's excellent book Frobenius algebras and 2D topological quantum field theories, which despite the title is a great introduction to the categorical way of thinking. It's aimed at beginning graduate students, is as easy to read as a maths textbook will ever be, and comes highly recommended. It's also interesting for the way the book's structured: it uses the bottomup style currently in fashion in programming circles. The book introduces a series of "languages", each defined in terms of the previous one, which approach successively closer to the material in question. By the end of the book, we're able to replace literally pages of calculation with a few simple diagrams, and it's all perfectly rigorous. Better than that, the graphical language makes proofs extremely easy to construct. The main result of the book's pretty cute too :) 


Comments: 
2fold monoidal categories! :)
As far as the notationa nd examplke side of things go, you might enjoy this paper.
Shiny! Thanks, I'll enjoy reading that.
The notation is indeed very nice.
I'm probably missing something, because my maths is pretty rusty, but doesn't that EckmannHilton result prove that if two operations "abide" they are in fact the same operation, and therefore "abiding" is a bit of a meaningless concept?
Not quite: they're the same operation if they abide and if they both have units. Not every binary operation has a unit.
The term "abiding" isn't particularly standard, or at least I hadn't heard it before a couple of days ago. A large part of the reason is probably what you say: from discovering that two operations abide, it's usually a pretty short step to determining that they're the same operation. But there are theoretical reasons for considering that condition  homomorphisms of monoids, as I said. I haven't looked into the CS stuff that Edward Kmett talks about in his post, but presumably it includes examples of abiding nonidentical operations...
Anyway, it's a good term. Mathematics needs more whimsical terminology :)
Not quite: they're the same operation if they abide and if they both have units. Not every binary operation has a unit. Ah, that makes sense.
From: (Anonymous) 20080512 07:53 pm (UTC)
Looks a bit like the "exchange rule"...  (Link)

...for horizontal and vertical composition of natural transformations.  sigfpe
 From: pozorvlak 20080514 01:38 pm (UTC)
Re: Looks a bit like the "exchange rule"...  (Link)

Yep, and there's definitely a connection  more generally, one can do exchange in arbitrary bicategories (weak 2categories), and that's the version on Eugenia Cheng's website. I can't remember the details right now, though.
 From: pingback_bot 20110722 05:24 pm (UTC)
fixed point, homomorphism, the abide law  (Link)

 

