nLab
computad

Idea

A computad is a formal device (due to Ross Street) for describing “generators” of $n$-categories, much as directed graphs describe generators of categories. Originally the $n$-categories under consideration were strict, but more recently the concept of $n$-computad has been expanded to take into account weak $n$-categories. The notion is tied to algebraic senses of higher categories, but computads can also be used as the input for geometric senses as well.

Terminology

The article

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

used term polygraph for computad . This term is now used in parts of the literature. Since “computad” is 20 years older, it should probably be preferred.

Definitions

First we work in Street’s original strict setting.

An n-computad is defined recursively as follows:

1. A 0-computad is a set;

2. The data of an $n$-computad consists of an $(n-1)$-computad $𝒞$, a set $C_n$, and source and target maps

   $$s,t:C_n\rightrightarrows F_{n-1}(𝒞{)}_{n-1}$$s, t: C_n \rightrightarrows F_{n-1}(\mathcal{C})_{n-1}

   where $F_{n-1}:(n-1)\mathrm{Comp}\to (n-1)\mathrm{Cat}$ is the “free $(n-1)$-category on an $(n-1)$-computad”, and $D_j$ denotes the set of $j$-cells in a higher-dimensional category $D$.

3. The data must satisfy globularity conditions: for all $c\in C_n$, the $(n-1)$-cells $s(c)$ and $t(c)$ must share the same source and the same target (as elements in $F_{n-1}(𝒞{)}_{n-2}$).

To complete the induction, we need to define $F_n$. Roughly speaking, in dimensions $j<n$, the structure agrees with that of $F_{n-1}(𝒞)$. In dimension $n$, the $n$-cells are formal pasting diagrams built from the elements of $C_n$ by formal whiskering?s and formal compositions across $(n-1)$-cells in $F_{n-1}(𝒞)$.

(Much detail to be filled in…)

Examples

• As in the definition, a 0-computad is a set.

• The free 0-category on a 0-computad is just itself.

• A 1-computad is just a directed graph.

• The free 1-category on a 1-computad is the usual free category on a graph. That is, its objects are the vertices of the graph and its morphisms are finite composable strings of edges in the graph.

• A 2-computad is given by a directed graph together with a set $C_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 directed graph is a square

  $$\begin{array}{ccc}•& \stackrel{f}{\to }& •\\ {}^h\downarrow & & {\downarrow }^k\\ •& \underset{g}{\to }& •\end{array}$$\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 $kf$ and $gh$. We can then make a 2-computad by adding one 2-cell $\alpha$ with source $kf$ and target $gh$. The free 2-category on this 2-computad can then be drawn pictorially as

  $$\begin{array}{ccc}•& \stackrel{f}{\to }& •\\ {}^h\downarrow & {\swarrow }_{\alpha }& {\downarrow }^k\\ •& \underset{g}{\to }& •\end{array}$$\array{\bullet & \overset{f}{\to} & \bullet\\^h\downarrow & \swarrow_\alpha & \downarrow^k\\ \bullet & \underset{g}{\to} & \bullet}

• Any $n$-globular set can be considered as an $n$-computad where for each $n$, the functions $s,t:C_n\rightrightarrows F_{n-1}(𝒞{)}_{n-1}$ land inside $C_{n-1}$. The free $n$-category on this $n$-computad will then agree with the free $n$-category on the $n$-globular set we started with.

• Every oriental can be presented by a computad.

Computads, presheaves and opetopes

The category of computads is “almost” a presheaf category. At first glance, it may look as though it should be a presheaf category, say ${\mathrm{Set}}^{{\mathrm{Ctp}}^{\mathrm{op}}}$ where $\mathrm{Ctp}$ is the category of “computopes.” A “computope” is, intuitively, one possible “shape” for an $n$-cell in an $n$-category. 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, the presence of identities in the notion of free $n$-category prevents this from quite working, for sort of the same reason that strict n-categories are insufficient for $n>2$. For instance, there is a 2-computad with one 0-cell $x$, 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 ${\mathrm{id}}_x$ of $x$. 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 $n\ge 3$, so the categories of 0-computads, 1-computads, and 2-computads are presheaf categories. (For 0 and 1, this is obvious.)

If we restrict the notion slightly, however, we can obtain presheaf categories. For instance, if we consider only “many-to-one” computads in which the target of each $n$-cell consists of exactly one $(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.

Mike Shulman: Do the non-strict versions of computads get around this problem?

Daniel Schäppi: Batanin has a paper on this: Computads and slices of operads

If you take any finitary monad $A$ on the category of globular sets, you can use the truncation functor to get monads $A_n$ on the category of $n$-globular sets, and then you can inductively define the notion of an $A$-computad. If you take $A=T$ the free strict $\omega$-category monad, then this notion agrees with Streets definition of an ordinary computad. Batanin gives a condition which ensures that the category of $n$-computads of $A$ is a presheaf category, in terms of slices of the monad $A$.

The $k$-slice of $A$ is defined as follows: the full subcategory of $A_n-\mathrm{Alg}$ consisting of those algebras whose underlying globular set is $(n-1)$-terminal is monadic over the category of sets, and the $k$-slice of $A$ is given by this monad. In the above paper, Theorem 5.2 Batanin shows that the category of $n$-computads of a Batanin-operad $A$ is a presheaf category if the $k$-slices of $A$ are strongly regular theories for $0\le k\le n-1$. This applies in particular to the case where $A$ is the operad for Batanin weak $\omega$-categories.

Computads as cofibrant resolutions

With respect to the folk model structure on strict ω-categories

• Yves Lafont, Francois Métayer, Krzysztof Worytkiewicz, A folk model structure on omega-cat (arXiv)

the $\omega$-categories that are (freely generated by) computads are precisely the cofibrant objects

This is discussed in

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

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

This says in particular that every strict ω-category is equivalent as an $\omega$-category to one that is a computad. (Notice that these articles say “polygraph” for “computad”, following Burroni).

The cofibrant resolution $(-{)}_{\mathrm{cof}}\to \mathrm{Id}:\omega \mathrm{Cat}\to \omega \mathrm{Cat}$ given by Métayer in these articles is the one counit of the adjunction $\omega \mathrm{Comp}\to \omega \mathrm{Cat}$.

We had some blog discussion about this at Freely generated omega-categories.