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.

March 30, 2010

Extraordinary 2-Multicategories

Posted by Mike Shulman

Let’s take a break from all this type theory and \infty-stuff and do some good old 2-dimensional category theory. Although as usual, I want to convince you that plain old 2-categories aren’t good enough, and we need something different. But as far as I know, the structure I have in mind today doesn’t exist yet! I think I know how to define it, but before I go to the trouble, I want to know what people think about it, and whether anyone has seen anything like it before. So I’ll just describe informally what I think this structure should look like.

Briefly, what I want is a “minimal” extension of a 2-category which can also include extraordinary natural transformations.

So what are extraordinary natural transformations (a.k.a. “extranatural” transformations)? The nlab page about them is fairly nice, and John also wrote a comment here about why you might want them. Namely, if VV is a closed monoidal category, then its internal-hom is a functor [,]:V op×VV[-,-]\colon V^{op}\times V \to V, and it comes with “evaluation” [X,Y]XY [X,Y] \otimes X \to Y and “coevaluation” Y[X,YX] Y \to [X, Y\otimes X] maps that look like the counit and unit of an adjunction. These are natural in YY, and for fixed XX they are the unit and counit of an adjunction, but we’d like to say that they’re “natural in XX” as well. That doesn’t make sense for the usual kind of “natural,” since XX appears only on one side of each, but since it appears on that one side twice, once covariantly and once contravariantly, we can define a similar “bent” sort of naturality that does apply. The formal definition can be found here.

Unfortunately, these sorts of transformations aren’t 2-cells in the 2-category CatCat, but there must be some kind of 2-category-like structure in which they live. One answer to the question of where they live is a compact closed proarrow equipment. This approach begins by noticing that if f,g:ABf,g\colon A\to B are two covariant functors, then an ordinary natural transformation from ff to gg can equivalently be defined as a map of profunctors hom Ahom B(f,g)hom_A \to hom_B(f,g), where hom A:A op×ASethom_A\colon A^{op}\times A\to Set is just the hom-functor of AA, and hom B(f,g):A op×ASethom_B(f,g)\colon A^{op}\times A\to Set is defined by hom B(f,g)(x,y)=B(f(x),g(y))hom_B(f,g)(x,y) = B(f(x),g(y)). Similarly, if we have a functor f:A×C op×CBf\colon A\times C^{op}\times C\to B and a functor g:ABg\colon A\to B, then a transformation fgf\to g which is natural in AA and extranatural in CC can be equivalently defined as to be a map of profunctors hom A×CHhom_{A\times C} \to H, where H:A op×C op×A×CSetH\colon A^{op}\times C^{op}\times A\times C\to Set is the profunctor defined by H(a 1,c 1,a 2,c 2)=B(f(a 1,c 2,c 1),g(a 2)). H(a_1,c_1,a_2,c_2) = B(f(a_1,c_2,c_1),g(a_2)). Thus, if we have a formal notion of “proarrow” for which we can make sense of these constructions, we can define extranatural transformations there.

I’m not going to say any more about that, though, because what I want is something different. Not to say anything against profunctors; as you all know, I love profunctors, and they are useful for all sorts of other things, so this approach puts extranatural transformations into a nice general situation with a nice general calculus. However, if all we want to talk about are extranatural transformations, then going to profunctors introduces a lot of extra baggage, which might not always be present in examples. So I want a structure which generalizes a 2-category just enough to include extranatural transformations.

First, since extranaturality depends on having functors of many variables, it makes sense to use some sort of multicategory. Recall that a multicategory includes morphisms whose domain is a finite list of objects, rather than just a single object, which we write like so: f:(A 1,,A n)B. f\colon (A_1,\dots,A_n) \to B. Our multicategories should probably be symmetric, meaning that given any such ff we can permute the objects in its domain and get another morphism with that permuted domain. Moreover, our multicategories should be CatCat-enriched, (i.e. they are “2-multicategories”) so that in addition to having such morphisms, we have 2-cells α:fg\alpha\colon f\to g between two such morphisms f,g:(A 1,,A n)Bf,g\colon (A_1,\dots,A_n) \to B. Note that this naive CatCat-enrichment only gives us 2-cells between morphisms with the same domain and codomain, which are thus still only “ordinary” natural transformations, although they are now explicitly “natural in many variables.”

Now we can add contravariance, by allowing some of the objects in the domain of a morphism to be decorated with an “op”. For instance, we could have a morphism such as f:(A,B op,C)Df\colon (A,B^{op},C) \to D. Composition of such morphisms requires “distributing” contravariance. For example, given such an ff, if we also have g:(X)Ag\colon (X)\to A, h:(Y op,Z)Bh\colon (Y^{op},Z) \to B, and k:(W,V op)Ck\colon (W,V^{op})\to C, then we can form the composite f(g,h op,k):(X,Y,Z op,W,V op)Df\circ (g,h^{op},k)\colon (X,Y,Z^{op},W,V^{op}) \to D. This is just like the usual composition in a multicategory, except that since BB is “opped” in the domain of ff, when we plug hh into ff we have to distribute the “op” over all the objects in the domain of hh, turning (Y op,Z)(Y^{op},Z) into (Y,Z op)(Y,Z^{op}). Moreover, when we extend this to the CatCat-enrichment by defining the horizontal composite of 2-cells, we have to reverse the direction of any 2-cells whose target is “opped.” For instance, if in the above situation we had another h:(Y op,Z)Bh'\colon (Y^{op},Z)\to B and a 2-cell α:hh\alpha\colon h\to h', then upon composition with ff we would get a 2-cell in the opposite direction f(g,(h) op,k)f(g,h op,k)f\circ (g,(h')^{op},k) \to f\circ (g,h^{op},k).

So far, so good, but now what about the extranaturals themselves? These have to be 2-cells between arrows whose domains don’t match up. Or, more precisely, between arrows whose domains aren’t the same, since we do still have to “match up” their domains in some way. Specifically, for an “extranatural 2-cell” from ff to gg, each object has to occur either (1) once each in the domains of both ff and gg with the same variance, (2) exactly twice in the domain of ff, once covariantly and once contravariantly, or (3) exactly twice in the domain of gg, once covariantly and once contravariantly. In fact, we actually need to specify how the objects in the domains are matched up, since if some of them are the same, there might be different ways to do it. For instance, given functors f:A×A op×ABf\colon A\times A^{op}\times A\to B and g:ABg\colon A\to B, there are two kinds of extranatural transformation fgf\to g; one has components f(a 1,a 2,a 2)g(a 1)f(a_1,a_2,a_2)\to g(a_1) and is natural in a 1a_1 and extranatural in a 2a_2, while the other has components f(a 1,a 1,a 2)g(a 2)f(a_1,a_1,a_2)\to g(a_2) and is natural in a 2a_2 and extranatural in a 1a_1.

Thus, every “extranatural 2-cell” in our multicategory should come with a “matching” which identifies where the naturality and extranaturality occurs. It’s convenient to draw this matching as a sort of graph. For instance, given f:(A,B,A op,C op)Xf\colon (A,B,A^{op},C^{op}) \to X and g:(C op,B,D op,D)Xg\colon (C^{op},B,D^{op},D) \to X, the graph representing one kind of extranatural 2-cell would look like this:

Layer 1 A B A C C B D D op op op op

This graph stipulates that the two copies of AA in the domain of ff are matched extranaturally, as are the two copies of DD in the domain of gg, while BB and C opC^{op} are matched naturally between the two functors. So our “extraordinary multicategory” will come with a collection of “extranatural 2-cells” between morphisms with possibly-different domains, but each such 2-cell fgf\to g also comes with a graph which matches up the objects in the domains of ff and gg in some way. Note that this includes ordinary 2-cells as well: these are just the extranatural ones whose graph is just a series of straight lines.

Now we have to say how to compose such 2-cells. Fortunately, most of the work has been done for us in the original paper that defined extranatural transformations, A generalization of the functorial calculus by Eilenberg and Kelly. There they showed that two extranatural transformations α:fg\alpha\colon f\to g and β:gh\beta\colon g\to h are composable precisely when, if you paste the graph labeling α\alpha on top of the graph labeling β\beta, you don’t get any closed loops. Moreover, in this case, the resulting transformation βα\beta\circ \alpha is labeled by this composite graph. (If there is a closed loop, then there is a category appearing in the domain of gg but not in the domains of ff or hh, and the “composite” will not be well-defined; it depends on the choice of an object of that category to “compose along”.)

Thus, this tells us exactly how to define “vertical” composition of 2-cells in our multicategory. It’s important to note that just as for extranatural transformations, not every pair of 2-cells with matching source and target will be composable. Finally, the “horizontal” composition should be definable using substitution of graphs; for now I’ll leave that as an exercise.

Let’s call this hypothetical thing an extraordinary 2-multicategory. As far as I know, no one has written down such a thing before, but I would be very glad to find myself wrong. I’m also curious about people’s reaction to such a thing. Does it seem natural or unnatural? Beautiful or ugly? Can it be improved?

The closest thing I know of in the literature is Max Kelly’s theory of clubs. A “club” is a structure kind of like an operad, which can be viewed as a concrete presentation of a monad on CatCat; thus coherence theorems about the algebras for that monad can be stated as theorems about the club. In fact, there are lots of kinds of clubs, and Kelly gave multiple related but not quite equivalent definitions—but one of his definitions is that a club is precisely a generalized operad (in the Leinster-Burroni sense) relative to some cartesian monad on CatCat.

The monad parametrizes the “arities” of operations as well as the allowable sorts of “transformations” between operations. If we take the “free symmetric (strict) monoidal category monad,” then clubs over this monad describe structure on categories involving only covariant operations, and natural transformations which can permute variables, but nothing else. The ur-example is, of course, the club for symmetric monoidal categories. Such clubs are almost the same as CatCat-enriched symmetric multicategories, so you can think of “the club for symmetric monoidal categories” as almost the same as the free CatCat-enriched symmetric multicategory containing a symmetric-monoidal-category object.

Kelly also considered other types of clubs which allow transformations with duplicated variables, but still with only covariant functors, such as the diagonal XX×XX\to X\times X which appears in the notion of “category with finite products.” He also wanted a version which would describe extranatural transformations, but as far as I can tell, he eventually gave up on this, after realizing that the monad for compact closed categories (which would be describable by such a club, if it existed) is not cartesian, and thus could not be presentable by any such generalized operad in CatCat.

I believe there should, however, be a “free extraordinary 2-multicategory containing a compact-closed-category-object,” so that extraordinary 2-multicategories could be used to present 2-theories involving contravariance and extranatural transformations. The reason I think this should work, though Kelly’s approach failed, is the important point I noted above: in an extraordinary 2-multicategory, 2-cells of incompatible graphs cannot be composed, whereas in any sort of club as defined by Kelly, any pair of 2-cells with matching source-target must always be composable. This change does mean that an extraordinary 2-multicategory can no longer be described entirely in CatCat, though I think we can describe it in a similar way if we use “partial categories” in which not all composites may exist. That also means it’s not clear whether it can give rise to a monad on CatCat, so I’m not sure whether this does anything to solve the actual problem Kelly was trying to address. But regardless, I think the structure should be of interest. Thoughts?

Posted at March 30, 2010 8:46 PM UTC

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

43 Comments & 1 Trackback

Re: Extraordinary 2-Multicategories

I’ve certainly been thinking about such things recently (such as this week!) – mainly motivated by Hopf monads. So the picture in my last post

A surface diagram

is supposed to represent the composition of two extraordinary natural (or dinatural) transformations – you can see the graph as the profile on the right-hand side and the colour blue is supposed to represent the opposite category.

[A very brief explanation of what is going on is as follows. The red line represents a functor T:CCT:C\to C, the black line separating the blue and white regions represents a duality functor ˇ:C opC\check{ }:C^{op}\to C, and the thick black line represents the triple tensor product C×C×CCC\times C\times C\to C (I’m cheating and using coherence here). So the diagram is supposed to represent a transformation from TTˇT op:C opCT\circ T\circ\check{}\circ T^{op}:C^op\to C at the bottom to ˇ:C opC\check{}:C^op\to C at the top.]

I suspect John will have something to say about this…

Posted by: Simon Willerton on March 31, 2010 12:56 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Yes, I should have mentioned that the string diagrams used to notate extranatural transformations are a “shadow” of a fragment of the surface diagrams that describe the compact closed bicategory of profunctors.

Sorry, though, I’m having trouble decoding that surface diagram, probably partly because of the lack of true 3D, but also because I don’t have much experience with surface diagrams. It looks kind of like one of those “impossible solids” to me. What does it mean that the thicker vertical line stops abruptly partway down?

Posted by: Mike Shulman on March 31, 2010 6:27 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

It looks to me like the thick vertical black line in the middle of the diagram shouldn’t be there at all. Rather there should be a dashed line or something that represents the continuation of the lower curled edge which is obscured from view by the surface. This curled edge (which we can’t see) is what should join up and form a cusp point with the curled edge which we can see. No?

That is, unless this surface represents something drastically different from what I imagining….

Posted by: Chris Schommer-Pries on March 31, 2010 7:03 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Chris said

It looks to me like the thick vertical black line in the middle of the diagram shouldn’t be there at all.

Well it all depends on your conventions! I tried various things. I decided that functors should be marked on the surface (though they should probably be labeled). In the first half of my Hopf monad paper I drew in all of the hidden lines but stopped after a certain point if it was reasonably clear what was going on because the pictures were getting cluttered.

I’m rather hoisted by my own petard here in the sense that I included that diagram as an example of the kind of complicated diagram that I needed, so it isn’t the easiest kind of diagram to understand straight off the bat – it comes towards the end of the paper.

Anyway, let me try to explain what is going on in the picture by using some diagrams from my paper.

First if we have a category with a duality :C opC{}^\vee:C^{op}\to C then you have the extranatural transformation idev: 3(id id)idid\otimes ev: {\otimes_3}\circ(id \otimes {}^\vee \otimes id)\Rightarrow id so for objects XX and YY of CC we have idev:XY YXid\otimes ev : X\otimes Y^\vee \otimes Y\to X; xfyxf(y)x\otimes f \otimes y\mapsto x\cdot f(y). Using my conventions that functors go from right to left, tensors go from front to back and transformations go from bottom to top, I draw this as

Identity tensor evaluation

We also have coevid:id 3(id id)coev\otimes id: id \Rightarrow{\otimes_3}\circ(id \otimes {}^\vee \otimes id) which I draw as

Identity tensor evaluation

The fact that evaluation and coevaluation are adjoint is then expressed by two equations, one of which is the following which says that composing the above two extranatural transformations should give the identity natural transformation.

Identity tensor evaluation

Where I’ve drawn this without the hidden lines.

Hopefully that should give you a better idea of what’s happening in the part you cannot see in my original picture above!

Posted by: Simon Willerton on April 1, 2010 8:20 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Oh, I get it. I think it would be a little clearer to me if you used boxes to denote the evaluation and coevaluation transformations, so that it’s clear that something is happening there.

Using my conventions that functors go from right to left, tensors go from front to back and transformations go from bottom to top

Can you say anything about why you use that convention? It’s counterintuitive for me, having been taught since kindergarten to write from left to right and from top to bottom.

Posted by: Mike Shulman on April 1, 2010 11:39 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Ahh, okay. I see. Your surfaces are immersed and this is a sort of singularity. Thanks for clarifying. (I’m really impressed by your diagrams, by the way).

“Using my conventions that functors go from right to left, tensors go from front to back and transformations go from bottom to top”


This seems to me like a good convention for many diagrams. Whenever I am on top of things and giving a talk I try to stick to this convention. The reason it is good is that when you compose diagrams, with say the one on the left labeled by F and the one on the right labeled by G, you get the composite FG. This is the convention which is consistent with the usual way of writing function composition.

If only we didn’t write function composition in a backwards-headed fashion, then we could stick to the good old kindergarten convention.


Posted by: Chris Schommer-Pries on April 2, 2010 2:44 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

If only we didn’t write function composition in a backwards-headed fashion, then we could stick to the good old kindergarten convention.

I guess I can see that, but I find it much less confusing to stick to the kindergarten convention for diagrams and instead write function composition in the corresponding diagrammatic order if necessary.

Does your argument provide a reason for the bottom-to-top ordering of transformations?

Posted by: Mike Shulman on April 2, 2010 4:21 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Does your argument provide a reason for the bottom-to-top ordering of transformations?

That's conventional from spacetime diagrams in physics. I don't know if that's Simon's reason, but since I predicted his reason for the left-right convention before I read his explanation, I'll predict this one too. (^_^)

Posted by: Toby Bartels on April 2, 2010 8:17 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

which in turn derives from our or Descartes? drawing the positive x-axis to the right and the positive y-axis to the top. I seem to recall physicists have x for space and y=t for time, as opposed to the time dependent version of motion.

Posted by: jim stasheff on April 3, 2010 5:22 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Chris and Toby got it spot on! Like many conventions, these conventions have their advantages and disadvantages.

The right to left convention is to agree with standard composition conventions. It’s one of those things where you just have to pick some convention – I think Ieke Moerdijk favours this convention (at least in the sense that he draws arrows from right to left) as does John Baez. The main problem I’ve found with it is actually drawing on the board in a seminar – it’s odd to work from that direction. As an undergraduate in Cambridge I seem to remember that in exams the algebraists would state explicitly whether composition was written on the right or the left.

The bottom to top convention is based on the time-goes-upwards convention. My first coauthored paper was about braids and we seemed to spend an inordinate amount of time arguing whether the braids should be oriented upwards or downwards. Then we realised that we didn’t actually need the braids to be oriented! We could happily agree that aba b became aa on top of bb (or vice versa) without having to saying whether aba b meant ‘aa then bb’ or ‘bb then aa’.

Posted by: Simon Willerton on April 9, 2010 8:41 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

The top to bottom issue is very relevant for trees.
Having started at the top of the page, it’s natural to compose rooted trees by root to leaf working on down
although for coalgebras up-rooted (pun intended) trees are useful.

Posted by: jim stasheff on April 3, 2010 12:36 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

In almost all actual trees, the root is at the bottom and the leaves are at the top.

Posted by: Toby Bartels on April 3, 2010 9:52 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Of course, we can also use surface diagrams to represent 2-cells in an extraordinary 2-multicategory, just as we would in a compact closed bicategory. (In fact, the relationship “extraordinary 2-multicategory : compact closed proarrow equipment” is very similar to that of “multicategory : monoidal category,” although not quite the same.) Here’s how I would draw a 2-cell m:fgm\colon f\to g with the graph pictured in the main entry, where f:(A,B,A op,C op)Xf\colon (A,B,A^{op},C^{op}) \to X and g:(C op,B,D op,D)Xg\colon (C^{op},B,D^{op},D)\to X are morphisms and AA, BB, CC, DD, and XX are objects.

picture of extranatural 2-cell

My first experiment with Blender! I managed to get the shrinkwrap modifier to do what I thought it would when I suggested it, although I’m not entirely sure that’s what you were asking for.

Posted by: Mike Shulman on April 1, 2010 2:46 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Great stuff! Can you let me have a copy of your .blend file to play with?

I can see you’re having similar problems to those that I had – like smoothing out a surface causes the corners to be smoothed off – and all of the action isn’t quite going on inside the mm box.

In terms of the shrinkwrap I was more interested in drawing curves on than on putting labels on, but I will have wanted to put labels on as well.

Your picture brings up a question that I meant to ask before: is there any reason you want to impose symmetry? Obvious answers include: because that’s what all my examples are; and because that seems like a simpler first case. From the 3d diagram point of view the symmetry isn’t so natural – we really need 5d diagrams. My motivation was Bruguières and Virelizier’s Hopf monads paper and they worked in the unsymmetric setting.

Posted by: Simon Willerton on April 1, 2010 7:23 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

smoothing out a surface causes the corners to be smoothed off

I just discovered that this can be fixed with edge creasing. In Edit mode, make sure the 3D cursor is nearby, select the two edges adjoining the corner that is undesireably smoothed off, and press Shift-E (or Mesh > Edges > Crease Subsurf). Then move the mouse away from the 3D cursor until the corner is sufficiently pointy again. I’m not going to post yet another picture, but this seems to basically fix the problem; so I think mesh+subsurf+edge creasing is probably the best way to go.

Posted by: Mike Shulman on April 5, 2010 3:59 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Here’s the .blend file for the picture I included above.

smoothing out a surface causes the corners to be smoothed off

Yes, the subsurf modifier seems to do this. Here’s a version where the meshes have a couple extra manual subdivisions, but with subsurf off:

picture with no subsurf

You can see that the corners are square, but the surfaces aren’t as smooth.

Another option is to use NURBS surfaces instead of meshes. I started out making these surfaces as NURBS, but then I converted them to meshes because the shrinkwrap modifier only works on meshes. But if you don’t want labels, or you can get the labels some other way, then you can just leave them as NURBS surfaces, which are nice and smooth and can still have sharp corners, like this:

picture with NURBS

Here’s the .blend file with NURBS surfaces.

and all of the action isn’t quite going on inside the mm box.

Yes, that’s an issue too. Presumably this could be fixed with some work, especially with the meshes where you can just drag around the vertices.

In terms of the shrinkwrap I was more interested in drawing curves on than on putting labels on

I’m pretty sure it should work for curves too, but I don’t have an example to play around with myself yet.

is there any reason you want to impose symmetry? Obvious answers include: because that’s what all my examples are; and because that seems like a simpler first case.

I think it’s where all my examples are. I don’t know of any non-symmetric situation in which “op” and extranaturals nevertheless make sense. For instance, in order for VV-categories to have opposites, you need VV to at least be braided, but if it’s braided and not symmetric then opposites behave pretty weird (e.g. you have “left opposites” and “right opposites” which aren’t the same), so I’m not sure whether you have extranaturals that behave the way I would expect them to. But maybe you have an example that is not symmetric?

I think symmetry is perfectly natural from the surface diagram point of view, if you don’t mind having surfaces pass through each other. (-: You can certainly think of them as living in high codimension, but I’m happy to think of them as merely immersed in 3-space.

Posted by: Mike Shulman on April 1, 2010 10:55 PM | Permalink | PGP Sig | Reply to this

Re: Extraordinary 2-Multicategories

The non-subsurfed-mesh version looks noticeably better if you remember to “Set smooth” on:

Extranatural transformation with no subsurf but smooth on

Posted by: Mike Shulman on April 2, 2010 11:06 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Way back when, Witten described string interaction
by having three strips (world sheets) abut to a (symmetric) Y. Btw, he had rediscovered the Lashof partial but associative composition on the space of maps Map (I, X).

To do Witten’s interaction geometrically back then, think of the strips as creased down the middle - paper models can easily be constructed. But these recent surface renderings are the first I’ve seen where only the vertex need be singular.

Posted by: jim stasheff on April 3, 2010 12:42 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

My motivation was Bruguières and Virelizier’s Hopf monads paper and they worked in the unsymmetric setting.

I think we may be using “symmetric” to mean different things. As far as I can tell from a quick glance at their paper and yours, both are in what I would call a symmetric setting, namely CatCat, which is a symmetric monoidal proarrow equipment or a symmetric extraordinary 2-multicategory. The monoidal categories involved (objects of CatCat) have non-symmetric monoidal structures, but there is no problem defining a non-symmetric pseudomonoid object in a symmetric monoidal 2-category.

Posted by: Mike Shulman on April 1, 2010 11:37 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

I looked at something similar to clubs in my thesis, though coming at it from a term rewriting angle. The thesis is here.

It’s been a while since I thought about these things, but page 15 describes connections with clubs and with some proof-theoretic/rewriting structures too.

Posted by: Jonathan Cohen on March 31, 2010 1:48 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

I think Paul-André Melliés and I had better quickly finish up our paper on Theories with duality before Mike and Simon completely finish off the task of incorporating extraordinary natural transformations into a kind of generalization of 2-category theory. We’ve been working on this for 3 years now.

Take a look, guys — we’re all thinking about the same stuff! This latest draft was heavily influenced by Mike’s post on double-categorical approach to proarrow equipments, but Paul-André had been very fond of proarrow equipments even before I saw Mike’s post on those.

Posted by: John Baez on April 1, 2010 6:00 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Indeed we are! But in slightly different ways, since you’re taking the profunctor tack I mentioned briefly. I presume from the title of your paper that you’re aiming at a presentation of “theories” such as the theory of compact-closed-categories or closed-monoidal-categories which Kelly was unable to do with clubs, and which I mentioned above as a possible use of “extraordinary 2-multicategories.” But I didn’t see anything in the draft you linked to about the theories themselves. Are you planning to describe “the free compact-closed proarrow-equipment containing a closed-monoidal-category object?” (Or have you done so already but not written it down in the draft?) If so, it would be interesting to compare that to the corresponding extraordinary 2-multicategory, once all the definitions are in place.

This reminds me that at some point someone should also throw in a background reference to Street’s paper “Functorial calculus in monoidal bicategories,” in case there is someone out there who hasn’t read it. He works with only the bicategory of profunctors, identifying functors with representable profunctors, but he’s using the same idea for how to describe extranaturals. He even has some nice surface diagrams.

Posted by: Mike Shulman on April 1, 2010 6:46 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Mike wrote:

But I didn’t see anything in the draft you linked to about the theories themselves.

True. Indeed, calling it a ‘draft’ is a bit overoptimistic; it’s just a draft of the introduction. There’s a lot more we need to write up.

Are you planning to describe “the free compact-closed proarrow-equipment containing a closed-monoidal-category object?”

Yes. Let me call that ‘the theory of closed monoidal categories’, for short. We’re planning to describe a sample of things like that, perhaps also including ‘the theory of cartesian closed categories’ and ‘the theory of compact closed categories’. We’ve worked some of these out…

This reminds me that at some point someone should also throw in a background reference to Street’s paper “Functorial calculus in monoidal bicategories.”

Indeed! Paul-André was influenced by this paper. I just hadn’t gotten around to putting in a reference.

Posted by: John Baez on April 1, 2010 3:28 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

We’ve worked some of these out…

I look forward to seeing them! At what level of strictness does their universal property live?

Posted by: Mike Shulman on April 1, 2010 6:30 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Could you envisage ever allowing closed loops to appear under composition? Of course you’d need lots of extra structure, such as some kind of dimension on the relevant category, as with fusion categories.

Posted by: David Corfield on April 1, 2010 12:27 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

This is the most subtle and fascinating part of the whole business! You can certainly envision allowing closed loops. And you don’t need any extra structure on the categories appearing in the source and target of the functors between which the extranatural transformations go. It’s just that what you get, when you compose graphs that produce a closed loop, is no longer an extranatural transformation. Or, rather, what you get is not a single extranatural transformation, but a whole family of them.

For example, suppose we have functors f:AXf\colon A \to X, g:(A,B,B op)Xg\colon (A,B,B^{op}) \to X, and h:AXh:A\to X, and extranaturals α:fg\alpha\colon f\to g and β:gh\beta\colon g\to h having the only possible graphs. That means α\alpha has components α a,b:f(a)g(a,b,b)\alpha_{a,b} \colon f(a) \to g(a,b,b) and β\beta has components β a,b:g(a,b,b)h(a)\beta_{a,b}\colon g(a,b,b) \to h(a). Now say we want to compose βα\beta\circ \alpha to get something going from ff to hh, which should have components of the form “(βα) a:f(a)g(a)(\beta\circ\alpha)_a \colon f(a) \to g(a).” Of course to get this, we want to compose a component of α\alpha with a component of β\beta, but in order to have such components, we need to pick a particular object bb to “compose along.” For any fixed bb, the family of composites f(a)g(a,b,b)h(a)f(a) \to g(a,b,b) \to h(a) are natural in aa, but if we pick different objects bb, these composites are different; so we have a family of natural transformations fhf\to h indexed by the objects of BB.

Now you might think, that’s not so bad; we’ll just generalize our notion of extranatural transformation to allow graphs which also contain disconnected loops, with each loop labeled by some category, and define an extranatural transformation labeled by that graph to consist of a family of plain extranaturals labeled by the loop-free part of the graph, indexed by a selection of one object from each of the categories labeling the loops. But then you start trying to make that precise, and you realize that the Eckmann-Hilton argument is hiding in the details!

Suppose to start with that each graph GG contains a loop-free part G lfG_{lf} and an (ordered) list G loopG_{loop} of loops. Now when we compose two graphs GG and HH, the loops in GHG\circ H will consist of the loops in GG, the loops in HH, and any new loops created by the composition of the loop-free parts. How do we put those in order to make a list of loops (GH) loop(G\circ H)_{loop}? We have to make a choice about how to order these three parts, and it seems to be impossible to make that choice in such a way so that composition of graphs is associative.

On the other hand, instead of an ordered list of loops labeled by categories, we can let G loopG_{loop} be an element of the free commutative monoid generated by loops labeled by categories, removing any need to put things in order. This gives us a category (which is, in fact, the free compact-closed category generated by the labels), but now it’s not clear how to work with extranaturals labeled by such graphs. For instance, if GG contains two loops labeled by the category BB, then an extranatural labeled by GG should consist of a family of extranaturals indexed by a pair of objects of BB—but since the two occurrences of BB don’t come in any order, I can’t decide which labeling object bBb\in B goes with which one. This isn’t a problem for defining the extranaturals, since we can make some arbitrary choice of ordering, but it is a problem when we try to compose them.

Now to a higher category theorist, it may be obvious what’s going on here: lack of associativity, the Eckmann-Hilton argument making things too commutative—clearly graphs should actually form a bicategory. And that’s exactly what the profunctor approach does. Instead of transformations labeled by graphs, we use transformations labeled by profunctors. Any loop-free graph gives a uniquely defined profunctor built from hom-profunctors, and composites of “compatible” (i.e. non-loop-producing) graphs correspond to the composites of these profunctors (up to isomorphism). But composition of profunctors is always defined, and associative up to coherent isomorphism.

However, as I said above, there are also lots of profunctors that don’t correspond to any sort of graph, and thus lots of “transformations” appearing in this world that don’t look much like the extranaturals we’re used to. What I was trying to do with “extraordinary 2-multicategories” is keep things as simple as possible and only describe the “familiar” extranaturals, with the structure that actually exists on them (such as a composition that’s only partially defined).

Posted by: Mike Shulman on April 1, 2010 6:27 PM | Permalink | PGP Sig | Reply to this

Re: Extraordinary 2-Multicategories

Do you ever look to decompose a natural transformation into a pair of extranaturals? That is, say we have α\alpha between f:AXf: A \to X and g:AXg: A \to X, do we look for some BB and bBb \in B such that α\alpha is equal to some composite

α a=γ a,bβ a,b:f(a)h(a,b,b)g(a)? \alpha_a = \gamma_{a, b} \cdot \beta_{a, b}: f(a) \to h(a, b, b) \to g(a)?

Could there be ‘maximal’/’minimal’ such decompositions?

Posted by: David Corfield on April 2, 2010 8:55 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Do you ever look to decompose a natural transformation into a pair of extranaturals?

I’ve never wanted to do such a thing, or heard of anyone wanting to do it.

Posted by: Mike Shulman on April 2, 2010 4:14 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Bent! 3 cheers for not calling it twisted.

Posted by: jim stasheff on April 1, 2010 1:25 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

For people who are interested, here’s how I’m thinking of defining extraordinary 2-multicategories. Let PCatPCat be the category of partial categories, i.e. reflexive directed graphs with a partially defined composition operation which is always unital (all identities exist) and associative insofar as it is defined. Of course, functors between partial categories must preserve all identities and all defined composites (i.e. if gfg \circ f is defined, then so is FgFfF g \circ F f and it is equal to F(gf)F(g\circ f)). There should be a monad TT on PCatPCat such that the objects of TCT C are finite lists of objects of CC with variance, e.g. (x,y op,z,x op)(x,y^{op},z,x^{op}), and the morphisms of TCT C are loop-free graphs each of whose edges is labeled with a morphism of CC in the appropriate direction. Two morphisms in TCT C are composable iff their graphs are composable (i.e. no loops are formed) and each pair of morphisms in CC that would get composed are composable in CC, and in that case their composite is obvious.

An extraordinary 2-multicategory is a generalized multicategory, in the Leinster-Burroni sense, relative to the monad TT, with two additional properties. Recall that this means a span C 0C 1TC 0C_0 \leftarrow C_1 \to T C_0 with an identity C 0C 1C_0 \to C_1 and a composition operation C 1× TC 0TC 1C 1C_1 \times_{T C_0} T C_1 \to C_1 satisfying suitable identities. The properties are:

  1. The partial category C 0C_0 is discrete, i.e. contains no nonidentity morphisms.

  2. The “source” map C 1TC 0C_1 \to T C_0 is an inner fibration of partial categories, i.e. a functor FF such that if FgFfF g\circ F f is defined, then so is gfg\circ f (and then necessarily FgFf=F(gf)F g \circ F f = F(g\circ f), since FF is a functor).

This matches my above informal description as follows:

  • The objects of C 0C_0 are the objects of the extraordinary 2-multicategory.

  • The objects of C 1C_1 are its morphisms; each has as source an object of TC 0T C_0, i.e. a list of objects with variance, and as target a single object of C 0C_0.

  • The morphisms of C 1C_1 are the “extraordinary 2-cells.” Their “vertical” source and target in C 1C_1 are two morphisms, which must have equal targets (since C 0C_0 is discrete), and their “horizontal” source is a morphism of TC 0T C_0, i.e. a graph with edges labeled by objects of C 0C_0.

The assumption that C 1TC 0C_1 \to T C_0 is an inner fibration means that whenever two 2-cells have composable graphs, they are composable (“vertically,” i.e. as morphisms in C 1C_1). The composition C 1× TC 0TC 1C 1C_1 \times_{T C_0} T C_1 \to C_1 of the generalized multicategory specifies the “horizontal” composition of morphisms and 2-cells via substitution which I left as an exercise.

Now by the general yoga of representability for generalized multicategories (which is, for example, how we identify monoidal categories with certain multicategories), a “representable” extraordinary 2-multicategory corresponds to a “TT-structured category,” i.e. an internal category in PCatPCat with a (possibly pseudo) structure of TT-algebra. An internal category in PCatPCat is, of course, like an internal category in CatCat, i.e. a double category, except that not all the arrows in one direction (say, the vertical direction, since that matches the other pictures) can necessarily be composed. The TT-structure makes such a thing sort of “compact closed,” in the sense that it is monoidal (with horizontal coherence isomorphisms) and every object has a vertical dual, which are assigned horizontally functorially.

This is very close to the profunctor context; the only differences seem to be that (1) not all vertical arrows are composable, and (2) not all cartesian squares necessarily exist. But it seems as though those could probably both be added “freely,” to give a “free compact-closed proarrow-equipment” generated by an extraordinary 2-multicategory. At the moment, this seems to me like it might have something to do with the relationship between the two ways of presenting “theories.”

Posted by: Mike Shulman on April 2, 2010 4:09 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Now I wish I’d waited a little longer before posting that last comment, because in thinking about how these things relate to compact-closed proarrow-equipments, I think I’ve come up with a better definition, which does away with those partial categories and includes the loops, and is much more nicely related to the profunctor approach.

Instead of generalized multicategories in the Leinster-Burroni sense, which live on spans, let’s use instead generalized multicategories in the Hermida sense, which live on profunctors. (The relation between the two is explained in this paper; we get to the latter from the former by applying the monoids-and-modules construction.) So instead of monads on CatCat with their usual extension to Span(Cat)Span(Cat), we are looking at monads on DblCatDblCat with an extension to the virtual double category of double categories and double profunctors.

Here we can define a similar monad TT, but which uses all graphs, possibly containing an ordered list of loops. As I explained up here, composition of such things is not strictly associative, but that’s okay now, as long as we are working with pseudo double categories. Now we can define an extraordinary 2-multicategory to be a virtual TT-algebra (i.e. a generalized multicategory relative to TT) whose underlying double category is discrete in one direction. No nonsense about inner fibrations, since now all composites of extraordinary 2-cells exist. This has the added benefit that the underlying double category, being discrete in one direction, is exactly a 2-category, and it is specifically the 2-category you would expect to have underlying an extraordinary 2-multicategory.

Furthermore, for this TT, a pseudo TT-algebra is a natural (unbiased) notion of compact-closed pseudo double category. Thus, the general yoga of representability for generalized multicategories specializes more or less exactly to compare such things (which include, in particular, compact-closed proarrow-equipments) with extraordinary 2-multicategories, defined in this way. (Though it may not be as nice as it sometimes is, since double profunctors can’t be composed associatively. This means that it doesn’t fit in Hermida’s approach as such; we really need the extra generality of virtual equipments that Geoff and I used.) In particular, this should give a direct construction of the extraordinary 2-multicategory underlying any compact-closed proarrow-equipment.

I realize this is very sketchy and possibly won’t make sense to anyone but me. I can explain it more and better, but first I need to work out the details myself and convince myself that it actually works.

Posted by: Mike Shulman on April 2, 2010 9:52 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Really neat stuff, and it would be great if it all works out as you describe in this last comment.

A few questions: how does one describe a cell of TC? And, is there a similar monad on virtual double categories whose pseudo T-algebras are compact closed virtual double categories, or does this rely on the existence of (pseudo) (horizontal) composites in C?

Posted by: Geoff Cruttwell on April 4, 2010 6:02 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

how does one describe a cell of TC?

I think that a cell of TC requires the horizontal source and target to have the same graph shape, possibly differing only by a permutation of the source and target and a permutation of the loops. Then the vertical source and target are required to implement that permutation, so that each edge in the graph gives rise to a potential boundary for a cell in C, which we then fill by an actual such cell. Finally we also connect up the loops in the horizontal source and target, along some given permutation, via cells in C which are vertically-endo. Does that vague explanation make sense?

is there a similar monad on virtual double categories [?]

Maybe. I’ve never quite managed to define a compact-closed virtual double category in a satisfactory way, but maybe the right thing to do is just write down an analogous monad and take that as the definition.

Posted by: Mike Shulman on April 4, 2010 6:17 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

I don’t really understand what the profunctors approach does with loops, but if you want to avoid them you might try replacing the compact-closed structure with a more constrained one, the first guess being some sort of symmetric monoidal closed (smc) structure.

Units are inconvenient to deal with in plain smc structure (as Todd could tell us). I’ll assume for now that they are irrelevant to extranatural transformations. So what we need is a kind of smc structure without units. Such structures have been proposed by

The important point is that in all cases the free such category on a set looks exactly like the loop-free graphs you drew, and loop-freeness is made stable under composition by taking as objects something finer than just lists with variance. Namely, objects are multiplicative linear logic formulas, i.e., formulas with connectives “par” (how to draw a “par”?) and \otimes.

I think such semi smc categories define a cartesian monad on Cat. Might they be useful to you?

Posted by: Tom Hirschowitz on April 7, 2010 10:27 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Interesting suggestion; thanks. But at first glance, it doesn’t seem like it would be the right thing. If I understand correctly, in a TT-multicategory for this monad TT, the morphisms would have MLL formulas as their domain, such as (A(BC))X(A \otimes (B \invamp C)) \to X. But if AA, BB, CC, and XX are categories, what kind of functor is that supposed to be? What I actually see in the motivating example of categories and extranatural transformations is lists with variance.

(The way to get \invamp is with \invamp or \parr).

Posted by: Mike Shulman on April 7, 2010 3:41 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Right, I forgot a connective: linear negation, which satisfies strict de Morgan laws. Thus, any formula is built out of atoms and negated atoms using pars and tensors.

From such a formula, you can extract a list with variance: the list of atoms and negated atoms, read from left to right. For example, a (ab)a^\bot \otimes (a \parr b) yields a ,a,ba^-, a, b.

I don’t fully understand what we’re talking about, but I guess that in your motivating example, a morphism a (ab)xa^\bot \otimes (a \parr b) \to x would be a functor a op×a×bxa^{\mathit{op}} \times a \times b \to x.

We thus would have, e.g., a (non-natural) bijection

C(a (ab),x)C(a (ab),x).C(a^\bot \otimes (a \parr b), x) \equiv C(a^\bot \otimes (a \otimes b), x).

The point being that different domains allow different compositions.

Does that make sense?

Posted by: Tom Hirschowitz on April 7, 2010 7:25 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Okay, so far that mostly makes sense. Why do you say that that bijection will be non-natural, though? Shouldn’t it respect composition in all the variables?

And when you say that different domains allow different compositions, are you referring to composites of 1-morphisms, or composites of 2-cells (labeled by loop-free graphs), or both? Can you describe exactly what composites are allowed? I can’t figure out from a quick glance at the papers you linked to how the composition is supposed to work.

I’m still skeptical this is going to be what I want, though, because the distinction between \otimes and \parr is foreign to all the examples and applications I have in mind, and I prefer abstract structures to describe exactly what I see whenever possible.

Posted by: Mike Shulman on April 7, 2010 7:48 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Why do you say that that bijection will be non-natural, though? Shouldn’t it respect composition in all the variables?

Yes, you’re probably right.

And when you say that different domains allow different compositions, are you referring to composites of 1-morphisms, or composites of 2-cells (labeled by loop-free graphs), or both? Can you describe exactly what composites are allowed? I can’t figure out from a quick glance at the papers you linked to how the composition is supposed to work.

I realise I wasn’t really clear, sorry. Here is a brief description of the free semi smc category C(X)C(X) over a set XX:

  • its objects are MLL formulas without units over XX;
  • its hom-set C(X)(A,B)C(X)(A, B) between two formulas AA and BB is a certain subset of D(X)(A ,B )D(X)(A^\star, B^\star), where D(X)D(X) is the free compact closed category over XX, and A A^\star denotes AA with all pars replaced with tensors.

Thus, morphisms in C(X)C(X) “are” morphisms in D(X)D(X), and composition works as in D(X)D(X), by glueing the graphs together.

The crucial point is which subset of D(X)(A ,B )D(X)(A^\star,B^\star) is used: it consists of those morphisms satisfying the so-called Danos-Regnier criterion, which I won’t detail here. This subset has the advantages of:

  • being stable under composition, and
  • containing only loop-free morphisms.

Thus, instead of making composition of 2-cells partial, you make 1-cells (formulas) more informative, so as to preserve loop-freeness under composition.

Posted by: Tom Hirschowitz on April 7, 2010 9:06 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Okay, that’s interesting. But it still doesn’t seem to me like the right thing here, because we can have extranaturals labeled by any loop-free graph.

By the way, do you really mean “semi smc”? A plain symmetric monoidal category doesn’t have a dualization operation, so it seems to me like these are more like “semi star-autonomous” or something.

Posted by: Mike Shulman on April 7, 2010 9:38 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Okay, that’s interesting. But it still doesn’t seem to me like the right thing here, because we can have extranaturals labeled by any loop-free graph.

Yes, I understand your concern.

By the way, do you really mean “semi smc”? A plain symmetric monoidal category doesn’t have a dualization operation, so it seems to me like these are more like “semi star-autonomous” or something.

No, you’re right, I should have said semi star-autonomous.

Posted by: Tom Hirschowitz on April 8, 2010 2:15 PM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

Here are the slides from a talk I just gave about these things at the CMS 2010 summer meeting.

Posted by: Mike Shulman on June 5, 2010 1:54 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

I’ll want to spend some time thinking about these structures, but is there a chance it could be put down in the Lab?

Posted by: Todd Trimble on June 5, 2010 4:02 AM | Permalink | Reply to this

Re: Extraordinary 2-Multicategories

A chance, yes, maybe. (-: But probably not in the very near future, since I have a lot of other stuff I need to be writing down at the moment. I did write a bit already at compact double category.

Posted by: Mike Shulman on June 5, 2010 2:56 PM | Permalink | Reply to this
Read the post PSSL 93 trip report
Weblog: The n-Category Café
Excerpt: A report on several talks from the PSSL 93 in Cambridge.
Tracked: April 25, 2012 4:16 PM

Post a New Comment