Comparison Functors

We have now seen both the Kleisli and Eilenberg-Moore constructions for a monad \mathbb{T}, and that they yield adjunctions that induce the original monad. Such an adjunction is sometime referred to as a resolution of \mathbb{T}.

In order to compare different resolutions of a monad \mathbb{T} on category \mathcal{C}, we need a suitable category in which to compare them. Define \mathsf{Adj}_{\mathbb{T}} as the category with:

  • Objects: Adjunctions F \dashv U, where U has codomain \mathcal{C}, that induce \mathbb{T}.
  • Morphisms: A morphism (F \dashv U : \mathcal{D} \rightarrow \mathcal{C}) \rightarrow (F' \dashv U' : \mathcal{D}' \rightarrow \mathcal{C}) is a functor K : \mathcal{D} \rightarrow \mathcal{D}' such that F' = K \circ F and U = U' \circ K.

Note: All the adjunctions inducing \mathbb{T} must have the same unit, and the counit of adjunction is determined by its unit. It is therefore sufficient to specify only the functors in the objects of \mathsf{Adj}_{\mathbb{T}}.

Writing \epsilon and \epsilon' for the counits of the domain and codomain respectively, the conditions for K being a \mathsf{Adj}_{\mathbb{T}}-morphism imply

K \epsilon' = \epsilon_K

We shall refer to this equation as the key property. Establishing its validity requires some additional work, either via direct calculation, or invoking some theory of adjoint squares, which we shall omit. (Although I should point out there is a short string diagrammatic proof, for those that like that sort of thing!)

The Kleisli Construction

Clearly, (F_{\mathbb{T}} \vdash U_{\mathbb{T}} : \mathcal{C}_{\mathbb{T}} \rightarrow \mathcal{C}) is an object of \mathsf{Adj}_{\mathbb{T}}. Let (F \vdash U : \mathcal{D} \rightarrow \mathcal{C}) be any other object, with counit of the adjunction \epsilon. There is a morphism from the Kleisli adjunction to this object, referred to as the Kleisli comparison functor, given by a functor K_{\mathbb{T}}. On objects:

K_{\mathbb{T}}(A) = F(A).

For a \mathcal{C}_{\mathbb{T}}-morphism f : A \rightarrow B, with underlying morphism f : A \rightarrow UF(B):

K_{\mathbb{T}}(f) = F(A) \xrightarrow{F(f)} FUF(B) \xrightarrow{\epsilon_{F(B)}}F(B)

That identities are preserved by K_{\mathbb{T}} follows from the snake equation:

K_{\mathbb{T}}(\eta_A) = \epsilon_{F(A)} \circ F(\eta_A) = \mathsf{id}_{F(A)}

For the composition, noting that \mu = U \epsilon_F, by definition:

K_{\mathbb{T}}(\mu_C \circ \mathbb{T}(g) \circ f) = \epsilon_{F(C)}  \circ FU(\epsilon_{F(C)}) \circ FUF(g) \circ F(f)

Applying naturality, this is equal to:

\epsilon_{F(C)}  \circ \epsilon_{FUF(C)} \circ FUF(g) \circ F(f)

Applying naturality again gives:

\epsilon_{F(C)}  \circ F(g) \circ \epsilon_{F(B)} \circ F(f)

Which completes verification that composition is preserved by K_{\mathbb{T}}. Verifying that the two equations required of morphisms hold is straightforward as well.

We would like to show that this is the unique such morphism in \mathsf{Adj}_{\mathbb{T}}. This uniqueness is termed “obvious” in some accounts, which in my opinion is rather optimistic, so we sketch the main points. The action on objects of any putative morphism K is easily seen to be forced by one of the equations required of morphisms in \mathsf{Adj}_{\mathbb{T}}:

F(A) = K(F_{\mathbb{T}}(A)) = K(A)

We would like to show that the action on morphisms is also forced, this is a bit trickier. We first note that as F_{\mathbb{T}} is identity on objects, every morphism in \mathcal{C}_{\mathbb{T}} is the transpose of a morphism in \mathcal{C}, that is, it is of the form:

\epsilon^{\mathbb{T}}(B) \bullet F_{\mathbb{T}}(f)

Furthermore, f is the underlying \mathcal{C}-morphism of the Kleisli morphism. (This may need a bit of thought about the Kleisli adjunction to convince yourself this is true). Above, we write the counit of the Kleisli adjunction as \epsilon^{\mathbb{T}}. This deviates from our usual convention of using subscripts for Kleisli notions, but saves notational confusion when dealing with components of natural transformations.

Using functoriality:

K (\epsilon^{\mathbb{T}}_B \bullet F_{\mathbb{T}}(f)) = K(\epsilon_B) \circ K(F_{\mathbb{T}}(B))

Applying the key property, the previous expression is equal to

\epsilon_K(B) \circ K(F_{\mathbb{T}(B)}(f))

Finally, applying one of the equations for K being a morphism, and its previously established action on objects, we get

\epsilon_{F{B}} \circ F(f)

This is exactly the expression for the action on morphisms in our definition of K_{\mathbb{T}}. In summary, we have established that the Kleisli adjunction is the initial resolution of \mathbb{T}.

We now quickly look at some important details of the universal morphisms from the Kleisli adjunction. K_{\mathbb{T}} has image on objects those of the form F(A). For a morphism F(A) \xrightarrow{f} F(B), U(f) \circ \eta_A is a Kleisli morphism, and its image under K_{\mathbb{T}} is f, so K_{\mathbb{T}} is full. Also

K_{\mathbb{T}}(f) = \epsilon_{F(A)} \circ A

By the snake equation, this assignment is injective, so also K_{\mathbb{T}} is faithful.

The Eilenberg-Moore Construction

The Eilenberg-Moore adjunction (F^{\mathbb{T}}, U^{\mathbb{T}}) also yields an object of \mathsf{Adj}_{\mathbb{T}}. For any other \mathsf{Adj}_{\mathbb{T}}-object (F \vdash U : \mathcal{D} \rightarrow \mathcal{C}), we aim to show there is a unique morphism K^{\mathbb{T}} to the Eilenberg-Moore adjunction. The equation U^{\mathbb{T}} \circ K^{\mathbb{T}} = U tells us that

K(A) = (U(A), \xi) \qquad K(f) = U(f)

Where \xi : UFU(A) \rightarrow U(A) is a to be determined structure map. Write \epsilon^{\mathbb{T}} for the counit of the Eilenberg-Moore adjunction. This has components \epsilon_{(A, \alpha)} = \alpha (This is just a matter of examining the details of adjunction if it is unfamiliar). Therefore \epsilon_{K(A)} = \xi. Applying the key property, combined with the action of K on morphisms, \xi = U(\epsilon_A). This completely fixes the only possible construction for K. We must confirm that U(\epsilon_A) is a valid algebra structure map. The unit axiom follows immediately from the snake equation:

U(\epsilon_A) \circ \eta_{U(A)} = \mathsf{id}_{U(A)}

For the multiplication axiom, recalling \mu = U \epsilon_F, and applying naturality:

U(\epsilon_A) \circ \mu = U(\epsilon_A) \circ U_{FU(A)} = U(\epsilon_A) \circ UFU(\epsilon_A)

Functoriality is then obviously inherited from that of U. We have therefore established that the Eilenberg-Moore adjunction is the terminal resolution of \mathbb{T}. The universal morphisms are referred to as (Eilenberg-Moore) comparison functors.

An Important Relationship

As a special case of the initial and terminal resolutions above, there must be a unique morphism from the Kleisli to the Eilenberg-Moore resolution. On objects:

K_{\mathbb{T}}(A) = F^{\mathbb{T}}(A) = (\mathbb{T}(A), \mu_A)

and on morphisms

K_{\mathbb{T}}(f) = \epsilon^{\mathbb{T}}_{F(A)} \circ F^{T}(f) = \mu_A \circ \mathbb{T}(f)

From our previous remarks, this functor is full and faithful onto the full subcategory generated by objects of the form F^{\mathbb{T}}(A). Therefore, we can identify the Kleisli category with the full subcategory of free Eilenberg-Moore algebras.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: