Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 6, 2012

Compact Closed Bicategories

Posted by John Baez

guest post by Mike Stay

Thanks to primates’ propensity for trade and because our planet rotates, everyone is familiar with abelian groups. We can add, we’ve got a zero element, addition is commutative and associative, and we can negate any element—or, using multiplicative language: we can multiply, we’ve got a 1 element, multiplication is commutative and associative, and we can divide 1 by any element to get its inverse.

Thanks to the fact that for most practical purposes we live in 3,\mathbb{R}^3, everyone’s familiar with at least one vector space. Peano defined them formally in 1888. The collection of vector spaces is like a “categorified” abelian group: instead of being elements of a set, vector spaces are objects in a compact closed category. We can “multiply” them using the tensor product; we have the 1-dimensional vector space that plays the role of 1 up to an isomorphism called the unitor; the tensor product is associative up to an isomorphism called the associator, and is commutative up to an isomorphism called the braiding; and every object AA has a “weak inverse”, or dual, an object equipped with morphisms for “cancelling”, e A:AA *1e_A:A\otimes A^{\ast} \to 1 and i A:1A *Ai_A:1 \to A^{\ast}\otimes A and some “yanking” equations. As always in categorification, when we weaken equations to isomorphisms, we have to add new equations: a pentagon equation for the associator, triangle equations for the unitors, hexagon equations for the braiding, and braiding twice is the identity.

Thanks to the fact that everyone has family and friends, everyone is (ahem) familiar with relations. Sets, relations, and implications form a compact closed bicategory. In a compact closed bicategory, we weaken the equations above to 2-isomorphisms and add new equations: an associahedron with 14 vertices, 7-vertex prisms for the unitors, shuffle polytopes and a map of permutahedra for the braiding, and an equation governing the syllepsis. The syllepsis is what happens when we weaken the symmetry equation: braiding twice is merely isomorphic to the identity.

Sequences

We can start to see some sequences emerging from this process. The stuff below is mostly due to Chris Schommer-Pries’ definition of symmetric monoidal bicategories together with Day and Street’s definition of a compact closed Gray monoid. Their work, in turn, relies greatly on Paddy McCrudden’s Balanced coalgebroids and a handwritten note for the swallowtail coherence law. In the graphics below, I tried to make the symmetries apparent, something that was lacking from McCrudden’s presentation of the coherence laws due to the failings of the tools available for typesetting them.

Associahedra

The first pattern is the sequence of Stasheff polytopes, or associahedra. These are geometric forms that tell how to move parentheses around. There’s only one way to parenthesize one or two objects. There are two ways to parenthesize three, so we need an associator. There are five ways to parenthesize four objects, so we need a pentagonator. There are fourteen ways to parenthesize five objects, so we need a cube with three of its edges beveled.

associahedra

Unitors

The next sequence tells how to cancel the unit. When we write an equation like ab1d=abdab1d = abd, we’re going from the product of four objects to the product of three. This sequence gives us a series of prisms that connect the associahedron for the product of nn objects to the associahedron for the product of (n1).(n-1). Here are the right unitor; the left 2-unitor that connects the associator “line” to the single way of parenthesizing two objects; and the prism connecting the pentagonator for four objects to the associator for three objects.

cancelling the unit

Shuffle polytopes

Next we get ways of shuffling objects into each other. To shuffle a deck of cards, we cut it into two parts, splay the cards, and allow them to slip past our thumbs. The cards on the left hand in the same position relative to the other cards in that hand, but an arbitrary number of cards from the right hand may appear between them; by symmetry, the same is true for the cards in the right hand. The shuffle polytopes show how the ways of shuffling two lists of objects into each other are related by uses of the braiding. The smallest shuffle polytope is the braiding itself, the two ways of shuffling a single card in each hand. Next comes a triangle, the three ways of shuffling one card into two cards. After that come two polyhedra: a tetrahedron for shuffling one card into three, and a six-vertex polyhedron for shuffling two cards into two.

shuffle polytopes

The polytopes above assume that the tensor product is strictly associative; when we account for the associator, it truncates corners and bevels edges:

truncated shuffles

Permutahedra

A permutohedron tiles the space it inhabits: in one dimension, it’s the braiding, which is topologically a line segment; in two dimensions, it’s the Yang-Baxter equation, a hexagon; in three dimensions, it’s a truncated octahedron. The shuffle polytopes imply that the permutohedra commute until we get to the bicategory level. In a compact closed category, the tensor product automatically satisfies the Yang-Baxter equation—but it does so in two different ways!

yang-baxter proofs

In a compact closed bicategory, these two hexagons form the front and back face of a coherence polytope. Kapranov and Voevodsky didn’t notice this was necessary when they defined braided semistrict monoidal 2-categories; Breen noticed the omission, so I call this the “Breen polytope”. Again, when we account for associators, various vertices get truncated.

Breen polytope

Syllepsis

The syllepsis comes with a coherence law that relates the two triangle shuffle polytopes to each other; to make a symmetric monoidal bicategory rather than a merely sylleptic one, we also need a coherence law relating it to the identity.

syllepsis laws

Duals

In an abelian group, aa 1=1aa^{-1} = 1; in a compact closed category, this equation gets weakened to an adjunction, a pair of morphisms e A:AA *1e_A:A\otimes A^{\ast} \to 1 and i A:1A *Ai_A:1 \to A^{\ast}\otimes A that satisfy some “yanking” or “zigzag” equations. In a compact closed bicategory, these equations get weakened to isomorphisms and we need a “swallowtail” coherence law.

duals, yanking, and swallowtail

Other examples

Groupoids, spans, and maps of spans generalize the example of sets, relations, and implications. They give us a wonderful generalization of linear algebra; the groupoidifcation program is exploring the possibilities it offers. Alex Hoffnung has a paper where he shows that given a 2-category CC with finite products and weak pullbacks, one can form a monoidal tricategory Span(CC) of objects, spans, weak maps of spans, and maps of weak maps. If we take isomorphism classes at the highest level, we get a compact closed bicategory Span₂(CC).

There’s a deep relation between spans and profunctors. Prof, the 2-category of small categories, profunctors, and natural transformations is compact closed.

When RR is a rig category, we can form Mat(RR), the compact closed bicategory of natural numbers, matrices with elements in Ob(RR), and matrices with elements in Mor(RR).

These examples are all rather algebraic in flavor, but there are topological examples too, like the compact closed bicategory nnCob₂ of manifolds, manifolds with boundary, and manifolds with corners. (Well, it’s actually a double bicategory, but there’s a simple way of turning it into a bicategory, and that thing is compact closed.)

Monads

One can define a monad in any compact closed bicategory; the result is a category-like object.

A monad in Rel is a preorder.

If CC has finite products and pullbacks, a monad in Span(CC) is a category internal to CC.

A monad in SymMonProf is an Arrow in the sense of Hughes.

A monad in Mat(RR) is one way to get an RR-enriched category.

Traces

Simon Willerton has a great slide deck on 2-traces in compact closed bicategories. Since every object has a dual, we can take any 1-morphism f:AXBXf:A\otimes X \to B\otimes X in a compact closed bicategory and bend the output XX around backwards and feed it into the input. This brings up all kinds of fun stuff about fixed points and recursion.

My paper

The reason for this post is really to advertise my new paper. After several years of working on this paper a few hours a week, it’s finally at the point where I feel like it’s ready for comments. I intend to submit it eventually to Mathematical Structures in Computer Science. It still needs some work on tuning it to that particular audience.

In the paper I give all the examples above and lay out the complete definition of a compact closed bicategory. I prove that Span₂(CC) is compact closed and work out the canonical round 2-trace with all its associators and unitors and such. I’m sure I’ve missed some recent work; I haven’t yet read Ponto and Shulman’s paper on fixed points that I mentioned above.

Posted at June 6, 2012 1:56 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2532

10 Comments & 0 Trackbacks

Re: Compact Closed Bicategories

Congratulations Mike!

I really hope the journal prints in color!

Posted by: Alex Hoffnung on June 6, 2012 3:19 AM | Permalink | Reply to this

Re: Compact Closed Bicategories

Thanks :)

Posted by: Mike Stay on June 7, 2012 1:34 AM | Permalink | Reply to this

Re: Compact Closed Bicategories

MSCS allows authors to post a copy of a paper on the author’s website as well as in an “institutional repository” or PubMed. Does anyone know if they allow papers to be put on the arxiv?

Can anyone suggest a comparable alternative with more liberal copyright policies?

Posted by: Mike Stay on June 6, 2012 11:52 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

I don’t know if the arXiv is an “institutional repository”. Some people have put papers on the arXiv, then submitted to MCSC. But that doesn’t imply it’s allowed!

Posted by: John Baez on June 7, 2012 3:03 AM | Permalink | Reply to this

Re: Compact Closed Bicategories

This is great, and impressively detailed! A trivial comment: the URL link in reference [2] is mangled.

Have you thought at all about the coherence conditions that should be satisfied by the “vanisher”, “superposer”, and “yanker” isomorphisms for the trace-up-to-isomorphism? Kate and I only considered the special case of round traces of morphisms XXX\to X rather than more generally AXBXA\otimes X\to B\otimes X (since that’s all we needed to define secondary traces of 2-morphisms, which was what we were really interested in), and our only coherence isomorphism was a “slider” (exhibiting extraordinary pseudonaturality in XX).

Posted by: Mike Shulman on June 7, 2012 10:46 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

Have you thought at all about the coherence conditions…?

I haven’t, but now you’re making me want to. My worry is that I’ve never proved coherence theorems before, and given the example of the Breen polytope, I know it’s very easy to miss something.

Posted by: Mike Stay on June 8, 2012 5:10 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

I think that if you actually try to prove a coherence theorem, rather than just guessing some axioms that look reasonable, then you’re much less likely to miss something. (You might end up with some redundancy in your axioms, as Mac Lane famously did for monoidal categories, but that’s less worrisome.) I once heard John Power give a talk in which he explained that they proved the coherence theorem for tricategories before they had the definition of tricategory. That is, they figured out how the proof would go, and then starting from that outline they worked backwards to find out what coherence axioms would be necessary to make the proof work.

Of course, before you can try to prove a coherence theorem, you have to know or guess what the coherence theorem might say, and in this case that’s not immediately obvious to me. The closest thing I know to a coherence theorem for traced monoidal 1-categories is the original Joyal-Street-Verity result that the forgetful functor from compact closed categories to traced symmetric monoidal categories has a left biadjoint and the unit of the biadjunction is fully faithful. So one could try to categorify that by universally embedding a traced symmetric monoidal bicategory in a compact closed bicategory, and see whether the coherence axioms for a traced symmetric monoidal bicategory can be extracted from that.

(If one felt really adventurous, one could try to also do the braided/ribbon/tortile case, as JSV did. Is it known how that sort of structure interacts with the possibility of a syllepsis?)

Posted by: Mike Shulman on June 8, 2012 7:12 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

The closest thing I know to a coherence theorem for traced monoidal 1-categories is the original Joyal-Street-Verity result that the forgetful functor from compact closed categories to traced symmetric monoidal categories has a left biadjoint and the unit of the biadjunction is fully faithful.

That sounds like a very reasonable approach. I’ll think about it. Thanks!

Posted by: Mike Stay on June 9, 2012 10:48 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

This is great, and impressively detailed! A trivial comment: the URL link in reference [2] is mangled.

Thanks! I’ll fix that.

Posted by: Mike Stay on June 8, 2012 5:11 PM | Permalink | Reply to this

Re: Compact Closed Bicategories

The paper appeared on the arXiv today; I intend to submit to TAC.

Posted by: Mike Stay on January 8, 2013 2:01 AM | Permalink | Reply to this

Post a New Comment