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.

April 17, 2017

On Clubs and Data-Type Constructors

Posted by Emily Riehl

Guest post by Pierre Cagne

The Kan Extension Seminar II continues with a third consecutive of Kelly, entitled On clubs and data-type constructors. It deals with the notion of club, first introduced by Kelly as an attempt to encode theories of categories with structure involving some kind of coherence issues. Astonishing enough, there is no mention of operads whatsoever in this article. (To be fair, there is a mention of “those Lawvere theories with only associativity axioms”…) Is it because the notion of club was developed in several stages at various time periods, making operads less identifiable among this work? Or does Kelly judge irrelevant the link between the two notions? I am not sure, but anyway I think it is quite interesting to read this article in the light of what we now know about operads.

Before starting with the mathematical content, I would like to thank Alexander, Brendan and Emily for organizing this online seminar. It is a great opportunity to take a deeper look at seminal papers that would have been hard to explore all by oneself. On that note, I am also very grateful for the rich discussions we have with my fellow participants.

Non symmetric Set-operads

Let us take a look at the simplest kind of operads: non symmetric Set\mathsf{Set}-operads. Those are informally collections of operations with given arities closed under compositions. The usual way to define them is to endow the category [N,Set][\mathbf{N},\mathsf{Set}] of N\mathbf{N}-indexed families of sets with the substitution monoidal product (see Simon’s post): for two such families RR and SS, (RS) n= k 1++k m=nR m×S k 1××S k mnN (R \circ S)_n = \sum_{k_1+\dots+k_m = n} R_m \times S_{k_1} \times \dots \times S_{k_m} \quad \forall n \in \mathbf{N} This monoidal product is better understood when elements of R nR_n and S nS_n are thought as branching with nn inputs and one output: RSR\circ S is then obtained by plugging outputs of elements of SS to the inputs of elements of RR. A non symmetric operad is defined to be a monoid for that monoidal product, a typical example being the family (Set(X n,X)) nN(\mathsf{Set}(X^n,X))_{n\in\mathbf{N}} for a set XX.

We can now take advantage of the equivalence [N,Set]Set/N[\mathbf{N},\mathsf{Set}] \overset \sim \to \mathsf{Set}/\mathbf{N} to equip the category Set/N\mathsf{Set}/\mathbf{N} with a monoidal product. This equivalence maps a family SS to the coproduct nS n\sum_n S_n with the canonical map to N\mathbf{N}, while the inverse equivalence maps a function a:ANa: A \to \mathbf{N} to the family of fibers (a 1(n)) nN(a^{-1}(n))_{n\in\mathbf{N}}. It means that a N\mathbf{N}-indexed family can be thought either as a set of operations of arity nn for each nn or as a bunch of operations, each labeled by an integer given its arity. Let us transport the monoidal product of [N,Set][\mathbf{N}, \mathsf{Set}] to Set/N\mathsf{Set}/\mathbf{N}: given two maps a:ANa: A \to \mathbf{N} and b:BNb: B \to \mathbf{N}, we compute the \circ-product of the family of fibers, and then take the coproduct to get AB={(x,y 1,,y m):xA,y iB,a(x)=m} A\circ B = \{ (x,y_1,\dots,y_m) : x \in A, y_i \in B, a(x) = m \} with the map ABNA\circ B \to \mathbf{N} mapping (x,y 1,,y m) ib(y i)(x,y_1,\dots,y_m)\mapsto \sum_i b(y_i). That is, the monoidal product is achieved by computing the following pullback:

Non symmetric operads as pullbacks

where LL is the free monoid monad (or list monad) on Set\mathsf{Set}. Hence a non symmetric operad is equivalently a monoid in Set/N\mathsf{Set}/\mathbf{N} for this monoidal product. In Burroni’s terminology, it would be called a LL-category with one object.

In my opinion, Kelly’s clubs are a way to generalize this point of view to other kind of operads, replacing N\mathbf{N} by the groupoid P\mathbf P of bijections (to get symmetric operads) or the category Fin\mathsf{Fin} of finite sets (to get Lawvere theories). Obviously, Set/P\mathsf{Set}/\mathbf P or Set/Fin\mathsf{Set}/\mathsf{Fin} does not make much sense, but the coproduct functor of earlier can be easily understood as a Grothendieck construction that adapts neatly in this context, providing functors: [P,Set]Cat/P,[Fin,Set]Cat/Fin [\mathbf P,\mathsf{Set}] \to \mathsf{Cat}/\mathbf P,\qquad [\mathsf{Fin},\mathsf{Set}] \to \mathsf{Cat}/\mathsf{Fin} Of course, these functors are not equivalences anymore, but it does not prevent us from looking for monoidal products on Cat/P\mathsf{Cat}/\mathbf P and Cat/Fin\mathsf{Cat}/\mathsf{Fin} that restrict to the substitution product on the essential images of these functors (i.e. the discrete opfibrations). Before going to the abstract definitions, you might keep in mind the following goal: we are seeking those small categories 𝒞\mathcal{C} such that Cat/𝒞\mathsf{Cat}/\mathcal{C} admits a monoidal product reflecting through the Grothendieck construction the substition product in [𝒞,Set][\mathcal{C},\mathsf{Set}].

Abstract clubs

Recall that in a monoidal category \mathcal{E} with product \otimes and unit II, any monoid MM with multiplication m:MMMm: M\otimes M \to M and unit u:IMu: I \to M induces a monoidal structure on /M\mathcal{E}/M as follows: the unit is u:IMu: I \to M and the product of f:XMf: X \to M by g:YMg: Y \to M is the composite XYfgMMmM X\otimes Y \overset {f\otimes g}\to M \otimes M \overset{m}\to M Be aware that this monoidal structure depends heavily on the monoid MM. For example, even if \mathcal{E} is finitely complete and \otimes is the cartesian product, the induced structure on /M\mathcal{E}/M is almost never the cartesian one. A notable fact about this structure on /M\mathcal{E}/M is that the monoids in it are exactly the morphisms of monoids with codomain MM.

We will use this property in the monoidal category [𝒜,𝒜][\mathcal{A},\mathcal{A}] of endofunctors on a category 𝒜\mathcal{A}. I will not say a lot about size issues here, but of course we assume that there exist enough universes to make sense of [𝒜,𝒜][\mathcal{A},\mathcal{A}] as a category even when 𝒜\mathcal{A} is not small but only locally small: that is, if smallness is relative to a universe 𝕌\mathbb{U}, then we posit a universe 𝕍𝕌\mathbb{V} \ni \mathbb{U} big enough to contain the set of objects of 𝒜\mathcal{A}, making 𝒜\mathcal{A} a 𝕍\mathbb{V}-small category hence [𝒜,𝒜][\mathcal{A},\mathcal{A}] a locally 𝕍\mathbb{V}-small category. The monoidal product on [𝒜,𝒜][\mathcal{A},\mathcal{A}] is just the composition of endofunctors and the unit is the identity functor Id\mathrm{Id}. The monoids in that category are precisely the monads on 𝒜\mathcal{A}, and for any such S:𝒜𝒜S: \mathcal{A} \to \mathcal{A} with multiplication n:SSSn: SS \to S and unit j:IdSj: \mathrm{Id} \to S, the slice category [𝒜,𝒜]/S[\mathcal{A},\mathcal{A}]/S inherits a monoidal structure with unit jj and product α Sβ\alpha \circ^S \beta the composite TRαβSSnS T R \overset{\alpha\beta} \to S S \overset n \to S for any α:TS\alpha: T \to S and β:RS\beta: R \to S.

Now a natural transformation γ\gamma between two functors F,G:𝒜𝒜F,G: \mathcal{A} \to \mathcal{A} is said to be cartesian whenever the naturality squares

Cartesian natural transformation

are pullback diagrams. If 𝒜\mathcal{A} is finitely complete, as it will be for the rest of the post, it admits in particular a terminal object 11 and the pasting lemma ensures that we only have to check for the pullback property of the naturality squares of the form

Alternative definition of cartesian natural transformation

to know if γ\gamma is cartesian. Let us denote by \mathcal{M} the (possibly large) set of morphsisms in [𝒜,𝒜][\mathcal{A},\mathcal{A}] that are cartesian in this sense, and denote by /S\mathcal{M}/S the full subcategory of [𝒜,𝒜]/S[\mathcal{A},\mathcal{A}]/S whose objects are in \mathcal{M}.

Definition. A club in 𝒜\mathcal{A} is a monad SS such that /S\mathcal{M}/S is closed under the monoidal product S\circ^S.

By “closed under S\circ^S”, it is understood that the unit jj of SS is in \mathcal{M} and that the product α Sβ\alpha \circ^S \beta of two elements of \mathcal{M} with codomain SS still is in \mathcal{M}. A useful alternate characterization is the following:

Lemma. A monad (S,n,j)(S,n,j) is a club if and only if n,jn,j \in \mathcal{M} and SS\mathcal{M}\subseteq \mathcal{M}.

It is clear from the definition of S\circ^S that the condition is sufficient, as the α Sβ\alpha \circ^S \beta can be written as n(Sβ)(αT)n\cdot(S\beta)\cdot(\alpha T) via the exchange rule. Now suppose SS is a club: jj \in \mathcal{M} as it is the monoidal unit; nn \in \mathcal{M} comes from id S Sid S\mathrm{id}_S \circ^S \mathrm{id}_S \in \mathcal{M}; finally for any α:TS\alpha: T \to S \in \mathcal{M}, we should have id S Sα=n(Sα)\mathrm{id}_S \circ^S \alpha = n\cdot(S\alpha) \in \mathcal{M}, and having already nn\in\mathcal{M} this yields SαS\alpha \in \mathcal{M} by the pasting lemma.

In particular, this lemma shows that monoids in /S\mathcal{M}/S, which coincide with monad maps TST \to S \in \mathcal{M} for some monad TT, are clubs too. We shall denote the category of these by Club(𝒜)/S\mathbf{Club}(\mathcal{A})/S.

The lemma also implies that any cartesian monad, by which is meant a pullbacks preserving monad with cartesian unit and multiplication, is automatically a club.

Now note that evaluation at 11 provides an equivalence /S𝒜/S1\mathcal{M}/S \overset\sim\to \mathcal{A}/S1 whose pseudo inverse is given for a map f:KS1f:K \to S1 by the natural transformation pointwise defined as the pullback


The previous monoidal product on /S\mathcal{M}/S can be transported on 𝒜/S1\mathcal{A}/S1 and bears a fairly simple description: given f:KS1f:K \to S1 and g:HS1g:H \to S1, the product, still denoted f Sgf\circ^S g, is the evaluation at 11 of the composite TRSSSTR \to SS \to S where TST \to S corresponds to ff and RSR\to S to gg. Hence the explicit equivalence given above allows us to write this as

Clubs as pullbacks

Definition. By abuse of terminology, a monoid in 𝒜/S1\mathcal{A}/S1 is said to be a club over S1S1.

Examples of clubs

On Set\mathsf{Set}, the free monoid monad LL is cartesian, hence a club on Set\mathsf{Set} in the above sense. Of course, we retrieve as L\circ^L the monoidal product of the introduction on Set/N\mathsf{Set}/\mathbf{N}. Hence, clubs over N\mathbf{N} in Set\mathsf{Set} are exactly the non symmetric Set\mathsf{Set}-operads.

Considering Cat\mathsf{Cat} as a 11-category, the free finite coproduct category monad FF on Cat\mathsf{Cat} is a club in the above sense. This can be shown directly through the charaterization we stated earlier: its unit and multiplication are cartesian and it maps cartesian transformations to cartesian transformations. Moreover, the obvious monad map PFP \to F is cartesian, where PP is the free strict symmetric monoidal category monad on Cat\mathsf{Cat}. Hence it yields for free that PP is also a club on Cat\mathsf{Cat}. Note that the groupoid P\mathbf{P} of bijections is P1P1 and the category Fin\mathsf{Fin} of finite sets is F1F1. So it is now a matter of careful bookkeeping to establish that the functors (given by the Grothendieck construction) [P,Set]Cat/P,[Fin,Set]Cat/Fin [\mathbf{P},\mathsf{Set}] \to \mathsf{Cat}/\mathbf{P}, \qquad [\mathsf{Fin},\mathsf{Set}] \to \mathsf{Cat}/\mathsf{Fin} are strong monoidal where the domain categories are given Kelly’s substition product. In other words, it exhibits symmetric Set\mathsf{Set}-operads and non enriched Lawvere theories as special clubs over P\mathbf{P} and Fin\mathsf{Fin}.

We could say that we are done: we have a polished abstract notion of clubs that can encompass the different notions of operads on Set\mathsf{Set} that we are used to. But what about operads on other categories? Also, the above monads PP and FF are actually 22-monads on Cat\mathsf{Cat} when seen as a 22-category. Can we extend the notion to this enrichement?

Enriched clubs

We shall fix a cosmos 𝒱\mathcal{V} to enriched over (and denote as usual the underlying ordinary notions by a 00-index), but we want it to have good properties, so that finite completeness makes sense in this enriched framework. Hence we ask that 𝒱\mathcal{V} is locally finitely presentable as a closed category (see David’s post). Taking a look at what we did in the ordinary case, we see that it heavily relies on the possibility of defining slice categories, which is not possible in full generality. Hence we ask for 𝒱\mathcal{V} to be semicartesian, meaning that the monoidal unit of 𝒱\mathcal{V} is its terminal object: then for a 𝒱\mathcal{V}-category \mathcal{B}, the slice category /B\mathcal{B}/B is defined to have elements 1(X,B)1 \to \mathcal{B}(X,B) as objects, and the space of morphisms between such f:1(X,B)f:1 \to \mathcal{B}(X,B) and f:1(X,B)f':1 \to \mathcal{B}(X',B) is given by the following pullback in 𝒱 0\mathcal{V}_0:

Comma enriched

If we also want to be able to talk about the category of enriched clubs over something, we should be able to make a 𝒱\mathcal{V}-category out of the monoids in a monoidal 𝒱\mathcal{V}-category. Again, this is a priori not possible to do: the space of monoid maps between (M,m,i)(M,m,i) and (N,n,j)(N,n,j) is supposed to interpret “the subspace of those f:MNf: M \to N such that fi=jfi=j and fm(x,y)=n(fx,fy)fm(x,y)=n(fx,fy) for all x,yx,y”, where the later equation has two occurences of ff on the right. Hence we ask that 𝒱\mathcal{V} is actually a cartesian cosmos, so that the interpretation of such a subspace is the joint equalizer of

Monoid enriched

Monoid enriched

Moreover, these hypothesis also resolve the set theoretical issues: because of all the hypotheses on 𝒱\mathcal{V}, the underlying 𝒱 0\mathcal{V}_0 identifies with the category Lex[𝒯 0,Set]\mathrm{Lex}[\mathcal{T}_0,\mathsf{Set}] of Set\mathsf{Set}-valued left exact functors from the finitely presentables of 𝒱 0\mathcal{V}_0. Hence, for a 𝒱\mathcal{V}-category 𝒜\mathcal{A}, the category of 𝒱\mathcal{V}-endofunctors [𝒜,𝒜][\mathcal{A},\mathcal{A}] is naturally a 𝒱\mathcal{V}'-category for the cartesian cosmos 𝒱=Lex[𝒯 0,Set]\mathcal{V}'=\mathrm{Lex}[\mathcal{T}_0,\mathsf{Set}'] where Set\mathsf{Set}' is the category of 𝕍\mathbb{V}-small sets for a universe 𝕍\mathbb{V} big enough to contain the set of objects of 𝒜\mathcal{A}. Hence we do not care so much about size issues and consider everything to be a 𝒱\mathcal{V}-category; the careful reader will replace 𝒱\mathcal{V} by 𝒱\mathcal{V}' when necessary.

In the context of categories enriched over a locally finitely presentable cartesian closed cosmos 𝒱\mathcal{V}, all we did in the ordinary case is directly enrichable. We call a 𝒱\mathcal{V}-natural transformation α:TS\alpha: T \to S cartesian just when it is so as a natural transformation T 0S 0T_0 \to S_0, and denote the set of these by \mathcal{M}. For a 𝒱\mathcal{V}-monad SS on 𝒜\mathcal{A}, the category /S\mathcal{M}/S is the full subcategory of the slice [𝒜,𝒜]/S[\mathcal{A},\mathcal{A}]/S spanned by the objects in \mathcal{M}.

Definition. A 𝒱\mathcal{V}-club on 𝒜\mathcal{A} is a 𝒱\mathcal{V}-monad SS such that /S\mathcal{M}/S is closed under the induced 𝒱\mathcal{V}-monoidal product of [𝒜,𝒜]/S[\mathcal{A},\mathcal{A}]/S.

Now comes the fundamental proposition about enriched clubs:

Proposition. A 𝒱\mathcal{V}-monad SS is a 𝒱\mathcal{V}-club if and only if S 0S_0 is an ordinary club.

In that case, the category of monoids in /S\mathcal{M}/S is composed of the clubs TT together with a 𝒱\mathcal{V}-monad map 1[𝒜,𝒜](T,S)1 \to [\mathcal{A},\mathcal{A}](T,S) in \mathcal{M}. We will still denote it Club(𝒜)/S\mathbf{Club}(\mathcal{A})/S and its underlying ordinary category is Club(𝒜 0)/S 0\mathbf{Club}(\mathcal{A}_0)/S_0. We can once again take advantage of the 𝒱\mathcal{V}-equivalence /S𝒜/S1\mathcal{M}/S \simeq \mathcal{A}/S1 to equip the later with a 𝒱\mathcal{V}-monoidal product, and abuse terminlogy to call its monoids 𝒱\mathcal{V}-clubs over S1S1. Proving all that carefully require notions of enriched factorization systems that are of no use for this post.

So basically, the slogan is: as long as 𝒱\mathcal{V} is a cartesian cosmos which is loccally presentable as a closed category, everything works the same way as in the ordinary case, and () 0(-)_0 preserves and reflects clubs.

Examples of enriched clubs

As we said earlier, FF and PP are 22-monads on Cat\mathsf{Cat}, and the underlying F 0F_0 and P 0P_0 (earlier just denoted FF and PP) are ordinary clubs. So FF and PP are Cat\mathsf{Cat}-clubs, maybe better called 22-clubs. Moreover, the map P 0F 0P_0 \to F_0 mentioned earlier is easily promoted to a 22-natural transformation making P\mathbf{P} a 22-club over Fin\mathsf{Fin}.

The free monoid monad on a cartesian cosmos 𝒱\mathcal{V} is a 𝒱\mathcal{V}-club and the clubs over L1L1 are precisely the non symmetric 𝒱\mathcal{V}-operads.

Last but not least, a quite surprising example at first sight. Any small ordinary category 𝒜 0\mathcal{A}_0 is naturally enriched in its category of presheaves Psh(𝒜 0)\mathrm{Psh}(\mathcal{A}_0), as the full subcategory of the cartesian cosmos 𝒱=Psh(𝒜 0)\mathcal{V}=\mathrm{Psh}(\mathcal{A}_0) spanned by the representables. Concretely, the space of morphisms between AA and BB is given by the presheaf 𝒜(A,B):C𝒜 0(A×C,B) \mathcal{A}(A,B): C \mapsto \mathcal{A}_0(A \times C, B) Hence an 𝒱\mathcal{V}-endofunctor SS on 𝒜\mathcal{A} is the data of a map ASAA \mapsto SA on objects, together with for any A,BA,B a 𝒱\mathcal{V}-natural transformation σ A,B:𝒜(A,B)𝒜(SA,SB)\sigma_{A,B}: \mathcal{A}(A,B) \to \mathcal{A}(SA,SB) satisfying some axioms. Now fixing A,C𝒜A,C \in \mathcal{A}, the collection of (σ A,B) C:𝒜 0(A×C,B)𝒜 0(SA×C,SB) (\sigma_{A,B})_C : \mathcal{A}_0(A\times C,B) \to \mathcal{A}_0(SA \times C, SB) is equivalently, via Yoneda, a collection of σ˜ A,C:𝒜 0(SA×C,S(A×C)). \tilde{\sigma}_{A,C} : \mathcal{A}_0(SA\times C,S(A \times C)). The axioms that σ\sigma satisfies as a 𝒱\mathcal{V}-enriched natural transformation make σ˜\tilde \sigma a strength for the endofunctor S 0S_0. Along this translation, a strong monad on 𝒜\mathcal{A} is then just a Psh(𝒜 0)\mathrm{Psh}(\mathcal{A}_0)-monad. And it is very common, when modelling side effects by monads in Computer Science, to end up with strong cartesian monads. As cartesian monads, they are in particular ordinary clubs on 𝒜 0\mathcal{A}_0. Hence, those are Psh(𝒜 0)\mathrm{Psh}(\mathcal{A}_0)-monads whose underlying ordinary monad is a club: that is, they are Psh(𝒜 0)\mathrm{Psh}(\mathcal{A}_0)-clubs on 𝒜\mathcal{A}.

In conclusion, let me point out that there is much more in Kelly’s article than presented here, especially on local factorisation systems and their link to (replete) reflexive subcategories with a left exact reflexion. It is by the way quite surprising that he does not stay in full generality longer, as one could define an abstract club in just that framework. Maybe there is just no interesting example to come up with at that level of generality…

Also, a great deal of examples of club comes from never published work of Robin Cockett (or at least, I was not able to find it), so these motivations are quite difficult to follow.

Going a little further in the generalization, the cautious reader should have noticed that we did not say anything about coloured operads. For then we would not have to look at slice categories of the form 𝒜/S1\mathcal{A}/S1, but at categories of span with one leg pointing to SCS C (morally mapping an operation to its coloured arity) and the other one to CC (morally picking the output colour), where the CC is the object of colours. Those spans actually appear above implicitly whenever a map or the form !:X1!:X \to 1 is involved (morally, this is the map picking the “only output colour” in a non coloured operad). This somehow should be contained somewhere in Garner’s work on double clubs or in Shulman’s and Cruttwell’s unified framework for generalized multicategories. I am looking forward to learn more about that in the comments!

Posted at April 17, 2017 12:30 AM UTC

TrackBack URL for this Entry:

4 Comments & 0 Trackbacks

Re: On Clubs and Data-Type Constructors

I have a quick question about your section on enriched clubs: why do we need 𝒱\mathcal{V} to be semi-cartesian in order to define the slice category? The pullback that defines /B(f,f)\mathcal{B}/B(f,f') doesn’t require 11 to be terminal.

I guess we later have to require 𝒱\mathcal{V} to be cartesian anyway (and I can see how we need cartesianness to get δ:(M,N)(M,N)×(M,N)\delta: \mathcal{B}(M,N) \to \mathcal{B}(M,N) \times \mathcal{B}(M,N)), so it’s not really an important question.

Nice post, by the way, and thanks for highlighting the link to the substitution product for operads!

Posted by: Ze on April 17, 2017 6:15 AM | Permalink | Reply to this

Re: On Clubs and Data-Type Constructors

You are right, we don’t need 𝒱\mathcal{V} to be semi-cartesian per se to define the slice category. But it is not very meaningful to do it in full generality. Let me try to convince you:

  • the space /B(f,f)\mathcal{B}/B(f,f') is not necessarily a subobject of (X,X)\mathcal{B}(X,X') if the monoidal unit II is not terminal,
  • related to the previous point, it seems possible that the underlying category of the slice is not the slice of the underlying category when there is non trivial maps III \to I (for example, if my computation is correct, Vect k/0\mathsf{Vect_k}/0 in the enriched sense is not Vect k\mathsf{Vect}_k as the space Vect k/0(E,F)\mathsf{Vect_k}/0(E,F) consists of maps EFE \to F together with a scalar in kk; but double-check that to be sure)

To be fair, even in full generality, the slice is a comma-object in 𝒱-Cat\mathcal{V}\text{-}\mathsf{Cat}, hence still enjoys some universal property.

Now to be completely honest, there is another reason that we want 𝒱\mathcal{V} to be semi-cartesian in our situation, but it is related to the factorization system stuff that I put under the rug: the evaluation [𝒜,𝒜]𝒜[\mathcal{A},\mathcal{A}]\to\mathcal{A} at the terminal 1𝒜1 \in \mathcal{A} should be a left exact reflexion, whose right adjoint is the restriction along 𝒜\mathcal{A}\to \mathcal{I} (\mathcal{I} being the 𝒱\mathcal{V}-category with one object and hom-space II). Both for this 𝒜\mathcal{A}\to\mathcal{I} to exists and to identify [,𝒜][\mathcal{I},\mathcal{A}] with 𝒜\mathcal{A}, we shall have II terminal in 𝒱\mathcal{V}.

Posted by: Pierre Cagne on April 17, 2017 8:24 AM | Permalink | Reply to this

Re: On Clubs and Data-Type Constructors

A nice exposition! I’ll take your last paragraph as invitation to pontificate about one of my favorite subjects. (-:

As you say, an SS-multicategory (in the Burroni-Leinster sense) is structure on a span C 0C 1SC 0C_0 \leftarrow C_1 \to S C_0, and so to exhibit them as monoids in a monoidal category, the category in question must be 𝒜/C 0×SC 0\mathcal{A}/C_0 \times S C_0. Unlike the special case of C 0=1C_0=1, this cannot be identified with a slice category of monads cartesianly-over SS. Instead, it is more natural to view this monoidal category as an endo-hom-category in a bicategory of “SS-spans”, and an SS-multicategory as a monad in that bicategory. Even better is to promote SS-spans to a double category, as that allows us to define SS-multi-functors as well. Finally, the double category of SS-spans is constructed naturally from an extension of the monad SS to the double category of ordinary spans, and this point of view generalizes naturally to monads on other double categories. This was the starting point of my paper with Geoff: all the other notions of generalized multicategory in the literature arise from different choices of the base double category.

This approach also fixes the problem that [P,Set]Cat/P[\mathbf{P},Set] \to Cat/\mathbf{P} is not an equivalence, so that not every P\mathbf{P}-club is a symmetric operad. Namely, if instead of considering PP as a monad on the double category Span(Cat)Span(Cat), we consider it as a monad on ProfProf, then the resulting generalized multicategories are exactly ordinary symmetric multicategories, and similarly for cartesian multicategories (“many-object Lawvere theories”).

Garner’s “double clubs” are a generalization in quite a different direction. I find it easiest to understand them by way of a further generalization to a club in a 2-category. Think of the category 𝒜\mathcal{A} on which Kelly’s clubs live as an object of the 2-category CATCAT; now express all of Kelly’s constructions using 2-categorical operations in CATCAT, and then generalize them to an arbitrary 2-category 𝒦\mathcal{K} replacing CATCAT. A double club is then what you get by specializing to the case 𝒦=DBL\mathcal{K}=DBL, the 2-category of double categories. In other words, Kelly’s clubs are monads on categories; Garner’s double clubs are monads on double categories.

However, Garner’s reason for introducing double clubs was not to talk about monads on double categories, but rather about distributive laws between such monads. Why? Well, up above I said that generalized multicategories are naturally defined with respect to a monad on a double category, such as ProfProf. In fact many monads used for this purpose are “double clubs”, but Garner’s goal was to generalize further to generalized polycategories (though he didn’t actually give a general definition of this notion). Roughly speaking, while in a generalized multicategory a morphism has many inputs and one output, in a generalized polycategory a morphism has many inputs and many outputs. This is naturally described using one monad SS for the inputs, a different monad TT for the outputs, and a sort of distributive law relating them that encodes the “allowable composition operations”. However, the sort of distributive law is a bit funny. Just as a double category has two directions of morphism, functors between double categories admit two directions of natural transformation. The monads on double categories that we’re talking about here have their multiplication and unit transformations in the “tight” direction (the direction of the functors in ProfProf); but the distributive law we need is a transformation in the “loose” direction (the direction of the profunctors in ProfProf). Garner used double clubs as a tool to construct a particular such “loose distributive law” whose corresponding “generalized polycategories” are ordinary polycategories (which turns out to be rather nontrivial). I’ve been thinking about this a lot lately for various reasons, and may end up writing a paper about generalized polycategories, which deserve to at least have a precise published definition.

Posted by: Mike Shulman on April 17, 2017 11:20 AM | Permalink | Reply to this

Re: On Clubs and Data-Type Constructors

There is one way to sort of generalize Kelly’s construction to the many-object case. If we assume that 𝒜\mathcal{A} is locally cartesian closed and that SS is a polynomial monad, then it is automatically cartesian. Moreover, any cartesian transformation TST\to S implies that TT is polynomial too, so Kelly’s category /S\mathcal{M}/S is equivalently the category of polynomial endofunctors over SS. However, polynomial functors make sense between arbitrary slices of 𝒜\mathcal{A}, not just 𝒜\mathcal{A} itself: a polynomial functor 𝒜/I𝒜/J\mathcal{A}/I \to \mathcal{A}/J is of the form p !f *q *p_! f_\ast q^\ast for some “polynomial data” IqBfApJI \xleftarrow{q} B \xrightarrow{f} A \xrightarrow{p} J. Moreover, we have a notion of “cartesian map” between two polynomials with different domains and codomains: it consists of a diagram I q B f A p J I q B f A p J\array{ I' & \xleftarrow{q'} & B' & \xrightarrow{f'} & A' & \xrightarrow{p'} & J' \\ \downarrow & & \downarrow & & \downarrow & & \downarrow \\ I & \xleftarrow{q} & B & \xrightarrow{f} & A & \xrightarrow{p} & J } in which the middle square (only) is a pullback. These are actually the squares in a double category whose vertical category is 𝒜\mathcal{A} and whose horizontal arrows are polynomials.

Now in such a transformation, if the bottom polynomial determines the monad SS, so that in particular I=J=1I=J=1, and we set I=J=C 0I'=J'=C_0, then the remaining data consists of an object A=C 1A'=C_1, a map C 1C 0C_1\to C_0, a map C 1AC_1 \to A, and a map f *C 1C 0f^\ast C_1 \to C_0. Manipulating adjoints, the latter map is equivalent to giving a map C 1f *q *C 0C_1 \to f_\ast q^\ast C_0 over AA. Thus if we give an arbitrary map C 1f *q *C 0C_1 \to f_\ast q^\ast C_0, the map C 1AC_1\to A is uniquely determined. But (the domain of) f *q *C 0f_\ast q^\ast C_0 is just SC 0S C_0, so as data we are left with just a span C 0C 1SC 0C_0 \leftarrow C_1 \to S C_0, i.e. the underlying data of an SS-multicategory. Thus the category of polynomial endofunctors of 𝒜/C 0\mathcal{A}/C_0 equipped with such a cartesian map to SS can be identified with the category of “SS-endospans” of C 0C_0. In fact this argument didn’t need the assumption I=JI'=J', and it identifies the whole “slice double category” of polynomials cartesianly-over SS (whose construction uses the monad structure of SS) with the double category of SS-spans. In particular, polynomial monads (on arbitrary slices of 𝒜\mathcal{A}) cartesianly-over SS can be identified with SS-multicategories.

Posted by: Mike Shulman on April 17, 2017 11:24 AM | Permalink | Reply to this

Post a New Comment