nLab
club

Idea

A club is a particular sort of doctrine or [[monad] on categories, one which encapsulates the following frequently observed phenomenon: to describe free algebras $F(C)$ with respect to the monad, it frequently suffices to describe the free algebra $F(1)$ on the terminal category, and then a certain “wreath product” gives the free algebra on $C$:

$$F(C)\cong F(1)\int C$$F(C) \cong F(1) \int C

Examples of this phenomenon include the monad for monoidal categories, symmetric monoidal categories, braided monoidal categories, categories with finite products, closed symmetric monoidal categories, and many others.

Mike Shulman: How do you get closed symmetric monoidal categories? I thought that was one of the ones that Kelly couldn’t handle because it involves extranatural transformations.

Todd Trimble: You can get them, but there are points to watch. The real trouble to watch out in doctrines of “mixed variance” is the possibility of producing loops or “islands” in the process of composing extranaturals, but as it happens this doesn’t occur in free smc categories. They do occur for compact closed categories, and that’s fatal. The classical example is trace in compact closed categories, where the composite

$$1\stackrel{\eta }{\to }{c}^{*}\otimes c\stackrel{\epsilon }{\to }1$$1 \stackrel{\eta}{\to} c^* \otimes c \stackrel{\varepsilon}{\to} 1

is not a well-defined extranatural since it depends on $c$.

Here are some details on clubs of mixed variance, which I was going to get to but here is a first pass. First, as you might expect, one replaces $P$ below by a category $G$ enriched in pointed sets whose objects are finite signed sets and whose non-basepoint morphisms are oriented 1-cobordisms. Let’s say that two morphisms in $G$ have a “defined” composition if no islands are produced, else their composition is taken to be the basepoint. Now let $F(1)$ be the free smc category on one generator. There is a “graph functor” $\Gamma :F(1)\to G$ which takes a morphism of $F(1)$ to its extranaturality graph. The crucial observation (and it’s a bit nontrivial; the proof relies on a cut-elimination theorem) is that no basepoint morphism lies in the image of $\Gamma$, i.e., no islands can occur in formal compositions for this doctrine.

In cases like that, the basic club idea will work. Given a category $C$, the free smc category $F(C)$ has the expected objects given by formal iterated applications of hom and tensor to objects of $C$. A morphism is given by a morphism of $F(1)$ together with a labeling of the oriented edges of its underlying graph (an oriented 1-cobordism) by morphisms of $C$. Then, you compose morphisms of this “wreath product” in the obvious way, composing the morphism-labels of edges in 1-cobordisms as they get pasted together.

It should also be mentioned (I’m sure you know this) that in such mixed variance cases, even if there are no islands in formal compositions, the result is merely a monad on $\mathrm{Cat}$, not a 2-monad. On the other hand, you do get a 2-monad if you restict to categories, functors, and natural isomorphisms.

Mike Shulman: Ah, right, thanks. Now I remember how Kelly dealt with graphs in that way by just throwing away the “bad composites”. I must have forgotten about it because I thought it was so weird. (-: Is that sort of club also a generalized operad for some cartesian monad on $\mathrm{Cat}$?

Todd Trimble: I’m pretty sure that it’s a cartesian monad on $\mathrm{Cat}$, and actually I don’t know any real examples of Kelly’s clubs which aren’t.

Clubs were introduced by [[Max Kelly], and are akin in spirit to operads. In fact, many types of clubs are a special case of generalized operads.

Clubs over the permutation category

Action by substitution product

Let $P$ be the category of finite sets $[n]=\{1,\dots ,n\}$ (including the empty set $[0]$) and permutations between them, and let $\mathrm{Cat}$ be the category of small categories. We define a “wreath product” action of the category $\mathrm{Cat}/P$ on $\mathrm{Cat}$,

$$\circ :\mathrm{Cat}/P\times \mathrm{Cat}\to \mathrm{Cat}$$\circ: Cat/\mathbf{P} \times Cat \to Cat

taking a pair $(\Gamma :C\to P,D)$ to the category whose objects are tuples

$$(c;d_1,\dots ,d_n)$$(c; d_1, \ldots, d_n)

with $c\in \mathrm{Ob}(C)$, $d_i\in \mathrm{Ob}(D)$, and $\Gamma (c)=[n]$. A morphism is a tuple

$$(f;g_1,\dots ,g_n)$$(f; g_1, \ldots, g_n)

consisting of a morphism $f:c\to c\prime$ in $C$ and morphisms $g_i:d_i\to d_{\Gamma (f)(i)}\prime$ in $D$, composed in the obvious way.

This generalizes the standard notion of wreath product: given a group $G$ and a permutation representation, i.e., a homomorphism $\gamma :G\to \mathrm{Aut}([n])\hookrightarrow P$, and given a group $H$, the wreath product is defined to be the semidirect product

$$G\int H=G⋉H^n$$G \int H = G \ltimes H^n

with the action of $G$ on $H^n$ induced from the action on $[n]$.

Another, more abstract, way to describe this substitution product is as follows: there is a cartesian monad $T$ on $\mathrm{Cat}$ whose algebras are symmetric strict monoidal categories, and we have $P=T1$, where $1$ is the terminal category. The substitution product $\Gamma \circ D$ can then be described as the following pullback in $\mathrm{Cat}$.

$$\begin{array}{ccc}\Gamma \circ D& \stackrel{}{\to }& TD\\ \downarrow & & {\downarrow }^{T!}\\ C& \underset{\Gamma }{\to }& T1& =P\end{array}$$\array{\Gamma \circ D & \overset{}{\to} & T D\\ \downarrow && \downarrow^{T !}\\ C & \underset{\Gamma}{\to} & T 1 & = \mathbf{P}}

Substitution product as monoidal product

We describe how the substitution action $\circ$ lifts to a self-action denoted by the same symbol:

$$\circ :\mathrm{Cat}/P\times \mathrm{Cat}/P\to \mathrm{Cat}/P$$\circ: Cat/\mathbf{P} \times Cat/\mathbf{P} \to Cat/\mathbf{P}

To start, given a pair $(\Gamma :C\to P,\Delta :D\to P)$, the domain of $\Gamma \circ \Delta$ is the category $\Gamma \circ D$ described above. The functor

$$\Gamma \circ \Delta :\Gamma \circ D\to P$$\Gamma \circ \Delta: \Gamma \circ D \to \mathbf{P}

sends an object $(c;d_1,\dots ,d_n)$ to ${\sum }_i\Delta (d_i)$.

The effect of $\Gamma \circ \Delta$ on morphisms $(f;g_1,\dots ,g_n)$ may be summarized as “substituting the permutations $\Delta (g_i)$ into the permutation $\Gamma (f)$”. To describe this more precisely, we give a little preface. The hom-set $P([n],[n])=\mathrm{Aut}(n)$ of permutations on $n$ may be identified with the set $\mathrm{Lin}(n)$ of total (or linear) orders on $[n]$, if we identify the identity element with the standard order on $\{1,2,\dots ,n\}$. The sets $\mathrm{Aut}(n)=\mathrm{Lin}(n)$ are components of an operad $\mathrm{Lin}$ where the operadic multiplication

$$\mu (n;k_1,\dots ,k_n):\mathrm{Lin}(n)\times \mathrm{Lin}(k_1)\times \dots \times \mathrm{Lin}(k_n)\to \mathrm{Lin}(k_1+\dots +k_n)$$\mu(n; k_1, \ldots, k_n): Lin(n) \times Lin(k_1) \times \ldots \times Lin(k_n) \to Lin(k_1 + \ldots + k_n)

takes a linear ordering of $n$ linearly ordered sets of and produces the evident linear ordering on the disjoint sum of the sets.

Then, given a morphism $(f;g_1,\dots ,g_n)$ in $\Gamma \circ D$, we define

$$(\Gamma \circ \Delta )(f;g_1,\dots ,g_n)\stackrel{\mathrm{def}}{=}\mu (n;k_1,\dots ,k_n)(\Gamma (f),\Delta (g_1),\dots \Delta (g_n))$$(\Gamma \circ \Delta)(f; g_1, \ldots, g_n) \stackrel{def}{=} \mu(n; k_1, \ldots, k_n)(\Gamma(f), \Delta(g_1), \ldots \Delta(g_n))

Given the abstract description above of the substitution product in terms of the cartesian monad $T$, the functor $\Gamma \circ \Delta$ can be described as the composite

$$\Gamma \circ D\to TD\stackrel{T\Delta }{\to }TT1\stackrel{{\mu }_1}{\to }T1=P$$\Gamma \circ D \to T D \overset{T \Delta}{\to} T T 1 \overset{\mu_1}{\to} T 1 = \mathbf{P}

where $\mu :TT\to T$ is the multiplication of the monad $T$.

The substitution product thus indicated,

$$\circ :\mathrm{Cat}/P\times \mathrm{Cat}/P\to \mathrm{Cat}/P,$$\circ: Cat/\mathbf{P} \times Cat/\mathbf{P} \to Cat/\mathbf{P},

is the product for a monoidal category structure on $\mathrm{Cat}/P$. The monoidal unit is the functor $I:1\to P$ which names the 1-element set. Abstractly, we can observe that the cartesian monad $T$ induces a pseudomonad on the bicategory $\mathrm{Span}(\mathrm{Cat})$ of spans in $\mathrm{Cat}$, which has a Kleisli bicategory $\mathrm{Span}(\mathrm{Cat}{)}_T$ in which a 1-cell $A\to B$ is a span $A\leftarrow X\to TB$ in $\mathrm{Cat}$. We then have

$$\mathrm{Cat}/P\simeq \mathrm{Cat}/(1\times T1)\simeq \mathrm{Span}(\mathrm{Cat}{)}_T(1,1)$$Cat/\mathbf{P} \simeq Cat / (1 \times T 1) \simeq Span(Cat)_T (1, 1)

and the monoidal structure above is that induced from the bicategory composition in $\mathrm{Span}(\mathrm{Cat}{)}_T$.

Under this monoidal product, the substitution action indicated earlier,

$$\circ :\mathrm{Cat}/P\times \mathrm{Cat}\to \mathrm{Cat},$$\circ: Cat/\mathbf{P} \times Cat \to Cat,

carries a structure of actegory over the monoidal category $\mathrm{Cat}/P$, in the sense that there is a coherent associativity

$$(\Gamma \circ \Delta )\circ E\cong \Gamma \circ (\Delta \circ E)$$(\Gamma \circ \Delta) \circ E \cong \Gamma \circ (\Delta \circ E)

for $\mathrm{Gamma}:C\to P$, $\Delta :D\to P$, and a category $E$, and similarly coherent left and right unit isomorphisms.

Clubs over $P$

Definition: A club over $P$ is a monoid in the monoidal category $(\mathrm{Cat}/P,\circ ,I)$. By the abstract characterization above, this is equivalent to a monad in the bicategory $\mathrm{Span}(\mathrm{Cat}{)}_T$ on the object $1$, or equivalently a $T$-operad in the sense of Leinster.

A club over $P$ induces (via the actegory structure) a 2-monad on $\mathrm{Cat}$, and an algebra over the club is an algebra for this monad. That is, an algebra over a club $C$ is a category $D$ together with an action $m:C\circ D\to D$ compatible in the usual way with the monoid structure on $C$.

Given a club structure on $\Gamma :C\to P$, we think of the objects $c$ as formal operations of arity $n=\Gamma (c)$. An algebra $D$ over $C$, $m:C\circ D\to D$, gives in effect an interpretation of each $c$ of arity $n$ as an actual operation $D^n\to D$.

The free $C$-algebra over a category $D$ is just $C\circ D$. For the free algebra over the terminal category $1$, notice that

$$C\circ 1\cong C$$C \circ 1 \cong C

(strictly speaking, the $C$ on the left is a category over $P$ and the $C$ on the right is just the category). Thus, in a manner of speaking, the free algebra generated by $D$ is obtained by wreathing the free algebra generated by $1$ with $D$, as adumbrated in the idea section above.

Examples

• The identity $1_P:P\to P$ carries a club structure. The multiplication $\mu$ of the club, on the object level, is given by the assignment

  $$(n;k_1,\dots ,k_n)\mapsto k_1+\dots +k_n$$(n; k_1, \ldots, k_n) \mapsto k_1 + \ldots + k_n

  and on morphisms, it is given by the operad structure on $\mathrm{Aut}(n)=\mathrm{Lin}(n)$ discussed above. Algebras over this club are symmetric (strict) monoidal categories. Algebras in the “pseudo” sense over the induced 2-monad on $\mathrm{Cat}$ are symmetric monoidal categories. Alternatively, if $F(1)$ is the free symmetric monoidal category on one generator, then the symmetric monoidal equivalence $\Gamma :F(1)\to P$ carries a club structure whose strict algebras are symmetric monoidal categories.

• Let $B$ be the braid category, equipped with the usual forgetful functor $\Gamma :B\to P$. The club mutliplication, at the level of morphisms, is “substitution” of $n$ braids into a braid on $n$ elements. Pseudo-algebras over the induced 2-monad on $\mathrm{Cat}$ are braided monoidal categories. Alternatively, as in the previous example, braided monoidal categories are also strict algebras over a club of the form $\Gamma :F(1)\to P$ where $F(1)$ is the free braided monoidal category on one generator.

• Let $C$ be any (permutative) operad valued in $\mathrm{Set}$, with underlying species $P\to \mathrm{Set}$. Then category of elements gives a functor $\Gamma :\mathrm{El}(C)\to P$, and this carries a club structure induced from the operad structure on $C$. In this way, clubs generalize operads. In fact, operads in $\mathrm{Set}$ can be identified with those clubs for which the functor $\Gamma :C\to P$ is a discrete fibration.

Clubs over finite sets

Clubs of mixed variance

The clubs described in the preceding two sections are examples of covariant clubs: the operations on their algebras $D$ are covariant functors $D^n\to D$. However, many doctrines on $\mathrm{Cat}$, such as the doctrine of closed categories, involve functors which are covariant in some arguments and contravariant in others, together with extranatural transformations between them. For example, in the doctrine for closed monoidal categories, there is an extranatural transformation of the form

$${\mathrm{ev}}_{X,Y}:[X,Y]\otimes X\to Y$$ev_{X, Y}: [X, Y] \otimes X \to Y

which is dinatural in $X$ and natural in $Y$.

It turns out that many doctrines of “mixed variance” can also be described by an extension of the club notion. This applies particularly to closed monoidal, closed symmetric monoidal, and $*$-autonomous categories. But there are some subtleties, some of which can be explained by looking at a non-example: the doctrine of compact closed categories.

Extranaturality graphs

The underlying arity of an operation of mixed variance will be a signed set, i.e., a finite set $\{1,2,\dots ,n\}$ where a sign $+$ or $-$ is assigned to each element $j$. The element $j$ is given the sign $+$ (resp., $-$) if $j^{\mathrm{th}}$ argument of the operation appears covariantly (resp., contravariantly). For example, for the operation

$$C^{\mathrm{op}}\times C\times C\to C:(a,b,c)\mapsto [a,b]\otimes c$$C^{op} \times C \times C \to C: (a, b, c) \mapsto [a, b] \otimes c

the underlying arity is an ordered list of signs $\{-,+,+\}$.

The underlying arity of an extranatural transformation for a given doctrine is an arrow of signed sets $A$, $B$ called a graph (or EKM graph, for Eilenberg, Kelly and Mac Lane), which by definition is a partition of the signed elements of $A\cup B$ into mated pairs, such that

• Mated elements, one in $A$ and one in $B$, have the same sign;

• Mated elements, both in $A$ or both in $B$, have opposite signs.

An EKM graph may be identified with a directed graph whose edges are mated pairs, oriented in the direction from an $A$-element to a $B$-element if the mates have the same sign, or from $+$ to $-$ if the mates are $A$-elements, or from $-$ to $+$ if the mates are $B$-elements. Such a graph may also be considered as an oriented 1-cobordism between oriented 0-manifolds without loops (circles).

For example, the arity of the evaluation map in closed monoidal categories,

$${\mathrm{ev}}_{X,Y}:[X,Y]\otimes X\to Y$$ev_{X, Y}: [X, Y] \otimes X \to Y

is an arrow with an oriented edge from the third placeholder of the domain to the first placeholder, and an oriented edge from the second placeholder of the domain to the placeholder of the codomain.

Hence we obtain a directed graph whose vertices are signed sets and whose edges are EKM graphs between the signed sets. An immediate question is how to compose graphs to form a category, and in particular what to do about “loops” or “islands” which may arise in composing such 1-cobordisms. The first answer that may come to mind is simply to ignore them (in other words, regard the pairings as morphisms in a bicategory of co-relations, and compose them as such). An answer more relevant to clubs will emerge in the next section.

Doctrine of compact closed categories

An example in which loops arise in compositions of extranatural transformations is the doctrine of compact closed (symmetric monoidal) categories. The classic example is the composition

$$1\stackrel{\eta }{\to }{c}^{*}\otimes c\stackrel{\epsilon }{\to }1$$1 \stackrel{\eta}{\to} c^* \otimes c \stackrel{\varepsilon}{\to} 1

where $1$ denotes a monoidal unit, $\eta$ is a unit for an adjunction $c⊣c^{*}$, and $\epsilon$ is a counit for $c^{*}⊣c$ (in a symmetric monoidal category, such adjunctions are inevitably ambidextrous?).

This composition obviously does not define an extranatural transformtion from a constant functor to itself, precisely because of dependence on $c$ (for example, when interpreted in the compact closed category of finite-dimensional vector spaces, the value is $\dim (c)$). In general, the presence of loops in compositions of extranaturality graphs should be seen as reflecting a fatal ill-definedness of composition of the extranatural transformations giving rise to them, and in such situations an alarm should sound: ”Danger, Will Robinson!”.

The lesson learned is that the doctrine of compact closed categories is not describable by a club, and that for the purposes of clubs there is no use for compositions of graphs which produce loops. If one insists on assigning a value to composition in such cases, it might as well be a junk value $*$, and therefore it is justifiable to regard signed sets and arrows between them as carrying a structure of category enriched in the symmetric monoidal category of pointed sets (= category of sets and partially defined functions).

Definition of club of mixed variance

Let $G$ be the category enriched in pointed sets whose objects are finite signed sets, and whose morphisms are graphs as described above, composed as in the bicategory of cospans between sets unless this results in the creation of loops (in which case the composition is defined to be the basepoint of the hom-set it belongs to). There is no harm in thinking of $G$ as an ordinary category.

Let $(\mathrm{Cat}/G)\prime$ be the full subcategory of $\mathrm{Cat}/G$ whose objects are functors $\Gamma :C\to G$ such that for every morphism $f$ of $C$, $\Gamma (f)$ is not the basepoint of the hom-set it belongs to. There is an action

$$\circ :(\mathrm{Cat}/G)\prime \times \mathrm{Cat}\to \mathrm{Cat}$$\circ: (Cat/\mathbf{G})' \times Cat \to Cat

for which the objects of $(\Gamma :C\to G)\circ D$ are pairs $(c,\sigma :\Gamma (c)\to \mathrm{Ob}(D)\cup \mathrm{Ob}(D^{\mathrm{op}}))$ where $c$ is an object of $C$ and $\sigma$ is a lift of $\mathrm{sign}:\Gamma (c)\to \{+,-\}$ through the function

$$!\cup !:\mathrm{Ob}(D)\cup \mathrm{Ob}(D^{\mathrm{op}})\to \{+\}\cup \{-\}=\{+,-\}$$! \cup !: Ob(D) \cup Ob(D^{op}) \to \{+\} \cup \{-\} = \{+, -\}

Morphisms of $(\Gamma :C\to G)\circ D$ are pairs $(f:c\to c\prime ,\varphi :\Gamma (f)\to U(D))$ where $\varphi$ is a morphism of directed graphs to the underlying graph of $D$. Again, this action $\circ$ lifts to a monoidal product

$$\circ :(\mathrm{Cat}/G)\prime \times (\mathrm{Cat}/G)\prime \to (\mathrm{Cat}/G)\prime$$\circ: (Cat/\mathbf{G})' \times (Cat/\mathbf{G})' \to (Cat/\mathbf{G})'

with monoidal unit $I:1\to G$ naming the 1-point set, positively signed. The action of $(\mathrm{Cat}/G)\prime$ on $\mathrm{Cat}$ becomes an actegory with respect to the monoidal category structure.

Definition: A club over $G$ is a monoid in the monoidal category $((\mathrm{Cat}/G)\prime ,\circ ,I)$.

A club over $G$ induces (via the actegory structure) a monad on $\mathrm{Cat}$, and an algebra over the club is an algebra for this monad.

• The monad on $\mathrm{Cat}$ induced by a club over $G$ is not a 2-monad, but it does give a 2-monad if one restricts to the locally groupoidal 2-category of categories, functors, and natural isomorphisms.

Clubs over $G$ are not however examples of generalized operads over a cartesian monad.