### 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
$\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!

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