April 28, 2014

On Two-Dimensional Monad Theory

Posted by Emily Riehl

Guest post by Sam van Gool

Monads provide a categorical setting for studying sets with additional structure. Similarly, 2-monads provide a 2-categorical setting for studying categories with additional structure. While there is really only one natural notion of algebra morphism in the context of monads, there are several choices of algebra morphism in the context of 2-monads. The interplay between these different kinds of morphisms is the main focus of the paper that I discuss in this post:

I will give an overview of the results and methods used in this paper. Also, especially towards the end of my post, I will also indicate some points that I think could still be clarified further by formulating some questions, which will hopefully lead to fruitful discussions below.

This post forms the 9th instalment of the series of posts written by participants of the Kan Extension Seminar, of which I’m very glad to be a part. In preparing the post I have greatly benefited from discussions with the other participants in the seminar, and of course with the seminar’s organizer, Emily Riehl. I am very grateful for the enthusiasm, encouragement and guidance that you all offered.

2-monads, their algebras, and their morphisms

Two-dimensional universal algebra goes beyond the $\mathbf{Cat}$-enriched setting in that it allows for non-strict morphisms. Consider the following (very) simple example.

Example. For a category $A$, let $T A$ be the category $A$ provided freely with a terminal object. This assignment can be extended to a 2-monad $T$ on $\mathbf{Cat}$. Then:

• an algebra for $T$ is (entirely determined by giving) a pair $(A,t_A)$ where $A$ is a category and $t_A$ is a designated terminal object in $A$;
• a strict morphism $(A,t_A) \to (B,t_B)$ is a functor $f$ for which $f(t_A) = t_B$;
• a pseudo morphism is a functor $f$ such that $f(t_A)$ is isomorphic to $t_B$;
• a lax morphism is just any functor from $A$ to $B$, with no additional requirement on the terminal object.

If you didn’t know them already, you will probably have guessed the general definitions of strict, pseudo and lax morphisms by now, as well as the definition of 2-cells between them. Note that, in this post, all 2-monads and algebras for them will be strict, as in [BKP].

For any 2-monad $T$, we thus get the following inclusions of 2-categories:

$T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p \to T\text{-}\mathrm{Alg}_l.$

(In [BKP], the category $T\text{-}\mathrm{Alg}_p$ is denoted by $T\text{-}\mathrm{Alg}$.) Roughly the first half of the paper [BKP] is devoted to the construction of left adjoints (in the 2-categorical sense) to these inclusion functors.

Note that $T\text{-}\mathrm{Alg}_s$ is simply the Eilenberg-Moore $\mathcal{V}$-category of the $\mathcal{V}$-enriched monad $T$ in the case where $\mathcal{V} = \mathbf{Cat}$, in the sense of the second paper that we read in this seminar. The categories $T\text{-}\mathrm{Alg}_p$ and $T\text{-}\mathrm{Alg}_l$, on the other hand, are special to the $\mathbf{Cat}$-enriched setting.

Limits in $T$-Alg$_p$

The category $T\text{-}\mathrm{Alg}_s$ has all 2-limits that the base 2-category $\mathcal{K}$ has. For $T\text{-}\mathrm{Alg}_p$, the situation is more subtle.

Example (c’t’d). In the example where $T A$ is $A$ provided freely with a terminal object, let $1 = \{\ast\}$ be the terminal category and $I$ the category with two objects $0$, $1$ and a unique isomorphism between them. There are two pseudo-morphisms $(1,\ast) \to (I,0)$, one sending $\ast$ to $0$, the other sending $\ast$ to $1$. However, if $C \to 1$ is any functor which equalizes these two morphisms, then $C$ is empty, and so it does not admit a $T$-algebra structure. Thus, the category $T\text{-}\mathrm{Alg}_p$ does not admit equalizers in general.

Assuming that the $2$-category $\mathcal{K}$ is complete, it is however possible to construct the following limits in $T\text{-}Alg_p$:

• Products,
• Inserters and iso-inserters,
• Equifiers,

and they are created by the forgetful functor $T\text{-}Alg_p \to \mathcal{K}$. As we saw in last week’s post, these PIE-limits allow for the construction of many other limits. In particular, from the results discussed last week, we see that $T\text{-}\mathrm{Alg}_p$ also has inverters and co-tensors, and hence also lax and pseudo limits.

It is also worth noting that each of the results on existence of limits “restricts to strict” (for lack of a better name), by which I mean that, for each of these limits, there exists a limiting cone such that the algebra 1-cells in the limiting cone:

1. are strict, and

2. detect strictness.

For example, for any parallel pair $f, g : B \to C$ in $T\text{-}\mathrm{Alg}_p$ there is an inserter $p : A \to B$ such that (1) $p$ is strict, and (2) if $ph$ is strict for some algebra morphism $h : D \to A$, then $h$ is strict.

The pseudomorphism classifier

Example (c’t’d). In the example where $T A$ is $A$ provided freely with a terminal object, note that pseudo-morphisms can be mimicked using strict morphisms: for any algebra $(A,t_A)$, consider the algebra $(A',t_{A'})$, defined by adding one new object $t_{A'}$ and an isomorphism $t_{A} \cong t_{A'}$ to $A$. It is then clear that, for any algebra $(B,t_B)$, strict morphisms $(A',t_{A'}) \to (B,t_B)$ correspond to pseudo-morphisms $(A,t_A) \to (B,t_B)$. In fact, this correspondence is an isomorphism between the categories of morphisms and natural transformations between them.

The following theorem, which is arguably at the heart of the paper [BKP], says that the above phenomenon in fact occurs for any reasonably well-behaved 2-monad.

Theorem. Let $T$ be an accessible 2-monad on a 2-category $\mathcal{K}$ that is complete and cocomplete. Then the inclusion 2-functor $T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p$ has a left adjoint.

Proof (Sketch). The proof of the theorem consists of three steps:

1. A general fact: in order to find a left adjoint to a 2-functor $G : \mathcal{K} \to \mathcal{L}$, it suffices to find a left adjoint to its underlying ordinary functor $G_o$, provided that $\mathcal{K}$ has cotensors with the walking arrow category $2$ and $G$ preserves them.
2. Using (1), one shows that there exists a left adjoint, $()^o$, to the inclusion functor $T\text{-}\mathrm{Alg}_s \to T/{\mathcal{K}},$ where $T/{\mathcal{K}}$ is the comma 2-category.
3. The hardest part: pseudo-morphisms out of a $T$-algebra $(A,a)$ can be mimicked by $T/\mathcal{K}$-morphisms out of a certain object $(C,c,Z)$ of $T/{\mathcal{K}}$.

Now, composing (2) and (3), one associates to any $T$-algebra $(A,a)$ the $T$-algebra $(C,c,Z)^o$ and observes that this gives an ordinary (1-categorical) left adjoint to $T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p$. Then, by (1) and the fact that cotensors exist in $T\text{-}\mathrm{Alg}_p$, it is also a 2-categorical left adjoint. $\qed$

The image under the left adjoint of an algebra $A$, seen as an object of $T\text{-}\mathrm{Alg}_p$, is denoted by $A'$ and called the pseudo-morphism classifier of $A$. Under the conditions of the Theorem, there is also a lax morphism classifier.

There are more conceptual proofs of these facts, using the concept of codescent objects; see, for example, this paper (which will be discussed in these series in a month or so) and Section 4 of the 2-categories companion by Stephen Lack. The latter paper, by the way, has been an indispensable source for me in preparing this post, and those who are familiar with it will probably recognize its influence throughout the post.

Flexibility

We denote by the letters $p$ and $q$ the unit and co-unit of the adjunction

$J : T\text{-}\mathrm{Alg}_s \leftrightarrows T\text{-}\mathrm{Alg}_p : ()'$

from the above theorem. For any algebra $A$ in $T\text{-}\mathrm{Alg}_p$, the morphism $q_A : A' \to A$ is in fact always a surjective equivalence in the 2-category $T\text{-}\mathrm{Alg}_p$, but in general $q_A$ does not even need to be an equivalence in $T\text{-}\mathrm{Alg}_s$, as we will see shortly. If $q_A : A' \to A$ is an equivalence in $T\text{-}\mathrm{Alg}_s$, then $A$ is called semi-flexible, and $A$ is called flexible if $q_A$ is a surjective equivalence in $T\text{-}\mathrm{Alg}_s$. The flexible objects are the cofibrant objects in a model structure on $T\text{-}\mathrm{Alg}_s$ lifted from the model structure on $\mathcal{K}$, and the pseudomorphism classifier $A'$ is then a special cofibrant replacement of $A$ (see Section 7.3 of the 2-categories companion for more details about this).

Several equivalent characterizations of flexibility and semi-flexibility are given in Theorems 4.4 and 4.7, respectively, of [BKP]. One useful equivalent way to say that a $T$-algebra $A$ is semi-flexible is that every pseudo-morphism out of $A$ is isomorphic to a strict morphism out of $A$. With this definition, we can see that not every $T$-algebra is semi-flexible:

Example. Let $T$ be the 2-monad on $\mathbf{Cat}$ whose algebras are small categories with assigned finite limits. Let $A$ be the terminal category, with finite limits assigned in the only possible way. Let $B$ be any category with assigned finite limits in which $t_B$ is the assigned terminal object and the assigned product $t_B \times t_B$ is not equal to $t_B$ (the two objects will of course be isomorphic). Then the functor $A \to B$ which sends the unique object of $A$ to $t_B$ is a pseudo-morphism, but it is clearly not isomorphic to any strict morphism.

The following example shows that flexibility and semi-flexibility are really different concepts.

Example. Categories whose objects are functors can also often be represented as the $T$-algebras for an appropriate monad $T$ on an appropriate base 2-category $\mathcal{K}$. For instance, there is a 2-monad $T$ on $\mathbf{Cat} \times \mathbf{Cat}$, given on objects by $T(X,Y) := (X,X+Y)$, such that $T$-algebras are functors, a pseudomorphism from $f : A \to B$ to $g : C \to D$ is a diagram of the form $\begin{matrix} A & \overset{f}{\to} & B \\ u \downarrow & \overset{\alpha}{\cong} & \downarrow v \\ C & \overset{g}{\to} & D \end{matrix}$ and such a pseudomorphism is strict exactly when $\alpha$ is the identity. Now, letting $1$ denote the terminal category, it is easy to describe the pseudomorphism classifier of the $T$-algebra $a : A \to 1$: this is the inclusion functor $j : A \to \overline{A}$, where $\overline{A}$ is the indiscrete category on objects $\mathrm{ob}(A) + \{\ast\}$ (As a simple but nice exercise, you may check that, indeed, any pseudomorphism out of the algebra $a : A \to 1$ corresponds uniquely to a strict morphism out of the algebra $j : A \to \overline{A}$.) Now, letting $I$ again denote the category with two objects $0$, $1$ and a unique isomorphism between them, one may check that the algebra $I \to 1$ is equivalent in $T\text{-}\mathrm{Alg}_s$ to the algebra $1 \to 1$, which is flexible, and therefore $I \to 1$ is semi-flexible. However, $I \to 1$ is not flexible. (See example 4.11 in [BKP]).

Biadjunctions and bicolimits in $T\text{-}\mathrm{Alg}_p$

So far, we have only considered limits, which one would expect to exist in a category of algebras. On the other hand, we wouldn’t generally expect colimits to exist in a category of algebras, but as it turns out, in the last section of [BKP], the authors prove that:

1. the category $T\text{-}\mathrm{Alg}_p$ admits bicolimits, and
2. any strict map of 2-monads $\theta : S \to T$ induces a map $T\text{-}\mathrm{Alg}_p \to S\text{-}\mathrm{Alg}_p$ that has a left biadjoint.

Both of these results are consequences of the following more technical fact:

Theorem. If $G : T\text{-}\mathrm{Alg}_p \to \mathcal{L}$ is a 2-functor so that the composite 2-functor

$\begin{matrix} T-Alg_s & \overset{J}{\to} & T-Alg_p & \overset{G}{\to} & L \end{matrix}$

has a left adjoint $H$, then $H$ maps into flexible algebras, and $J \circ H$ is left biadjoint to $G$.

From the above theorem and the relation between biadjoints and bicolimits that we discussed last week, bicolimits can now be constructed in $T\text{-}\mathrm{Alg}_p$, as claimed in (1) above. To prove (2), one first notices that 2-functor $\theta^* : T\text{-}\mathrm{Alg}_s \to S\text{-}\mathrm{Alg}_s$ extends to a 2-functor $\theta^\# : T\text{-}\mathrm{Alg}_p \to S\text{-}\mathrm{Alg}_p$ making the diagram

$\begin{matrix} T\text{-}\mathrm{Alg}_s & \overset{\theta^*}{\to} & S\text{-}\mathrm{Alg}_s \\ J\downarrow & \quad & \downarrow J \\ T\text{-}\mathrm{Alg}_p & \overset{\theta^\sharp}{\to} & S\text{-}\mathrm{Alg}_p \end{matrix}$

commute. One may then apply the Theorem in the case $G = \theta^\#$.

More examples of 2-monads

Above I motivated the concepts and theorems in [BKP] with some simple examples of 2-monads. The last section of [BKP] contains many more examples. About the general method for constructing such examples, the authors make the following interesting comment.

“In practice one is seldom presented with a 2-monad and invited to consider its algebras; more commonly one contemplates some structure borne by a category (…) and one concludes in certain cases that the structure is given by an action of a 2-monad (…)”

With this comment in mind, one may now construct 2-monads whose algebras are monoidal categories, symmetric monoidal closed categories (here the 2-monad is over the 2-category $\mathbf{Cat}_g$, where the 2-cells are only taken to be natural isomorphisms), and even finitary 2-monads themselves (they are the algebras for a certain 2-monad $R$ on the functor 2-category $[\mathbf{Cat}_f,\mathbf{Cat}]$, where $\mathbf{Cat}_f$ is the full subcategory of $\mathbf{Cat}$ consisting of the finitely presentable objects. This perspective was exploited in a later paper by Kelly and Power on presentations of 2-monads.

A final point of interest is that one may distinguish a special kind of 2-monad $T$, namely those for which the $T$-algebra structure on an object $A$ is unique if it exists. Such 2-monads $T$ define a property of rather than a structure on the objects of the base 2-category $\mathcal{K}$, and may thus be called property-like (as they are in this later paper by Kelly and Lack). As the authors of [BKP] remark, it “may well be a hard problem” how to distinguish the property-like 2-monads $T$ from, say, a presentation for them. A particular class of 2-monads which are ‘property-defining’ are the lax-idempotent 2-monads (which also go by the names “quasi-idempotent” and “Kock-Zöberlein” 2-monads).

Questions

Let me finish with a (non-exhaustive) list of questions that may be interesting to discuss below.

1. Can the fact that limits in $T\text{-}\mathrm{Alg}_p$ can be chosen with a fair amount of “strictness” be understood using this account of lax / pseudo limits for morphisms between $T$-algebras using $\mathcal{F}$-enrichment?

2. The flexible algebras are exactly the strict retracts of pseudomorphism classifiers. The latter are “free algebras”, in some sense (at least in the sense that they are the images of a left adjoint). This suggests that one could think of the concept ‘flexible algebra’ as a 2-categorical version of the familiar concept ‘projective algebra’ in the 1-categorical setting. Is this a good intuition, and if so, can it be (or has it already been) made more precise?

3. In order to better understand the concept of flexible algebra and the biadjunctions in the later part of [BKP], it would probably be useful to study different examples of 2-monads, and in particular, answer the following questions in such examples:

(a) is there a concrete construction of the pseudomorphism classifier?

(b) which algebras are (semi-)flexible?

(c) (for a strict map between 2-monads) what does the biadjunction do?

Posted at April 28, 2014 9:31 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2737

0 Comments & 0 Trackbacks

Post a New Comment