Codescent Objects and Coherence
Posted by Emily Riehl
Guest post by Alex Corner
This is the 11th post in the Kan Extension Seminar series, in which we will be looking at Steve Lack’s paper
- [Lack] Codescent objects and coherence, Stephen Lack, J. Pure and Appl. Algebra 175 (2002), pp. 223-241.
A previous post in this series introduced us to two-dimensional monad theory, where we were told about $2$-monads, their strict algebras, and the interplay of the various morphisms that can be considered between them. The paper of Lack has a slightly different focus in that not only are we interested in morphisms of varying levels of strictness but also in the weaker notions of algebra for a $2$-monad, namely the pseudoalgebras and lax algebras.
An example that we will consider is that of the free monoid $2$-monad on the $2$-category $\mathbf{Cat}$ of small categories, functors, and natural transformations. The strict algebras for this $2$-monad are strict monoidal categories, whilst the lax algebras are (unbiased) lax monoidal categories. Similarly, the pseudoalgebras are (unbiased) monoidal categories. The classic coherence theorem of Mac Lane is then almost an instance of saying that the pseudoalgebras for the free monoid $2$-monad are equivalent to the strict algebras. We will see conditions for when this can be true for an arbitrary $2$-monad.
Thanks go to Emily, my supervisor Nick Gurski, the other participants of the Kan extension seminar, as well as all of the participants of the Sheffield category theory seminar.
Algebras for $2$-monads
When doing $2$-category theory, we often look at weakening familiar notions. We generally do this by replacing axioms that required commutativity of certain diagrams with (possibly invertible) $2$-cells, which themselves are required to satisfy coherence axioms. For instance, given a $2$-monad $T$ (with multiplication $\mu$ and unit $\eta$) on a $2$-category $\mathcal{K}$, a lax algebra for $T$ consists of an object $A$ of $\mathcal{K}$, a $1$-cell $x : TX \rightarrow X$ of $\mathcal{K}$ and $2$-cells $\begin{matrix} T^2X & \overset{Tx}{\longrightarrow} & TX & & X & \overset{1_X}{\longrightarrow} & X \\ {}_{\mu_X}\downarrow & \Downarrow {\chi} & \downarrow^x & & {}_{\eta_X}\searrow & \Downarrow {\chi_0} & \nearrow_x & \\ TX & \underset{x}{\longrightarrow} & X & & \quad & TX & \\ \end{matrix}$ in $\mathcal{K}$ which satisfy suitable axioms. A pseudoalgebra is defined as above but with invertible $2$-cells.
Example We’ll see what’s going on by looking at the free monoid $2$-monad again, call it $M$. A lax algebra for $M$ is a category $X$ and a functor $x : MX \rightarrow X$ with natural transformations $\chi$, $\chi_0$ as above. Now $MX$ is the coproduct $\coprod_{n \in \mathbb{N}} X^n$ meaning that objects in $MX$ are finite lists of objects in $X$, and similarly for morphisms. The functor $x : MX \rightarrow X$ is a functor out of a coproduct so in fact corresponds to a family of functors $(x_n : X^n \rightarrow X)_{n \in \mathbb{N}}$ which we can view as being the $n$-ary tensors of an unbiased lax monoidal category. The natural transformation $\chi$ then has components which are morphisms $\left(\left(a_{11} \otimes \ldots \otimes a_{1k_1}\right) \otimes \ldots \otimes \left(a_{n1} \otimes \ldots \otimes a_{nk_n}\right)\right) \rightarrow \left(a_{11} \otimes \ldots \otimes a_{nk_n}\right)$ in $X$. These are what correspond to the associators in a biased monoidal category. The associativity and unit axioms can then be found to be expressed by the lax algebra axioms.
These differing levels of strictness offer us a whole host of $2$-categories to look at. For our purposes we will be looking at the following $2$-categories:
- $T\text{-Alg}_s$, of strict algebras, strict morphisms, and transformations;
- $\text{Ps-}T\text{-Alg}$, of pseudoalgebras, pseudomorphisms, and transformations;
- $\text{Lax-}T\text{-Alg}_l$, of lax algebras, lax morphisms, and transformations.
Lax codescent objects
The second section of the paper begins by considering lax morphisms of the form $(f, \overline{f}) : (X, x, \chi, \chi_0) \rightarrow (Y,y),$ between a lax algebra $X$ and a strict algebra $Y$. The idea is that lax morphisms of this form in $\text{Ps-}T\text{-Alg}$ can be recast as strict morphisms $(g = y \cdot Tf, \overline{g} = 1_{y} \ast T\overline{f}) : (TX, \mu_X) \rightarrow (Y,y)$ in $T\text{-Alg}_s$. There is an inclusion 2-functor $U : T\text{-Alg}_s \rightarrow \text{Lax-}T\text{-Alg}_l$ and the aim is to construct a left adjoint. To this end, Lack describes a universal property related to $1$-cells in $T\text{-Alg}_s$ of the form $TX \rightarrow X'$ so that there is an isomorphism $T\text{-Alg}_s(X',Y) \cong \text{Lax-}T\text{-Alg}_l(X,Y)$ which is natural in Y. This tells us that if such an object $X'$ exists for every lax algebra $X$, then the left adjoint also exists.
The universal property in question turns out to be that of a lax codescent object in a $2$-category. First we define lax coherence data to be diagrams $\begin{array}{ccccc} \quad & \overset{p}{\rightarrow} & \quad & \overset{d}{\rightarrow} & \\ X_3 & \overset{q}{\rightarrow} & X_2 & \overset{e}{\leftarrow} & X_1\\ \quad & \overset{r}{\rightarrow} & \quad & \overset{c}{\rightarrow} & \end{array}$ accompanied by $2$-cells $\begin{array}{cc} \delta : de \Rightarrow 1_{X_1}, & \gamma : 1_{X_1} \Rightarrow ce, \\ \kappa : dp \Rightarrow dq, & \lambda : cr \Rightarrow cq, \\ \rho : cp \Rightarrow dr. \end{array}$ A lax codescent object is then an object $X$, a $1$-cell $x : X_1 \rightarrow X$, and a $2$-cell $\chi : xd \Rightarrow xc$, all interacting with the $1$-cells and $2$-cells of the lax coherence data. These then also satisfy universal properties of a $2$-categorical nature, much like those we saw in a previous post.
Consider for a moment, an algebra $(A,a)$ for a $1$-monad $S$ on a $1$-category $\mathcal{C}$. We know that this can be expressed as the reflective coequaliser of the diagram $\begin{array}{ccc} \quad & \overset{\mu_A}{\longrightarrow} & \quad \\ S^2A & \overset{S\eta_A}{\longleftarrow} & SA \\ \quad & \overset{Sa}{\longrightarrow} & \quad \\ \end{array}$ in the category $S\text{-Alg}$ of $S$-algebras. However in the case of a lax algebra $(X, x, \chi, \chi_0)$ for a $2$-monad $T$, this won’t be the case. Instead we can form lax coherence data $\begin{array}{ccccc} \quad & \overset{\mu_{TA}}{\rightarrow} & \quad & \overset{\mu_A}{\rightarrow} & \\ T^3X & \overset{T\mu_X}{\rightarrow} & T^2X & \overset{T\eta_A}{\leftarrow} & TX\\ \quad & \overset{T^2x}{\rightarrow} & \quad & \overset{Tx}{\rightarrow} & \end{array}$ in $T\text{-Alg}_s$ when we accompany it with $2$-cells $T\chi_0$ and $T\chi$, where the rest of the $2$-cells are just identities arising from the $2$-monad axioms. The universal property alluded to above is then that the lax codescent object of this lax coherence data is the same as that of the replacement (strict) algebra $X'$ which would give the adjunction previously described.
If all of the mentions of $2$-cells in the above description of a lax codescent object were replaced with invertible $2$-cells, then we would have the notion of a codescent object. This is the analogous situation in the case of pseudoalgebras, where the aim is to find a left adjoint to the inclusion to the inclusion $2$-functor $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}.$
A useful observation is that lax codescent objects may be defined using weighted colimits and can be built from coinserters and coequifiers. Also worthy of note is that codescent objects can be built from co-iso-inserters and coequifiers. Now co-iso-inserters exist whenever coinserters and coequifiers do, so that anything we want to prove about lax algebras by utilising such colimits, will also be true for pseudoalgebras.
This section of the paper also includes a number of results concerning adjunctions between the various $2$-categories of algebras, with the following theorem then being the basis for the first characterisation of a coherence theorem.
Theorem: (Lack, 2.4) For a $2$-monad $T$ on a $2$-category $\mathcal{K}$, the inclusion $T\text{-Alg}_s \rightarrow \text{Lax-}T\text{-Alg}_l$ has a left adjoint if any of the following conditions holds:
- $\mathcal{K}$ admits lax codescent objects and $T$ preserves them;
- $\mathcal{K}$ admits coinserters and coequifiers and $T$ preserves them;
- $\mathcal{K}$ is cocomplete and $T$ preserves $\alpha$-filtered colimits for some regular cardinal $\alpha$.
Conditions $2$ and $3$ also give us a left adjoint to the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$. Furthermore, we also find that a left adjoint to the inclusion $T\text{-Alg}_s \rightarrow T\text{-Alg}$, which we saw in the paper of Blackwell, Kelly, and Power, also exists under these conditions. Something else that we saw in that paper is the reason for needing $T$ to preserve these colimits - the colimits exist in $T\text{-Alg}_s$ just when $T$ preserves them.
Coherence
The simplest possible characterisation of coherence for $2$-monads would be:
Theorem-Schema: The inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit are equivalences in $\text{Ps-}T\text{-Alg}$.
Now this is certainly not true in general. A counter-example (3.1) is given in the paper, whilst Mike Shulman also shows that not every pseudoalgebra is equivalent to a strict one.
Something that is rather nice, though, is that we already have some conditions under which the theorem-schema is satisfied.
Theorem: (Lack, 3.2) If $T$ is a $2$-monad on a $2$-category $\mathcal{K}$ admitting codescent objects, and $T$ preserves them, then the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit are equivalences in $\text{Ps-}T\text{-Alg}$. In particular this is the case if $\mathcal{K}$ has coinserters and coequifiers, and $T$ preserves them.
The proof of this is rather simple and falls out of the two-dimensional universal property of the codescent objects.
I’m going to roll the latter two sections of the paper together now and talk about the other characterisation of coherence, which concerns a general coherence result of Power. That paper looks at $2$-monads on $\mathbf{Cat}^X$ and $\mathbf{Cat}^X_g$, where $X$ is a small set and the latter $2$-category is attained from the first by only considering invertible $2$-cells. Power then shows that if $T$ is a $2$-monad on one of these $2$-categories which preserves bijective-on-objects functors, then every pseudoalgebra for $T$ is equivalent to a strict one.
Some $2$-monads which satisfy these conditions include $\mathbf{Set}$-based clubs, whose strict algebras give such structures as monoidal categories (see the scope of the results below for more monoidal examples) or categories with strictly associative finite products or coproducts. Also described in Power’s paper is a $2$-monad on $\mathbf{Cat}^{X \times X}$ for which the pseudoalgebras are unbiased bicategories with object set $X$. The coherence result then tells us that every bicategory is biequivalent to a $2$-category with the same set of objects.
Comparing Power’s statement to the theorem-schema, we see that they are not quite the same. The schema asks for there to be an adjunction for which the components of the unit give the equivalences we are concerned with. As it turns out, the conditions which Power proposes are indeed enough to give what we desire, and this is what the latter characterisation of Lack looks at.
Recall that every functor can be factored as a bijective-on-objects functor followed by a full and faithful functor. This gives an orthogonal factorisation system $(bo,ff)$ on $\mathbf{Cat}$. However, the $(bo,ff)$ factorisation system has an extra two-dimensional property concerning $2$-cells. If we are given a natural isomorphism $\begin{matrix} A & \overset{R}{\longrightarrow} & C \\ {}_{F}{\downarrow} & {\Downarrow}_{\alpha} & \downarrow^G \\ B & \underset{S}{\longrightarrow} & D \\ \end{matrix}$ where $F$ is bijective-on-objects and $G$ is full and faithful, then there is a unique pair $(H,\beta)$ consisting of a functor $H:B \rightarrow C$ and a natural isomorphism $\beta:GH \Rightarrow S$ such that $HF = R$ and the whiskering of $\beta$ with $F$ gives back $\alpha$. For an arbitrary $2$-category $\mathcal{K}$, an orthogonal factorisation system with such a property is deemed an enhanced factorisation system.
Theorem: (Lack, 4.10) If $\mathcal{K}$ is a $2$-category with an enhanced factorisation system $(\mathcal{L},\mathcal{R})$ having the property that if $j \in \mathcal{R}$ and $jk \cong 1$ then $kj \cong 1$, and if $T$ is a $2$-monad on $\mathcal{K}$ for which $T$ preserves $\mathcal{L}$-maps, then the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit of the adjunction are equivalences in $\text{Ps-}T\text{-Alg}$.
The proof starts by noting that if we have a pseudoalgebra $(X, x, \chi, \chi_0)$ then we can factorise $x:TX \rightarrow X$ as $TX \overset{e}{\longrightarrow} X' \overset{m}{\longrightarrow} X,$ where $e \in \mathcal{L}$ and $m \in \mathcal{R}$. Thus we have an invertible $2$-cell $\begin{array}{ccccc} T^2X & \overset{\mu_X}{\longrightarrow} & TX & \overset{e}{\longrightarrow} & X' \\ {}_{Te}{\downarrow} & \quad & \Downarrow^{\chi} & \quad & \downarrow^{m} \\ TX' & \underset{Tm}{\longrightarrow} & TX & \underset{x}{\longrightarrow} & X \\ \end{array}$ and, since $T$ preserves $\mathcal{L}$-maps, we can use the enhanced factorisation system to get a strict algebra $X'$ which is equivalent to $X$. (See Power’s coherence result for the details on this.)
It is interesting to see the scope of these results and the places in which people have considered this type of coherence problem before.
- Dunn proved the theorem-schema when $\mathcal{K}$ is the $2$-category of based topological categories and for which $T$ is a $2$-monad induced by a braided $\mathbf{Cat}$-operad.
- The theorem-schema was also proved by Hermida, though required much more of both the $2$-category $\mathcal{K}$ and the $2$-monad $T$, such as requiring existence and preservation of various limits and colimits, exactness properties relating these, as well as further conditions on the unit and multiplication of the $2$-monad. Something that does fall out of this alternative setup is that $T$ can be replaced by a new $2$-monad, on a different $2$-category, which is lax-idempotent.
- Rather more recently Nick Gurski and I wrote about operads with general groups of equivariance. Therein we showed that the $2$-monads which arise from $\mathbf{Cat}$-operads in this way satisfy the coherence conditions following the enhanced factorisation system route. These $2$-monads capture many different structures, including monoidal categories, braided monoidal categories, symmetric monoidal categories, and ribbon braided monoidal categories. Thus we can say, for example, that every unbiased braided monoidal category is equivalent to a braided strict monoidal category, and similarly for the other variations.
- The first theorem we mentioned above has three conditions, the third being the requirement that $\mathcal{K}$ is cocomplete and $T$ preserves $\alpha$-filtered colimits for some regular cardinal $\alpha$. We mentioned aboe that it was proved by Blackwell, Kelly, and Power that this is also sufficient to give a left adjoint to the inclusion $U : T\text{-Alg}_s \rightarrow T\text{-Alg}$. They also proved further that if $\mathcal{K}$ is locally $\alpha$-presentable then there is a $2$-monad $T'$ which preserves $\alpha$-filtered colimits and where $T'\text{-Alg}_s = \text{Ps-}T\text{-Alg}$. The result of the theorem we discussed then follows when $\mathcal{K}$ is locally presentable and $T$ preserves $\alpha$-filtered colimits. Lack comments that it is a major unsolved problem as to whether the entire theorem-schema can be shown to be true under these asumptions - and further whether it is true when $\mathcal{K}$ is only cocomplete.
Re: Codescent Objects and Coherence
Another interesting appearance of codescent objects, as touched on in this paper, is in the bo-ff factorisation of a functor. Just as how in Set (or more generally a regular category) we may form the image factorisation of a function by taking the coequaliser of its kernel pair (the equivalence relation it induces on its domain), in Cat (or more generally) we get the bo-ff factorisation of a functor by taking the codescent object of its “higher kernel”. See for instance John Bourke’s thesis, where this 2-dimensional exactness play continues, featuring cateads in the role of equivalence relations.