nLab
generalized multicategory

Context

Category theory

Higher algebra

Contents

Idea

An ordinary category consists of a set of objects and a set of arrows, each with a single input or domain object and a single output or codomain object. Arrows are composed by plugging outputs into inputs, as when one composes unary operations.

An ordinary multicategory consists of a set of objects and a set of “multi-arrows”, each with a finite list of inputs or domain objects and a single output or codomain object. These multi-arrows are composed by means of multiple plug-ins or substitutions, as when one substitutes a list of mm operations of varying arities into an mm-ary operation.

Both categories and multicategories can be seen as monads in an appropriate bicategory of span-like objects. Categories are monads in the category of ordinary spans (of sets). Multicategories are monads in a bicategory of spans of shape

XRY *X \leftarrow R \to Y^*

where Y *Y^* is the set of finite lists of elements of YY. In order to compose spans of this type, one uses the fact that () *(-)^* has itself the structure of a monad on SetSet, namely the list monad or “free monoid” monad. The idea of a generalized multicategory is to replace this monad by some more general monad TT.

There are a lot of ways of making this precise, ranging in abstractness from the fairly concrete (cartesian monads on a cartesian category) to the most general and abstract (monads on a virtual equipment). We will start from the former and gradually generalize to the latter.

Definitions

Cartesian monads

Let VV be a finitely complete category, and let TT be a cartesian monad on VV, i.e. a monad whose functor part TT preserves pullbacks, and for which the naturality squares of its unit and multiplication are pullbacks. Then there is a bicategory Span(V,T)Span(V,T) of TT-spans in VV, whose objects XX are objects of VV, whose morphisms XYX \to Y are spans from XX to TYT Y, and whose 2-cells are morphisms of such spans. The identity XXX \to X is the span

XidXηXTXX \overset{id}{\leftarrow} X \overset{\eta X}{\to} T X

where η:1 VT\eta: 1_V \to T is the unit of TT. The composite of TT-spans R:XYR\colon X \to Y, S:YZS\colon Y \to Z is given by taking the following pullback:

RS R TS f g Th Tk X TY TTZ μZ TZ\array{ & & & & R \circ S & & & &\\ & & & \swarrow & & \searrow & & & \\ & & R & & & & T S & &\\ & ^f \swarrow & & \searrow ^g & & ^{T h} \swarrow & & \searrow ^{T k} & \\ X & & & & T Y & & & & T T Z & \overset{\mu Z}{\rightarrow} & TZ}

A TT-multicategory in VV is by definition a monad in the bicategory described above. However, it is convenient to use the alternate word monoid rather than monad here, to avoid confusion with the monad TT which lives on VV, and because the relevant morphisms of monoids (see below) are rather different from any of the usual sort of morphisms of monads.

If we spell out what this means more explicitly, a TT-multicategory consists of an object C 0C_0 of VV, along with a span C 0C 1TC 0C_0 \leftarrow C_1 \to T C_0, and suitable identity-assigning and composition morphisms.

If C 0C_0 is the terminal object, then we speak instead of a TT-operad.

Examples

  • When TT is the “free monoid” monad on SetSet, a TT-multicategory is precisely an ordinary multicategory.

  • When TT is the identity monad on VV, a TT-multicategory is simply an internal category in VV.

  • When TT is the “free strict ω-category” monad on globular sets, a TT-multicategory with C 0=1C_0 = 1 is a globular operad in the sense of Batanin (this reformulation was found by Leinster).

  • If MM is a monoid in SetSet and T=M×T = M\times - is the “free MM-set” monad, then a TT-multicategory is an “MM-graded category.”

  • When TT is the free category monad on quivers, a TT-multicategory is a virtual double category (also called an fc-multicategory, coming from the name “fc” for this monad).

  • If AA is a small category and TT is the monad on Set ob(A)Set^{ob(A)} whose algebras are functors ASetA\to Set, then a TT-multicategory can be identified with an object of Cat/ACat/A.

Kleisli bicategories

Note that when TT is a cartesian monad on a finitely complete category VV, then it extends to a (pseudo) 2-monad on the bicategory Span(V)Span(V). The functor part of this 2-monad is given simply by applying TT; this is a (pseudo) 2-functor since TT preserves pullbacks. The unit of this 2-monad is given by the spans

XidXηXTX X \overset{id}{\leftarrow} X \overset{\eta X}{\to} T X

and its multiplication by

TTXidTTμXTX; T T X \overset{id}{\leftarrow} T T \overset{\mu X}{\to} T X;

these are pseudonatural transformations since η\eta and μ\mu are cartesian natural transformations.

Moreover, the bicategory Span(V,T)Span(V,T) defined above is easily seen to be precisely the Kleisli bicategory of this extended 2-monad TT on Span(V)Span(V). Thus, a more general notion of “generalized multicategory” would be a monad (monoid) in some Kleisli bicategory.

Examples

Are ordinary symmetric multicategories the TT-multicategories relative to any monad TT? Recall that in a symmetric multicategory, the source of a morphism f:(x 1,,x n)yf\colon (x_1,\dots,x_n) \to y is still an ordered list, but we have an action of the symmetric groups on the morphisms, in such a way that for σS n\sigma\in S_n we have σf:(x σ1,,x σn)y\sigma \cdot f \colon (x_{\sigma 1}, \dots, x_{\sigma n}) \to y, and composition is equivariant for this action.

It doesn’t work to let TT be the “free commutative monoid” monad, since that would destroy all ordering on the lists. (Also, that monad is not cartesian.) Really what we want is to let TT be the “free symmetric strict monoidal category” monad, since for a discrete set AA we have TA=T A = the set of finite ordered lists of elements of AA, with isomorphisms imposed for all permutations.

However, of course this monad does not live on SetSet, but rather on CatCat. But there is a natural bicategory which extends CatCat analogously to how SpanSpan extends SetSet, namely the bicategory ProfProf of categories and profunctors. The “free symmetric strict monoidal category” monad TT does extend to a pseudomonad on ProfProf, and symmetric multicategories can be identified with monads C 0TC 0C_0 ⇸ T C_0 in the Kleisli bicategory of this TT such that C 0C_0 is a discrete category.

Double categories

While the bicategorical framework is very nice, it does not provide a good definition of the functors between generalized multicategories. From the explicit point of view, a functor f:CDf\colon C\to D between TT-multicategories should consist of morphisms

C 0 C 1 TC 0 f 0 f 1 Tf 0 D 0 D 1 TD 0 \array { C_0 & \leftarrow & C_1 & \to & T C_0 \\ ^{f_0} \downarrow & & ^{f_1}\downarrow & & \downarrow^{T f_0}\\ D_0 & \leftarrow & D_1 & \to & T D_0 }

which respect the identity and structure maps. This reduces to the natural notion of functor in all the examples mentioned above. However, such morphisms cannot be identified with any of the usual notions of “morphisms of monads” in the bicategory Span(V,T)Span(V,T). The closest thing there is would be a “colax morphism of monads,” but that would allow f 0f_0 to be an arbitrary span rather than a morphism in VV.

We can remedy this problem if instead of the bicategory Span(V,T)Span(V,T), we consider a pseudo double category whose horizontal bicategory is Span(V,T)Span(V,T), and whose vertical arrows are the morphisms of VV. In particular, a square in this double category will be precisely a diagram of the above sort. Thus, if we define a monoid in a double category to be the same as monad in its horizontal bicategory, we can also define a monoid homomorphism in a double category to consist of a vertical arrow and a square respecting the multiplication and identities, in such a way that monoid homomorphisms in Span(V,T)Span(V,T) are precisely the correct functors of TT-multicategories mentioned above.

Thus, a better definition of TT-multicategory is “a monoid in the double category Span(V,T)Span(V,T),” since this definition recovers the correct morphisms immediately. And a better generalized definition, which works for symmetric multicategories as well (using the double category of categories, functors, and profunctors), is “a monoid in a Kleisli double category.”

Equipments

When we try to make the notion of “Kleisli double category” precise, however, we run into some issues. We want the “Kleisli-ness” to happen horizontally, i.e. in the span/profunctor direction. However, in the examples, the monads in question live most naturally in in the 2-category of double categories, functors, and vertical natural transformations. For example, when TT is a monad on VV, its multiplication and unit transformations naturally induce vertical transformations Id Span(V)Span(T)Id_{Span(V)} \to Span(T) and Span(T) 2Span(T)Span(T)^2 \to Span(T), where Span(T)Span(T) denotes the induced functor on Span(V)Span(V). Similarly, for the “free symmetric strict monoidal category” monad on the double category ProfProf, the unit and multiplication are naturally functors, i.e. vertical arrows, not profunctors.

However, in general, if all we know is that TT is a monad on a double category XX in the “vertical” sense, then there is no way to define a “horizontally Kleisli” double category of TT. The composite of horizontal arrows ATBA\to T B and BTCB \to T C in such a double category would have to be the composite ATBTTCμTCA\to T B \to T T C \overset{\mu}{\to} T C, but in a double category there is no way to compose the horizontal arrow ATTCA\to T T C with the vertical arrow μ:TTCTC\mu\colon T T C \to T C. Specifically, the problem is that while any (pseudo) double functor between pseudo double categories induces a (pseudo) 2-functor between horizontal bicategories, a vertical transformation does not necessarily induce a pseudonatural one.

There are two solutions to this problem, and it turns out that the best approach is to use them both. The first, and most obvious, is to generalize the way in which the monads in these two examples do, in fact, induce pseudomonads on the horizontal bicategory. Namely, in both of the double categories SpanSpan and ProfProf, every vertical arrow f:ABf\colon A\to B gives rise to a horizontal arrow B(1,f):ABB(1,f)\colon A\to B in a universal way. This construction, along with its dual, makes SpanSpan and ProfProf into framed bicategories, or equivalently proarrow equipments.

Now in general, a vertical transformation between double categories that are proarrow equipments does not quite induce a pseudo natural transformation on horizonal bicategories, but only an oplax natural transformation. However, in the examples we have considered so far, the oplax transformations are in fact pseudo, and so there is a horizontally-Kleisli double category (which is easily seen to be, itself, a proarrow equipment).

Virtual double categories

From the double-category point of view, it seems unnatural to require that the unit and multiplication of the monad induce “horizontally pseudo” transformations; the vertical transformation of double categories is surely the more basic notion. Moreover, it is also unnatural to require the functor TT to be pseudo; there are interesting examples where TT is only a (horizontally) lax functor. Note that unlike the case for bicategories, there is a 2-category of double categories, lax functors, and vertical transformations, so we can talk about monads in such a 2-category.

However, at this level of generality, the horizontal Kleisli construction does not yield a double category. It does, however, yield a virtual double category. Moreover, it also suffices to take as input a monad TT on a virtual double category XX; we write the result of this construction as HKl(X,T)HKl(X,T). (Recall that for pseudo double categories regarded as virtual ones, functors of virtual double categories can be identified with lax functors of pseudo double categories.) Thus a natural and even more general notion of generalized multicategory is “a monoid in the horizontal-Kleisli virtual double category for some monad TT on a virtual double category;” we call such a thing a TT-monoid.

Note also that for any virtual double category XX, there is another virtual double category Mod(X)Mod(X) whose objects are monoids in XX, whose vertical arrows are monoid homomorphisms, and whose horizontal arrows are “bimodules.” Therefore, for any monad TT on a virtual double category XX, there is another virtual double category KMod(X,T)=Mod(HKl(X,T))KMod(X,T) = Mod(HKl(X,T)) whose objects are TT-monoids, and whose vertical arrows are TT-monoid homomorphisms.

Examples

  • If VV has pullbacks and TT is a monad preserving pullbacks (no condition on η\eta and μ\mu), then TT induces a monad on the virtual double category (which is actually, of course, a pseudo double category) Span(V)Span(V). The TT-monoids in Span(V)Span(V) are then precisely the TT-multicategories, as defined above.

  • The “free symmetric strict monoidal category” monad on ProfProf can also be regarded as a monad on the virtual double category ProfProf, and its TT-monoids on a discrete category are symmetric multicategories.

  • If we use instead the “free category with finite products” monad on the virtual double category ProfProf, then TT-monoids on discrete categories can be identified with cartesian multicategories, which include a sub-collection equivalent to that of Lawvere theories.

  • More basically, we also have a “free strict monoidal category” monad on ProfProf, whose TT-monoids on discrete categories are ordinary non-symmetric multicategories. Noting that Prof=Mod(Span)Prof = Mod(Span), this TT is also Mod(S)Mod(S), where SS is the “free monoid” monad on Span=Span(Set)Span = Span(Set). In fact, quite generally for any monad SS on a virtual double category XX, we can identify SS-monoids in XX with Mod(S)Mod(S)-monoids in Mod(X)Mod(X) on “discrete objects.”

  • The ultrafilter monad UU on SetSet has a “canonical” extension to the virtual double category RelRel of sets, functions, and binary relations. Although RelRel is a pseudo double category and this monad is a strict functor, η\eta is only oplax. The UU-monoids in RelRel can be identified with topological spaces, by an observation originally due to Barr. In this context they are often referred to as relational β-modules, where β\beta is another name for UU.

  • Similarly, the powerset monad PP on SetSet extends to RelRel in a canonical way, and the PP-monoids in RelRel are closure space?s. Topological examples of this sort are sometimes called (T,V)(T,V)-algebras, where TT denotes a Set-monad like UU or PP, and VV a category (usually a quantale) of enrichment.

Units and transformations

Equipments and normalization

References

Revised on February 5, 2014 15:17:00 by Mike Shulman (108.225.238.144)