symmetric monoidal (∞,1)-category of spectra
A computad is a formal device (due to Ross Street, 1976) for describing “generators” of higher categories, and in particular for -categories. They generalize quivers (directed graphs), which describe generators of ordinary (1-)categories. In a sense, -computads are the “most general” structure from which one can generate a free -category; they allow the free adjoining of -cells whose source and target are arbitrary composites of previously adjoined -cells.
Originally the -categories under consideration were strict, but more recently the concept of -computad has been expanded to take into account weak -categories and other higher-categorical structures. The notion is tied to algebraic senses of higher categories, but computads can also be used as the input for geometric senses as well, and may aid in a comparison between the two approaches.
Each type of higher-categorical structure comes with its own notion of computad. Thus there are computads for strict -categories, computads for weak -categories, computads for double categories, and so on.
First we will define computads relative to an arbitrary globular operad . This reproduces the original strict situation when is the terminal globular operad, whose algebras are strict ω-categories, but it also applies to operads whose algebras are Batanin weak ω-categories. The generalization to the weak case is originally due to Batanin; the following simpler reformulation of it is due to Richard Garner.
Let be a globular operad and let denote the category of -algebras and strict morphisms. Thus if is terminal, then . We denote by the forgetful functor and by its left adjoint, where denotes the category of globular sets. Let denote the -globe and its boundary (which is the pushout of two -globes along their boundaries). These are globular sets and thus they generate free -algebras and .
We now define, recursively in , the category of -computads relative to , together with an adjunction
When , the category is Set, picks out the set of objects, and is its left adjoint, which constructs the free -algebra on a set (considered as a globular set concentrated in degree 0).
If , an n-computad consists of an -computad , a set , and a function
We call the set of n-cells. Note that simply equips each -cell with a pair of parallel -cells in . In fancy language, the category is the comma category , where .
The functor sends a -algebra to the -computad defined by the -computad together with and defined by the following pullback square in Set:
Here the bottom map is induced by the counit of the adjunction , while the right-hand map is induced by the inclusion .
The left adjoint of is defined by taking an -computad to the following pushout in :
Here denotes a copower by a set, the top map is the adjunct of , and the left-hand map is again induced by the inclusion . Adjointness is easy to verify using the universal properties of pullbacks and pushouts.
Finally, the category of -computads is the limit of the diagram
For simplicity, let be the terminal globular operad, such that -algebras are strict ω-categories.
As in the definition, a 0-computad is just a set, and the free 0-category on a 0-computad is just itself, considered as a discrete -category.
A 1-computad consists of 0-computad (i.e. a set) together with another set and a function . Now is just a pair of objects, so this means that each element of is equipped with a pair of elements of , which we call its source and target. Thus a 1-computad is just a quiver.
The free 1-category on a 1-computad is the usual free category on a quiver. That is, its objects are the vertices of the graph and its morphisms are finite composable strings of edges in the quiver.
A 2-computad is given by a quiver together with a set of 2-cells, each equipped with a source and a target which are composable strings of edges in the graph. For example, if the given quiver is a square
then the free category it generates is the free noncommutative square, having two diagonals and . We can then make a 2-computad by adding one 2-cell with source and target . The free 2-category on this 2-computad can then be drawn pictorially as
Any -globular set can be considered as an -computad where for each , the functions land inside . The free -category on this -computad will then agree with the free -category on the -globular set we started with.
The above definition can easily be generalized by replacing the globe category by any direct category, i.e. the opposite of an inverse category. In more detail, let be any inverse category, and consider the diagram category . Then any object has a representable functor defined by , which has a “boundary” subfunctor consisting of all nonidentity morphisms (as varies). These play the role of and above.
Let be a monad on with induced adjunction . Since (by definition of “inverse category”) the objects of have a well-founded relation given by the existence of nonidentity arrows, we will define by well-founded recursion on the category and an adjunction .
Assume, therefore, that this adjunction has been defined for all for which there is any nonidentity morphism . Let be the limit of the for all such , with an induced adjunction to (see below). Now define an -computad to consist of a -computad , a set , and a function
The functor is defined as before: it sends a -algebra to the -computad defined by the -computad together with and defined by the following pullback square in Set:
Similarly, its left adjoint takes an -computad to the following pushout in :
This definition is not quite correct as written, because it assumes in the definition of -computads not just that the categories are defined with adjunctions to , but that they are related by suitable functors as varies that commute with these adjunctions. Thus, formally speaking it has to be phrased as a definition of a functor, rather than a function, by well-founded recursion, as explained here. We leave the details to the reader.
For example, if , where , then there is a monad on whose algebras are double categories, and in this way we can obtain a notion of “double computad”.
The category of computads relative to a globular operad is sometimes a presheaf category, and when it isn’t, it “almost is.” At first glance, it may look as though it should always be a presheaf category, say where is the category of “computopes.” A “computope” is, intuitively, one possible “shape” for an -cell in an -category (i.e. a -algebra). For example, every “globe” is a computope, as is every simplex/oriental, every cube, and so on. It may feel at first as though a computad should be specified by giving a set of cells of each “shape” (i.e. for each computope) related by “face maps,” generalizing globular sets, simplicial sets, cubical sets, and so on.
However, when is the terminal globular operad whose algebras are strict -categories, the presence of identities in the notion of free -category prevents this from quite working, for sort of the same reason that strict n-categories are insufficient for . For instance, there is a 2-computad with one 0-cell , no 1-cells, and two 2-cells and . The source and target of and must then both be the identity 1-cell of . Now in the free 2-category generated by this 2-computad, we have , by the Eckmann-Hilton argument. If we define a 3-computad on top of this 2-computad with a 3-cell whose source (say) is , then there can be no “face” maps from the computope-shape of to the computope-shape of and , since there is no way to distinguish from (i.e. neither one is the “first” or the “second”).
This argument only kicks in for , so the categories of 0-computads, 1-computads, and 2-computads are presheaf categories. Moreover, the problem can also be avoided if is “suitably weak.” To define what this means, one considers the “slices” of the operad . By truncation, any such induces a monad on the category of -globular sets. Now the full subcategory of on the objects whose underlying globular set is -terminal (i.e. terminal in degrees ) is monadic over the category of sets; the resulting monad on Set is called the -slice of . In Theorem 5.2 of Computads and slices of operads, Batanin shows that the category of -computads of a Batanin-operad is a presheaf category if the -slices of are strongly regular theories? for all . This applies in particular to the case where is an operad for Batanin weak -categories.
On the other hand, even in the strict case we can obtain presheaf categories of suitably restricted computads. For instance, if we consider only “many-to-one” computads in which the target of each -cell consists of exactly one -cell (rather than a free composite of such), we obtain a presheaf category, which is in fact equivalent to the category of opetopic sets.
The adjunction should be monadic, at least in good cases. However, it is not clear to the author of this page whether or where a correct proof of this fact appears in the literature for any value of .
Quite generally, computads can be used to describe cofibrant replacements. Specifically, the -categories freely generated by computads are precisely the cofibrant objects in the canonical model structure on strict ω-categories. This is discussed in
The cofibrant resolution given by Métayer in these articles is the one counit of the adjunction . In particular, this implies that every strict ω-category is equivalent as an -category to one that is freely generated by a computad. (Notice that these articles say “polygraph” for “computad”, following Burroni).
It is to be expected that similar results are true for Batanin weak -categories, defined as algebras for some other “contractible” globular operad .
Moreover, for any globular operad , one can show that the “cofibrant replacement” obtained as above from the adjunction is the same as the “canonical” cofibrant replacement comonad obtained from the algebraic weak factorization system on generated by the boundary inclusions . This is proven in
In particular, the Kleisli category of this comonad is a good candidate for the category of weak functors between Batanin weak -categories.
2-computads were originally defined by Ross Street in the paper
The goal there was to describe which 2-categories are “finitely presented” (the presentation being given by a 2-computad) in order to describe the correct notion of “finite 2-limit”.
Makkai, Harnik, and Zawadowski, Multitopic sets are the same as many-to-one computads, link.
Makkai, The word problem for computads, link.
The following more recent papers are referred to above:
One should beware that there are some erroneous claims in some of Batanin’s papers; in particular the claim that computads relative to a globular operad are always a presheaf category. This was explicitly shown to be false in
Michael Makkai and Marek Zawadowski, The category of 3-computads is not cartesian closed, MR.
Finally, we had some blog discussion about this at