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)F(C) with respect to the monad, it frequently suffices to describe the free algebra F(1)F(1) on the terminal category, and then a certain “categorical wreath product” gives the free algebra on CC:

F(C)F(1)CF(C) \cong F(1) \wr 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ηc *cε11 \stackrel{\eta}{\to} c^* \otimes c \stackrel{\varepsilon}{\to} 1

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

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\mathbf{P} below by a category G\mathbf{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\mathbf{G} have a “defined” composition if no islands are produced, else their composition is taken to be the basepoint. Now let F(1)F(1) be the free smc category on one generator. There is a “graph functor” Γ:F(1)G\Gamma: F(1) \to \mathbf{G} which takes a morphism of F(1)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 CC, the free smc category F(C)F(C) has the expected objects given by formal iterated applications of hom and tensor to objects of CC. A morphism is given by a morphism of F(1)F(1) together with a labeling of the oriented edges of its underlying graph (an oriented 1-cobordism) by morphisms of CC. Then, you compose morphisms of this “categorical 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 CatCat, 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 CatCat?

Todd Trimble: I’m pretty sure that it’s a cartesian monad on CatCat, 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\mathbf{P} be the category of finite sets [n]={1,,n}[n] = \{1, \ldots, n\} (including the empty set [0][0]) and permutations between them, and let CatCat be the category of small categories. We define a “wreath product” action of the category Cat/PCat/\mathbf{P} on CatCat, where Cat/PCat/\mathbf{P} is the slice category of CatCat over P\mathbf{P}

:Cat/P×CatCat\circ: Cat/\mathbf{P} \times Cat \to Cat

taking a pair (Γ:CP,D)(\Gamma: C \to \mathbf{P}, D) to the category whose objects are tuples

(c;d 1,,d n)(c; d_1, \ldots, d_n)

with cOb(C)c \in Ob(C), d iOb(D)d_i \in Ob(D), and Γ(c)=[n]\Gamma(c) = [n]. A morphism is a tuple

(f;g 1,,g n)(f; g_1, \ldots, g_n)

consisting of a morphism f:ccf: c \to c' in CC and morphisms g i:d id Γ(f)(i)g_i: d_i \to d_{\Gamma(f)(i)}' in DD, composed in the obvious way.

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

GH=GH nG \int H = G \ltimes H^n

with the action of GG on H nH^n induced from the action on [n][n].

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

ΓD SD S! C Γ S1 =P\array{\Gamma \circ D & \overset{}{\to} & S D\\ \downarrow && \downarrow^{S !}\\ C & \underset{\Gamma}{\to} & S 1 & = \mathbf{P}}

See below for a general version of this construction.

Substitution product as monoidal product

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

:Cat/P×Cat/PCat/P\circ: Cat/\mathbf{P} \times Cat/\mathbf{P} \to Cat/\mathbf{P}

To start, given a pair (Γ:CP,Δ:DP)(\Gamma: C \to \mathbf{P}, \Delta: D \to \mathbf{P}), the domain of ΓΔ\Gamma \circ \Delta is the category ΓD\Gamma \circ D described above. The functor

ΓΔ:ΓDP\Gamma \circ \Delta: \Gamma \circ D \to \mathbf{P}

sends an object (c;d 1,,d n)(c; d_1, \ldots, d_n) to iΔ(d i)\sum_i \Delta(d_i).

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

μ(n;k 1,,k n):Lin(n)×Lin(k 1)××Lin(k n)Lin(k 1++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 nn linearly ordered sets of and produces the evident linear ordering on the disjoint sum of the sets.

Then, given a morphism (f;g 1,,g n)(f; g_1, \ldots, g_n) in ΓD\Gamma \circ D, we define

(ΓΔ)(f;g 1,,g n)=defμ(n;k 1,,k n)(Γ(f),Δ(g 1),Δ(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 TT, the functor ΓΔ\Gamma \circ \Delta can be described as the composite

ΓDTDTΔTT1μ 1T1=P \Gamma \circ D \to T D \overset{T \Delta}{\to} T T 1 \overset{\mu_1}{\to} T 1 = \mathbf{P}

where μ:TTT\mu\colon T T \to T is the multiplication of the monad TT.

The substitution product thus indicated,

:Cat/P×Cat/PCat/P,\circ: Cat/\mathbf{P} \times Cat/\mathbf{P} \to Cat/\mathbf{P},

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

Cat/PCat/(1×T1)Span(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 Span(Cat) TSpan(Cat)_T.

Under this monoidal product, the substitution action indicated earlier,

:Cat/P×CatCat,\circ: Cat/\mathbf{P} \times Cat \to Cat,

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

(ΓΔ)EΓ(ΔE)(\Gamma \circ \Delta) \circ E \cong \Gamma \circ (\Delta \circ E)

for Γ:CP\Gamma: C \to \mathbf{P}, Δ:DP\Delta: D \to \mathbf{P}, and a category EE, and similarly coherent left and right unit isomorphisms.

Clubs over P\mathbf{P}

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

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

Given a club structure on Γ:CP\Gamma: C \to \mathbf{P}, we think of the objects cc as formal operations of arity n=Γ(c)n = \Gamma(c). An algebra DD over CC, m:CDDm: C \circ D \to D, gives in effect an interpretation of each cc of arity nn as an actual operation D nDD^n \to D.

The free CC-algebra over a category DD is just CDC \circ D. For the free algebra over the terminal category 11, notice that

C1CC \circ 1 \cong C

(strictly speaking, the CC on the left is a category over P\mathbf{P} and the CC on the right is just the category). Thus, in a manner of speaking, the free algebra generated by DD is obtained by wreathing the free algebra generated by 11 with DD, as adumbrated in the idea section above.


  • The identity 1 P:PP1_{\mathbf{P}}: \mathbf{P} \to \mathbf{P} carries a club structure. The multiplication μ\mu of the club, on the object level, is given by the assignment

    (n;k 1,,k n)k 1++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 Aut(n)=Lin(n)Aut(n) = Lin(n) discussed above. Algebras over this club are symmetric (strict) monoidal categories. Algebras in the “pseudo” sense over the induced 2-monad on CatCat are symmetric monoidal categories. Alternatively, if F(1)F(1) is the free symmetric monoidal category on one generator, then the symmetric monoidal equivalence Γ:F(1)P\Gamma: F(1) \to \mathbf{P} carries a club structure whose strict algebras are symmetric monoidal categories.

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

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

Clubs over cartesian monads

The foregoing construction can be generalized to any cartesian monad SS on CatCat. Since a monad is a monoid in the monoidal category of endofunctors, the slice category [Cat,Cat]/S[Cat,Cat]/S inherits a monoidal structure. We also have an “evaluate at 11” functor [Cat,Cat]/SCat/S1[Cat,Cat]/S \to Cat/S1, which has a right adjoint defined by pulling back: given AS1A\to S1, we define an endofunctor A^\hat{A} of CatCat by the following pullbacks:

A^(X) A S(X) S(1) \array{ \hat{A}(X) & \to & A \\ \downarrow && \downarrow\\ S(X) & \to & S(1) }

This right adjoint is fully faithful and embeds Cat/S1Cat/S1 into [Cat,Cat]/S[Cat,Cat]/S as the endofunctors equipped with a cartesian natural transformation to SS. Finally, the cartesianness of SS implies that Cat/S1Cat/S1 is closed under the monoidal structure of [Cat,Cat]/S[Cat,Cat]/S. This induced monoidal structure on Cat/S1Cat/S1 is, in the case when SS is the symmetric strict monoidal category monad, exactly the substitution product defined above. Thus, a club is a monoid for this monoidal structure, and the inclusion of Cat/S1Cat/S1 into [Cat,Cat]/S[Cat,Cat]/S thereby sends it to a monad over SS.

Note, however, that this construction depends on no special features of CatCat; it can be performed for any cartesian monad SS on any category with finite limits. This can be found in (Kelly, Clubs and datatype constructors). More generally, it can be performed for cartesian monads in a suitable 2-category; see club in a 2-category.

Clubs over finite sets

(To be written…)

Clubs of mixed variance

The clubs described in the preceding two sections are examples of covariant clubs: the operations on their algebras DD are covariant functors D nDD^n \to D. However, many doctrines on CatCat, 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

ev X,Y:[X,Y]XYev_{X, Y}: [X, Y] \otimes X \to Y

which is dinatural in XX and natural in YY.

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,,n}\{1, 2, \ldots, n\} where a sign ++ or - is assigned to each element jj. The element jj is given the sign ++ (resp., -) if j thj^{th} argument of the operation appears covariantly (resp., contravariantly). For example, for the operation

C op×C×CC:(a,b,c)[a,b]cC^{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 AA, BB called a graph (or EKM graph, for Eilenberg, Kelly and Mac Lane), which by definition is a partition of the signed elements of ABA \cup B into mated pairs, such that

  • Mated elements, one in AA and one in BB, have the same sign;

  • Mated elements, both in AA or both in BB, have opposite signs.

An EKM graph may be identified with a directed graph whose edges are mated pairs, oriented in the direction from an AA-element to a BB-element if the mates have the same sign, or from ++ to - if the mates are AA-elements, or from - to ++ if the mates are BB-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,

ev X,Y:[X,Y]XYev_{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ηc *cε11 \stackrel{\eta}{\to} c^* \otimes c \stackrel{\varepsilon}{\to} 1

where 11 denotes a monoidal unit, η\eta is a unit for an adjunction cc *c \dashv c^*, and ε\varepsilon is a counit for c *cc^* \dashv 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 cc (for example, when interpreted in the compact closed category of finite-dimensional vector spaces, the value is dim(c)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\mathbf{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\mathbf{G} as an ordinary category.

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

:(Cat/G)×CatCat\circ: (Cat/\mathbf{G})' \times Cat \to Cat

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

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

Morphisms of (Γ:CG)D(\Gamma: C \to \mathbf{G}) \circ D are pairs (f:cc,ϕ:Γ(f)U(D))(f: c \to c', \phi: \Gamma(f) \to U(D)) where ϕ\phi is a morphism of directed graphs to the underlying graph of DD. Again, this action \circ lifts to a monoidal product

:(Cat/G)×(Cat/G)(Cat/G)\circ: (Cat/\mathbf{G})' \times (Cat/\mathbf{G})' \to (Cat/\mathbf{G})'

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

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

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

  • The monad on CatCat induced by a club over G\mathbf{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\mathbf{G} are not however examples of generalized operads over a cartesian monad.


  • Max Kelly, On clubs and data-type constructors, Applications of Categories in Computer Science, Proceedings of the London Mathematical Society Symposium, Durham 1991

Revised on August 1, 2016 12:29:22 by Mike Shulman (