nLab computad

Redirected from "polygraph".
Contents

Context

Higher category theory

higher category theory

Basic concepts

Basic theorems

Applications

Models

Morphisms

Functors

Universal constructions

Extra properties and structure

1-categorical presentations

Higher algebra

Contents

Idea

A computad is a formal device (due to Ross Street, 1976) for describing “generators” of higher categories, and in particular for nn-categories. They generalize quivers (directed graphs), which describe generators of ordinary (1-)categories. In a sense, nn-computads are the “most general” structure from which one can generate a free nn-category; they allow the free adjoining of kk-cells whose source and target are arbitrary composites of previously adjoined (k1)(k-1)-cells.

Originally the nn-categories under consideration were strict, but more recently the concept of nn-computad has been expanded to take into account weak nn-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.

Computads are also called polygraphs, following Burroni; this term is especially used in parts of the literature related to rewriting theory.

Definition

Each type of higher-categorical structure comes with its own notion of computad. Thus there are computads for strict nn-categories, computads for weak nn-categories, computads for double categories, and so on.

Globular computads

First we will define computads relative to an arbitrary globular operad PP. This reproduces the original strict situation when PP is the terminal globular operad, whose algebras are strict ∞-categories, but it also applies to operads PP 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 PP be a globular operad and let PAlgP Alg denote the category of PP-algebras and strict morphisms. Thus if PP is terminal, then PAlg=StrωCatP Alg = Str \omega Cat. We denote by U PU_P the forgetful functor PAlgGSetP Alg \to GSet and by F PF_P its left adjoint, where GSetGSet denotes the category of globular sets. Let 2 n2_n denote the nn-globe and n\partial_n its boundary (which is the pushout of two (n1)(n-1)-globes along their boundaries). These are globular sets and thus they generate free PP-algebras F P2 nF_P 2_n and F P nF_P \partial_n.

We now define, recursively in nn, the category nCptd Pn Cptd_P of nn-computads relative to PP, together with an adjunction

nCptd PU nF nPAlg. n Cptd_P \underoverset{U_n}{F_n}{\rightleftarrows} P Alg .
  • When n=0n=0, the category (1)Cptd P(-1) Cptd_P is Set, U 0:PAlgSetU_0\colon P Alg \to Set picks out the set of objects, and F 0F_0 is its left adjoint, which constructs the free PP-algebra on a set (considered as a globular set concentrated in degree 0).

  • If n>0n\gt 0, an n-computad consists of an (n1)(n-1)-computad CC, a set XX, and a function

    x:XPAlg(F P n,F n1C)=GSet( n,U PF n1C).x\colon X\to P Alg(F_P \partial_n, F_{n-1} C) = GSet(\partial_n, U_P F_{n-1} C).

    We call XX the set of n-cells. Note that xx simply equips each nn-cell with a pair of parallel (n1)(n-1)-cells in F n1CF_{n-1} C. In fancy language, the category nCptd Pn Cptd_P is the comma category Set/B nSet / B_n, where B n=PAlg(F P n,F n1)B_n = P Alg(F_P \partial_n, F_{n-1} -).

  • The functor U n:PAlgnCptd PU_n\colon P Alg \to n Cptd_P sends a PP-algebra AA to the nn-computad defined by the (n1)(n-1)-computad U n1AU_{n-1} A together with XX and xx defined by the following pullback square in Set:

    X PAlg(F P2 n,A) x PAlg(F P n,F n1U n1A) PAlg(F P n,A)\array{X & \overset{}{\to} & P Alg(F_P 2_n, A)\\ ^x \downarrow && \downarrow\\ P Alg(F_P \partial_n, F_{n-1} U_{n-1} A) & \underset{}{\to} & P Alg(F_P \partial_n, A)}

    Here the bottom map is induced by the counit of the adjunction F n1U n1F_{n-1}\dashv U_{n-1}, while the right-hand map is induced by the inclusion n2 n\partial_n \hookrightarrow 2_n.

  • The left adjoint F nF_n of U nU_n is defined by taking an nn-computad D=(C,X,x)D = (C,X,x) to the following pushout in PAlgP Alg:

    XF P n x¯ F n1C XF P2 n F nD\array{X\cdot F_P \partial_n & \overset{\overline{x}}{\to} & F_{n-1} C\\ \downarrow && \downarrow\\ X \cdot F_P 2_n & \underset{}{\to} & F_n D}

    Here \cdot denotes a copower by a set, the top map x¯\overline{x} is the adjunct of xx, and the left-hand map is again induced by the inclusion n2 n\partial_n \hookrightarrow 2_n. Adjointness is easy to verify using the universal properties of pullbacks and pushouts.

Finally, the category ωCptd P\omega Cptd_P of ω\omega-computads is the limit of the diagram

2Cptd P1Cptd P0Cptd P(1)Cptd P \dots \to 2 Cptd_P \to 1 Cptd_P \to 0 Cptd_P \to (-1) Cptd_P

consisting of the functors nCptd P(n1)Cptd Pn Cptd_P \to (n-1)Cptd_P taking (C,X,x)(C,X,x) to CC. The functors U nU_n form a cone over this diagram and thus induce a functor U ω:PAlgωCptd PU_\omega\colon P Alg \to \omega Cptd_P, which is easily seen to have a left adjoint which takes an object (C n)(C_n) of ωCptd P\omega Cptd_P to the colimit

F 1C 1F 0C 0F 1C 1F 2C 2. F_{-1} C_{-1} \to F_0 C_0 \to F_1 C_1 \to F_2 C_2 \to \dots.

Examples

For simplicity, let PP be the terminal globular operad, such that PP-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 ω\omega-category.

  • A 1-computad consists of 0-computad CC (i.e. a set) together with another set XX and a function XGSet( 1,U PF 0C)X\to GSet(\partial_1, U_P F_0 C). Now 1\partial_1 is just a pair of objects, so this means that each element of XX is equipped with a pair of elements of CC, 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 C 2C_2 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

    f h k g \array{\bullet & \overset{f}{\to} & \bullet \\ ^h\downarrow && \downarrow^k\\ \bullet& \underset{g}{\to} & \bullet}

    then the free category it generates is the free noncommutative square, having two diagonals kfk f and ghg h. We can then make a 2-computad by adding one 2-cell α\alpha with source kfk f and target ghg h. The free 2-category on this 2-computad can then be drawn pictorially as

    f h α k g \array{\bullet & \overset{f}{\to} & \bullet\\ ^h\downarrow & \swarrow_\alpha & \downarrow^k\\ \bullet & \underset{g}{\to} & \bullet}
  • Any nn-globular set can be considered as an nn-computad where for each nn, the functions s,t:C nF n1(𝒞) n1s, t: C_n \rightrightarrows F_{n-1}(\mathcal{C})_{n-1} land inside C n1C_{n-1}. The free nn-category on this nn-computad will then agree with the free nn-category on the nn-globular set we started with.

  • Every oriental can be presented by a computad, as can every opetope, cube, as can most other geometric shapes for higher structures.

On inverse diagrams

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 \mathcal{I} be any inverse category, and consider the diagram category Set \Set^{\mathcal{I}}. Then any object nn\in \mathcal{I} has a representable functor Y nSet Y_n\in \Set^{\mathcal{I}} defined by Y n(x)=(n,x)Y_n(x) = \mathcal{I}(n,x), which has a “boundary” subfunctor nY n\partial_n \subset Y_n consisting of all nonidentity morphisms nxn\to x (as xx varies). These play the role of 2 n2_n and n\partial_n above.

Let PP be a monad on Set \Set^{\mathcal{I}} with induced adjunction F P:Set PAlg:U PF_P : \Set^{\mathcal{I}} \rightleftarrows P Alg : U_P. Since (by definition of “inverse category”) the objects of \mathcal{I} have a well-founded relation given by the existence of nonidentity arrows, we will define by well-founded recursion on nn\in \mathcal{I} the category nCptd Pn Cptd_P and an adjunction nCptd PU nF nPAlg n Cptd_P \underoverset{U_n}{F_n}{\rightleftarrows} P Alg .

Assume, therefore, that this adjunction has been defined for all kk for which there is any nonidentity morphism nkn\to k. Let (<n)Cptd P(\lt n) Cptd_P be the limit of the kCptd Pk Cptd_P for all such kk, with an induced adjunction F <nU <nF_{\lt n} \dashv U_{\lt n} to PAlgP Alg (see below). Now define an nn-computad to consist of a (<n)(\lt n)-computad CC, a set XX, and a function

x:XPAlg(F P n,F <nC)=Set ( n,U PF <nC).x\colon X\to P Alg(F_P \partial_n, F_{\lt n} C) = Set^{\mathcal{I}}(\partial_n, U_P F_{\lt n} C).

The functor U n:PAlgnCptd PU_n\colon P Alg \to n Cptd_P is defined as before: it sends a PP-algebra AA to the nn-computad defined by the (<n)(\lt n)-computad U <nAU_{\lt n} A together with XX and xx defined by the following pullback square in Set:

X PAlg(F PY n,A) x PAlg(F P n,F <nU <nA) PAlg(F P n,A)\array{X & \overset{}{\to} & P Alg(F_P Y_n, A)\\ ^x \downarrow && \downarrow\\ P Alg(F_P \partial_n, F_{\lt n} U_{\lt n} A) & \underset{}{\to} & P Alg(F_P \partial_n, A)}

Similarly, its left adjoint F nF_n takes an nn-computad D=(C,X,x)D = (C,X,x) to the following pushout in PAlgP Alg:

XF P n x¯ F <nC XF PY n F nD\array{X\cdot F_P \partial_n & \overset{\overline{x}}{\to} & F_{\lt n} C\\ \downarrow && \downarrow\\ X \cdot F_P Y_n & \underset{}{\to} & F_n D}

This definition is not quite correct as written, because it assumes in the definition of (<n)(\lt n)-computads not just that the categories kCptd Pk Cptd_P are defined with adjunctions to PAlgP Alg, but that they are related by suitable functors as kk 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 =𝒫×𝒫\mathcal{I} = \mathcal{P}\times \mathcal{P}, where 𝒫=(10)\mathcal{P} = (1 \rightrightarrows 0), then there is a monad on Set Set^{\mathcal{I}} whose algebras are double categories, and in this way we can obtain a notion of “double computad”.

Computads, presheaves and opetopes

The category of computads relative to a globular operad PP 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 Set Ctp opSet^{Ctp^{op}} where CtpCtp is the category of “computopes.” A “computope” is, intuitively, one possible “shape” for an nn-cell in an nn-category (i.e. a PP-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 PP is the terminal globular operad whose algebras are strict ω\omega-categories, the presence of identities in the notion of free nn-category prevents this from quite working, for sort of the same reason that strict n-categories are insufficient for n>2n\gt 2. For instance, there is a 2-computad with one 0-cell xx, no 1-cells, and two 2-cells α\alpha and β\beta. The source and target of α\alpha and β\beta must then both be the identity 1-cell id xid_x of xx. Now in the free 2-category generated by this 2-computad, we have βα=αβ\beta\alpha = \alpha\beta, by the Eckmann-Hilton argument. If we define a 3-computad on top of this 2-computad with a 3-cell μ\mu whose source (say) is βα=αβ\beta\alpha = \alpha\beta, then there can be no “face” maps from the computope-shape of μ\mu to the computope-shape of β\beta and α\alpha, since there is no way to distinguish α\alpha from β\beta (i.e. neither one is the “first” or the “second”).

This argument only kicks in for n3n\ge 3, so the categories of 0-computads, 1-computads, and 2-computads are presheaf categories. Moreover, the problem can also be avoided if PP is “suitably weak.” To define what this means, one considers the “slices” of the operad PP. By truncation, any such PP induces a monad P kP_k on the category of kk-globular sets. Now the full subcategory of P nAlgP_n Alg on the objects whose underlying globular set is (n1)(n-1)-terminal (i.e. terminal in degrees <n\lt n) is monadic over the category of sets; the resulting monad on Set is called the kk-slice of PP. In Theorem 5.2 of Computads and slices of operads, Batanin shows that the category of nn-computads of a Batanin-operad PP is a presheaf category if the kk-slices of PP are strongly regular theories? for all 0kn10\leq k \leq n-1. This applies in particular to the case where PP is an operad for Batanin weak ω\omega-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 nn-cell consists of exactly one (n1)(n-1)-cell (rather than a free composite of such), we obtain a presheaf category, which is in fact equivalent to the category of opetopic sets. We also obtain a presheaf category if we restrict both source and target to not be identity arrows; see Henry 2017.

Monadicity

The monadicity of ωCptd\omega Cptd over ωCat\omega Cat was first claimed by Batanin in his ‘98 paper. The proof however made use of the fact that ωCptd\omega Cptd was a category of presheaves, which was later found to be false. Métayer provided a corrected proof in

Computads as cofibrant resolutions

Quite generally, computads can be used to describe cofibrant replacements. Specifically, the ω\omega-categories freely generated by computads are precisely the cofibrant objects in the canonical model structure on strict ∞-categories. This is discussed in

  • F. Métayer, Cofibrant complexes are free (arXiv)

  • F. Métayer, Resolutions by polygraphs (tac)

The cofibrant resolution () cofId:ωCatωCat(-)_{cof} \to Id : \omega Cat \to \omega Cat given by Métayer in these articles is the one counit of the adjunction ωCptdωCat\omega Cptd \to \omega Cat. In particular, this implies that every strict ∞-category is equivalent as an ω\omega-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 ω\omega-categories, defined as algebras for some other “contractible” globular operad PP.

Moreover, for any globular operad PP, one can show that the “cofibrant replacement” obtained as above from the adjunction ωCptd PPAlg\omega Cptd_P \rightleftarrows P Alg is the same as the “canonical” cofibrant replacement comonad obtained from the algebraic weak factorization system on PAlgP Alg generated by the boundary inclusions F P nF P2 nF_P \partial_n \to F_P 2_n. 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 ω\omega-categories.

References

2-computads were originally defined by Ross Street in the paper

  • Ross Street, Limits indexed by category-valued 2-functors.

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”.

I don’t know the first use of “nn-computads,” but Michael Makkai has studied them as a way to define opetopic sets, and shown that they are “almost” but not quite a presheaf category:

  • Makkai, Harnik, and Zawadowski, Multitopic sets are the same as many-to-one computads, link.

  • Makkai, The word problem for computads, link.

Computads were studied by Burroni under the name “polygraph” in the framework of rewriting:

  • Albert Burroni, Higher dimensional word problems with applications to equational logic (pdf)

The following more recent papers are referred to above:

Disucssion of computads as inductive types:

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

Some blog discussion:

Last revised on June 12, 2024 at 09:53:28. See the history of this page for a list of all contributions to it.