A club is a particular sort of doctrine or monad on categories, one which encapsulates the following frequently observed phenomenon: to describe free algebras with respect to the monad, it frequently suffices to describe the free algebra on the terminal category, and then a certain “categorical wreath product” gives the free algebra on :
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.
Clubs were introduced by Max Kelly in a series of papers (see references), and are akin in spirit to operads. In fact, many (perhaps even all) types of clubs are a special case of generalized operads, and also of polynomial monads.
This is the most basic sort of club, introduced by Kelly in MVFC and AAC.
Let be the category of finite sets (including the empty set ) and permutations between them, and let be the category of small categories. We define a “wreath product” action of the category on , where is the slice category of over
taking a pair to the category whose objects are tuples
with , , and . A morphism is a tuple
consisting of a morphism in and morphisms in , composed in the obvious way.
This generalizes the standard notion of wreath product: given a group and a permutation representation, i.e., a homomorphism , and given a group , the wreath product is defined to be the semidirect product
with the action of on induced from the action on .
Another, more abstract, way to describe this substitution product is as follows: there is a cartesian monad on whose algebras are symmetric strict monoidal categories, and we have , where is the terminal category. The substitution product can then be described as the following pullback in .
See below for a general version of this construction.
We describe how the substitution action lifts to a self-action denoted by the same symbol:
To start, given a pair , the domain of is the category described above. The functor
sends an object to .
The effect of on morphisms may be summarized as “substituting the permutations into the permutation ”. To describe this more precisely, we give a little preface. The hom-set of permutations on may be identified with the set of total (or linear) orders on , if we identify the identity element with the standard order on . The sets are components of an operad where the operadic multiplication
takes a linear ordering of linearly ordered sets and produces the evident linear ordering on the disjoint sum of the sets.
Then, given a morphism in , we define
Given the abstract description above of the substitution product in terms of the cartesian monad , the functor can be described as the composite
where is the multiplication of the monad .
The substitution product thus indicated,
is the product for a monoidal category structure on . The monoidal unit is the functor which names the 1-element set. Abstractly, we can observe that the cartesian monad induces a pseudomonad on the bicategory of spans in , which has a Kleisli bicategory in which a 1-cell is a span in . We then have
and the monoidal structure above is that induced from the bicategory composition in .
Under this monoidal product, the substitution action indicated earlier,
carries a structure of actegory over the monoidal category , in the sense that there is a coherent associativity
for , , and a category , and similarly coherent left and right unit isomorphisms.
A club over is a monoid in the monoidal category . By the abstract characterization above, this is equivalent to a monad in the bicategory on the object , or equivalently a -operad in the sense of Leinster.
A club over induces (via the actegory structure) a 2-monad on , and an algebra over the club is an algebra for this monad. That is, an algebra over a club is a category together with an action compatible in the usual way with the monoid structure on .
Given a club structure on , we think of the objects as formal operations of arity . An algebra over , , gives in effect an interpretation of each of arity as an actual operation .
The free -algebra over a category is just . For the free algebra over the terminal category , notice that
(strictly speaking, the on the left is a category over and the on the right is just the category). Thus, in a manner of speaking, the free algebra generated by is obtained by wreathing the free algebra generated by with , as adumbrated in the idea section above.
The identity carries a club structure. The multiplication of the club, on the object level, is given by the assignment
and on morphisms, it is given by the operad structure on discussed above. Algebras over this club are symmetric strict monoidal categories. Algebras in the “pseudo” sense over the induced 2-monad on are unbiased non-strict symmetric monoidal categories. Alternatively, if is the free (biased, non-strict) symmetric monoidal category on one generator, then the symmetric monoidal equivalence carries a club structure whose strict algebras are (biased, non-strict) symmetric monoidal categories.
Let be the braid category, equipped with the usual forgetful functor . The club multiplication, at the level of morphisms, is “substitution” of braids into a braid on elements. Pseudo-algebras over the induced 2-monad on are unbiased braided monoidal categories. Alternatively, as in the previous example, biased non-strict braided monoidal categories are also strict algebras over a club of the form where is the free braided monoidal category on one generator.
Let be any (permutative) operad valued in , with underlying species . The category of elements gives a functor , and this carries a club structure induced from the operad structure on . In this way, clubs generalize operads. In fact, operads in can be identified with those clubs for which the functor is a discrete fibration.
Essentially the same construction can be given replacing by (a skeleton of) the category of finite sets and functions, or its opposite. The corresponding cartesian monads are those whose algebras are categories with strictly associative finite coproducts or strictly associative finite products, respectively. Examples of such clubs include categories with (not necessarily strictly associative) finite coproducts or products. Clubs of this sort were also defined in MVFC and AAC, and studied further in OCD.
In fact, the foregoing constructions can be generalized to any cartesian monad on . Since a monad is a monoid in the monoidal category of endofunctors, the slice category inherits a monoidal structure. We also have an “evaluate at ” functor , which has a right adjoint defined by pulling back: given , we define an endofunctor of by the following pullbacks:
This right adjoint is fully faithful and embeds into as the endofunctors equipped with a cartesian natural transformation to . Finally, the cartesianness of implies that is closed under the monoidal structure of . This induced monoidal structure on is, in the case when 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 into thereby sends it to a monad over .
Note, however, that this construction depends on no special features of ; it can be performed for any cartesian monad on any category with finite limits. This generalization was performed by Kelly in CDT. More generally, it can be performed for cartesian monads in a suitable 2-category; see club in a 2-category.
To describe structures on a family of categories rather than a single category (such as a monoidal functor between two monoidal categories), we can generalize to for any set . In this case the substitution monoidal product lives on . This generalization can also be found in MVFC and AAC; it amounts to nothing more than considering generalized multicategories for a cartesian monad (with a discrete category of objects) rather than simply generalized operads (those with the terminal category of objects).
In CDT Kelly described a further generalization of clubs over , in which is replaced by . The crucial feature that allows the substitution product to continue working is the Grothendieck construction for functors into . In fact, Kelly generalized even further to a substitution product that lives not on the ordinary slice category but on the lax slice 2-category (which Kelly denoted ). This has the advantage that the resulting functor from clubs to monads on is fully faithful, which it is not for the previous notions of club.
There is an analogous generalization of the many-object case, though Kelly did not make this explicit. Similarly, there is a dual notion of club in which generalizes clubs over .
Kelly did not give any interesting examples of clubs in this generality, only remarking that one is “ineluctably led to” the generalization. But also worth noting is that there could be interesting morphisms between clubs over that are only visible when they are viewed as clubs in (or equivalently as monads on ).
The cartesian monads that are used to define clubs over , , and are in fact polynomial monads (which immediately implies that they are cartesian). And an endofunctor equipped with a cartesian natural transformation to a polynomial functor is itself automatically polynomial. Thus, the subcategory of identified with by the “clubs over cartesian monads” construction is equivalently the category of polynomial endofunctors of cartesianly-over , and the identification with reduces to the identification of cartesian morphisms between polynomial functors with pullback squares of exponentiable morphisms. Similarly, considering cartesian natural transformations in the double category of polynomial functors yields a description of clubs with many objects.
This suggests that an arbitrary polynomial monad could be regarded as a “global club”, i.e. one not “over any base”. A polynomial endofunctor of is determined by a single exponentiable morphism in , i.e. a Conduche functor, which in turn is determined by a pseudofunctor Prof. Composition of polynomial endofunctors thus yields a monoidal structure on the “slice category” whose objects are categories equipped with a pseudofunctor to , monoids with respect to which are polynomial monads; thus a polynomial monad could be viewed as a “club over ”. Clubs in and are the obvious special cases when and are embedded into by representable and corepresentable profunctors and the pseudofunctor is strict; these correspond to polynomial endofunctors for which is a split opfibration or split fibration respectively.
Finally, recall that non-cartesian natural transformations between polynomial functors determined by and have a similar description as consisting of a map and a map over . Translated into the classifying maps and this corresponds to a triangle filled by a lax natural transformation whose components are functors. Thus in the cases of split (op)fibrations we recover Kelly’s lax slice 2-categories and .
The clubs described in the preceding sections are all examples of covariant clubs: the operations on their algebras are covariant functors . However, many doctrines on , 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
which is dinatural in and natural in .
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.
The underlying arity of an operation of mixed variance will be a signed set, i.e., a finite set where a sign or is assigned to each element . The element is given the sign (resp., ) if argument of the operation appears covariantly (resp., contravariantly). For example, for the operation
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 , called a graph (or EKM graph, for Eilenberg, Kelly and Mac Lane), which by definition is a partition of the signed elements of into mated pairs, such that
Mated elements, one in and one in , have the same sign;
Mated elements, both in or both in , have opposite signs.
An EKM graph may be identified with a directed graph whose edges are mated pairs, oriented in the direction from an -element to a -element if the mates have the same sign, or from to if the mates are -elements, or from to if the mates are -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,
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.
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
where denotes a monoidal unit, is a unit for an adjunction , and is a counit for (in a symmetric monoidal category, such adjunctions are inevitably ambidextrous).
This composition obviously does not define an extranatural transformation from a constant functor to itself, precisely because of dependence on (for example, when interpreted in the compact closed category of finite-dimensional vector spaces, the value is ). 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).
Let 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 as an ordinary category.
Let be the full subcategory of whose objects are functors such that for every morphism of , is not the basepoint of the hom-set it belongs to. There is an action
for which the objects of are pairs where is an object of and is a lift of through the function
Morphisms of are pairs where is a morphism of directed graphs to the underlying graph of . Again, this action lifts to a monoidal product
with monoidal unit naming the 1-point set, positively signed. The action of on becomes an actegory with respect to the monoidal category structure.
A club over is a monoid in the monoidal category .
A club over induces (via the actegory structure) a monad on , and an algebra over the club is an algebra for this monad. Unlike in the covariant cases, this monad 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.
As shown above, we cannot expect to describe compact closed categories with a club. However, we can describe various other structures of mixed variance, such as symmetric monoidal closed categories. Specifically, let be the free smc category on one generator. There is a “graph functor” which takes a morphism of to its extranaturality graph. The crucial observation is that no basepoint morphism lies in the image of , i.e., no islands can occur in formal compositions for this doctrine. This fact is nontrivial; its proof relies on a cut-elimination theorem (see KellyCET) and works for any structure obtained by adding multi-variable right adjoints to any of the operations of a club over .
A morphism in the free symmetric monoidal closed category on a category is then given by a morphism of together with a labeling of the oriented edges of its underlying graph (an oriented 1-cobordism) by morphisms of . 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.
Last revised on July 2, 2024 at 15:25:34. See the history of this page for a list of all contributions to it.