## 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.

Let us take a look at the simplest kind of operads: non symmetric $\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 $[\mathbf{N},\mathsf{Set}]$ of $\mathbf{N}$-indexed families of sets with the substitution monoidal product (see Simon’s post): for two such families $R$ and $S$, $(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_n$ and $S_n$ are thought as branching with $n$ inputs and one output: $R\circ S$ is then obtained by plugging outputs of elements of $S$ to the inputs of elements of $R$. A non symmetric operad is defined to be a monoid for that monoidal product, a typical example being the family $(\mathsf{Set}(X^n,X))_{n\in\mathbf{N}}$ for a set $X$.

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

where $L$ is the free monoid monad (or list monad) on $\mathsf{Set}$. Hence a non symmetric operad is equivalently a monoid in $\mathsf{Set}/\mathbf{N}$ for this monoidal product. In Burroni’s terminology, it would be called a $L$-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 $\mathbf{N}$ by the groupoid $\mathbf P$ of bijections (to get symmetric operads) or the category $\mathsf{Fin}$ of finite sets (to get Lawvere theories). Obviously, $\mathsf{Set}/\mathbf P$ or $\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: $[\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 $\mathsf{Cat}/\mathbf P$ and $\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 $\mathsf{Cat}/\mathcal{C}$ admits a monoidal product reflecting through the Grothendieck construction the substition product in $[\mathcal{C},\mathsf{Set}]$.

### Abstract clubs

Recall that in a monoidal category $\mathcal{E}$ with product $\otimes$ and unit $I$, any monoid $M$ with multiplication $m: M\otimes M \to M$ and unit $u: I \to M$ induces a monoidal structure on $\mathcal{E}/M$ as follows: the unit is $u: I \to M$ and the product of $f: X \to M$ by $g: Y \to M$ is the composite $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 $M$. For example, even if $\mathcal{E}$ is finitely complete and $\otimes$ is the cartesian product, the induced structure on $\mathcal{E}/M$ is almost never the cartesian one. A notable fact about this structure on $\mathcal{E}/M$ is that the monoids in it are exactly the morphisms of monoids with codomain $M$.

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 $\mathrm{Id}$. The monoids in that category are precisely the monads on $\mathcal{A}$, and for any such $S: \mathcal{A} \to \mathcal{A}$ with multiplication $n: SS \to S$ and unit $j: \mathrm{Id} \to S$, the slice category $[\mathcal{A},\mathcal{A}]/S$ inherits a monoidal structure with unit $j$ and product $\alpha \circ^S \beta$ the composite $T R \overset{\alpha\beta} \to S S \overset n \to S$ for any $\alpha: T \to S$ and $\beta: R \to S$.

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

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 $1$ and the pasting lemma ensures that we only have to check for the pullback property of the naturality squares of the form

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 $\mathcal{M}/S$ the full subcategory of $[\mathcal{A},\mathcal{A}]/S$ whose objects are in $\mathcal{M}$.

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

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

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

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

In particular, this lemma shows that monoids in $\mathcal{M}/S$, which coincide with monad maps $T \to S \in \mathcal{M}$ for some monad $T$, are clubs too. We shall denote the category of these by $\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 $1$ provides an equivalence $\mathcal{M}/S \overset\sim\to \mathcal{A}/S1$ whose pseudo inverse is given for a map $f:K \to S1$ by the natural transformation pointwise defined as the pullback

The previous monoidal product on $\mathcal{M}/S$ can be transported on $\mathcal{A}/S1$ and bears a fairly simple description: given $f:K \to S1$ and $g:H \to S1$, the product, still denoted $f\circ^S g$, is the evaluation at $1$ of the composite $TR \to SS \to S$ where $T \to S$ corresponds to $f$ and $R\to S$ to $g$. Hence the explicit equivalence given above allows us to write this as

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

### Examples of clubs

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

Considering $\mathsf{Cat}$ as a $1$-category, the free finite coproduct category monad $F$ on $\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 $P \to F$ is cartesian, where $P$ is the free strict symmetric monoidal category monad on $\mathsf{Cat}$. Hence it yields for free that $P$ is also a club on $\mathsf{Cat}$. Note that the groupoid $\mathbf{P}$ of bijections is $P1$ and the category $\mathsf{Fin}$ of finite sets is $F1$. So it is now a matter of careful bookkeeping to establish that the functors (given by the Grothendieck construction) $[\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 $\mathsf{Set}$-operads and non enriched Lawvere theories as special clubs over $\mathbf{P}$ and $\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 $\mathsf{Set}$ that we are used to. But what about operads on other categories? Also, the above monads $P$ and $F$ are actually $2$-monads on $\mathsf{Cat}$ when seen as a $2$-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 $0$-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 $\mathcal{B}/B$ is defined to have elements $1 \to \mathcal{B}(X,B)$ as objects, and the space of morphisms between such $f:1 \to \mathcal{B}(X,B)$ and $f':1 \to \mathcal{B}(X',B)$ is given by the following pullback in $\mathcal{V}_0$:

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)$ and $(N,n,j)$ is supposed to interpret “the subspace of those $f: M \to N$ such that $fi=j$ and $fm(x,y)=n(fx,fy)$ for all $x,y$”, where the later equation has two occurences of $f$ 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

Moreover, these hypothesis also resolve the set theoretical issues: because of all the hypotheses on $\mathcal{V}$, the underlying $\mathcal{V}_0$ identifies with the category $\mathrm{Lex}[\mathcal{T}_0,\mathsf{Set}]$ of $\mathsf{Set}$-valued left exact functors from the finitely presentables of $\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 $\mathcal{V}'=\mathrm{Lex}[\mathcal{T}_0,\mathsf{Set}']$ where $\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 $\alpha: T \to S$ cartesian just when it is so as a natural transformation $T_0 \to S_0$, and denote the set of these by $\mathcal{M}$. For a $\mathcal{V}$-monad $S$ on $\mathcal{A}$, the category $\mathcal{M}/S$ is the full subcategory of the slice $[\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 $S$ such that $\mathcal{M}/S$ is closed under the induced $\mathcal{V}$-monoidal product of $[\mathcal{A},\mathcal{A}]/S$.

Now comes the fundamental proposition about enriched clubs:

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

In that case, the category of monoids in $\mathcal{M}/S$ is composed of the clubs $T$ together with a $\mathcal{V}$-monad map $1 \to [\mathcal{A},\mathcal{A}](T,S)$ in $\mathcal{M}$. We will still denote it $\mathbf{Club}(\mathcal{A})/S$ and its underlying ordinary category is $\mathbf{Club}(\mathcal{A}_0)/S_0$. We can once again take advantage of the $\mathcal{V}$-equivalence $\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 $S1$. 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$ preserves and reflects clubs.

### Examples of enriched clubs

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

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

Last but not least, a quite surprising example at first sight. Any small ordinary category $\mathcal{A}_0$ is naturally enriched in its category of presheaves $\mathrm{Psh}(\mathcal{A}_0)$, as the full subcategory of the cartesian cosmos $\mathcal{V}=\mathrm{Psh}(\mathcal{A}_0)$ spanned by the representables. Concretely, the space of morphisms between $A$ and $B$ is given by the presheaf $\mathcal{A}(A,B): C \mapsto \mathcal{A}_0(A \times C, B)$ Hence an $\mathcal{V}$-endofunctor $S$ on $\mathcal{A}$ is the data of a map $A \mapsto SA$ on objects, together with for any $A,B$ a $\mathcal{V}$-natural transformation $\sigma_{A,B}: \mathcal{A}(A,B) \to \mathcal{A}(SA,SB)$ satisfying some axioms. Now fixing $A,C \in \mathcal{A}$, the collection of $(\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 $\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_0$. Along this translation, a strong monad on $\mathcal{A}$ is then just a $\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 $\mathcal{A}_0$. Hence, those are $\mathrm{Psh}(\mathcal{A}_0)$-monads whose underlying ordinary monad is a club: that is, they are $\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 $\mathcal{A}/S1$, but at categories of span with one leg pointing to $S C$ (morally mapping an operation to its coloured arity) and the other one to $C$ (morally picking the output colour), where the $C$ is the object of colours. Those spans actually appear above implicitly whenever a map or the form $!: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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2960

### 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 $\mathcal{B}/B(f,f')$ doesn’t require $1$ 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 $\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 $\mathcal{B}/B(f,f')$ is not necessarily a subobject of $\mathcal{B}(X,X')$ if the monoidal unit $I$ 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 $I \to I$ (for example, if my computation is correct, $\mathsf{Vect_k}/0$ in the enriched sense is not $\mathsf{Vect}_k$ as the space $\mathsf{Vect_k}/0(E,F)$ consists of maps $E \to F$ together with a scalar in $k$; but double-check that to be sure)

To be fair, even in full generality, the slice is a comma-object in $\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 \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 $I$). Both for this $\mathcal{A}\to\mathcal{I}$ to exists and to identify $[\mathcal{I},\mathcal{A}]$ with $\mathcal{A}$, we shall have $I$ 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 $S$-multicategory (in the Burroni-Leinster sense) is structure on a span $C_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 $\mathcal{A}/C_0 \times S C_0$. Unlike the special case of $C_0=1$, this cannot be identified with a slice category of monads cartesianly-over $S$. Instead, it is more natural to view this monoidal category as an endo-hom-category in a bicategory of “$S$-spans”, and an $S$-multicategory as a monad in that bicategory. Even better is to promote $S$-spans to a double category, as that allows us to define $S$-multi-functors as well. Finally, the double category of $S$-spans is constructed naturally from an extension of the monad $S$ 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 $[\mathbf{P},Set] \to Cat/\mathbf{P}$ is not an equivalence, so that not every $\mathbf{P}$-club is a symmetric operad. Namely, if instead of considering $P$ as a monad on the double category $Span(Cat)$, we consider it as a monad on $Prof$, 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 $CAT$; now express all of Kelly’s constructions using 2-categorical operations in $CAT$, and then generalize them to an arbitrary 2-category $\mathcal{K}$ replacing $CAT$. A double club is then what you get by specializing to the case $\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 $Prof$. 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 $S$ for the inputs, a different monad $T$ 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 $Prof$); but the distributive law we need is a transformation in the “loose” direction (the direction of the profunctors in $Prof$). 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 $S$ is a polynomial monad, then it is automatically cartesian. Moreover, any cartesian transformation $T\to S$ implies that $T$ is polynomial too, so Kelly’s category $\mathcal{M}/S$ is equivalently the category of polynomial endofunctors over $S$. However, polynomial functors make sense between arbitrary slices of $\mathcal{A}$, not just $\mathcal{A}$ itself: a polynomial functor $\mathcal{A}/I \to \mathcal{A}/J$ is of the form $p_! f_\ast q^\ast$ for some “polynomial data” $I \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 $\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 $S$, so that in particular $I=J=1$, and we set $I'=J'=C_0$, then the remaining data consists of an object $A'=C_1$, a map $C_1\to C_0$, a map $C_1 \to A$, and a map $f^\ast C_1 \to C_0$. Manipulating adjoints, the latter map is equivalent to giving a map $C_1 \to f_\ast q^\ast C_0$ over $A$. Thus if we give an arbitrary map $C_1 \to f_\ast q^\ast C_0$, the map $C_1\to A$ is uniquely determined. But (the domain of) $f_\ast q^\ast C_0$ is just $S C_0$, so as data we are left with just a span $C_0 \leftarrow C_1 \to S C_0$, i.e. the underlying data of an $S$-multicategory. Thus the category of polynomial endofunctors of $\mathcal{A}/C_0$ equipped with such a cartesian map to $S$ can be identified with the category of “$S$-endospans” of $C_0$. In fact this argument didn’t need the assumption $I'=J'$, and it identifies the whole “slice double category” of polynomials cartesianly-over $S$ (whose construction uses the monad structure of $S$) with the double category of $S$-spans. In particular, polynomial monads (on arbitrary slices of $\mathcal{A}$) cartesianly-over $S$ can be identified with $S$-multicategories.

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

Post a New Comment