Codensity Monads and Kan Extensions

In this post, we are going to look at another method of constructing monads. The details are possibly more mathematically complex that those we have discussed so far, hinging on the topic of Kan extensions. We will study this construction at a fairly high level of abstraction, aiming to highlight the wide applicability of the techniques involved.

Kan Extensions

Given a category $\mathcal{D}$ , with a subcategory $\mathcal{C}$ , and a functor $G : \mathcal{C} \rightarrow \mathcal{E}$ , it is natural to ask if there is some systematic way to extend $G$ to the whole of $\mathcal{D}$ , yielding a functor $G' : \mathcal{D} \rightarrow \mathcal{E}$ ? Of course, when we look for “systematic” or “canonical” ways of doing things in category theory, we are looking for a construction with a universal property.

Although a natural motivation, the restriction to subcategories is unnecessary. Instead, for any functor $J : \mathcal{C} \rightarrow \mathcal{D}$ , and functor $G : \mathcal{C} \rightarrow \mathcal{E}$ , we are looking for a way to extend $G$ “along $J$ ” to construct a functor of type $\mathcal{D} \rightarrow \mathcal{E}$ .

It turns out, there is not one, but two mathematically natural choices, with universal properties given by the following isomorphisms, natural in $F$ :

$\mathsf{Lan}_J(G)\Rightarrow F \quad\cong\quad G \Rightarrow F \circ J$ .
$F \circ J \Rightarrow G \quad\cong\quad F \Rightarrow \mathsf{Ran}_J(G)$ .

$\mathsf{Lan}_J(G)$ and $\mathsf{Ran}_J(G)$ are respectively known as the left and right Kan extensions of $G$ along $J$ . Note that this terminology can be reversed in some parts of the literature, so it is always wise to check which universal property is being assumed. Kan extensions arise all over category theory and mathematics, for example in connection to adjunctions, (co)limits and monads, leading to MacLane’s claim “All concepts are Kan extensions”.

If these extensions exist for all $G$ , we have adjunctions involving precomposition with $J$ :

$\mathsf{Lan}_J(-) \dashv (-) \circ J \qquad\text{ and }\qquad (-) \circ J \dashv \mathsf{Ran}_J(-)$

So left Kan extensions then conveniently yield left adjoints and dually on the right, making the naming convention somewhat logical.

We can rephrase the universal properties for Kan extensions as follows:

For $\mathsf{Lan}_J(G)$ there exists a universal natural transformation $\mathsf{run} : G \Rightarrow \mathsf{Lan}_J(G) \circ J \Rightarrow G$ such that for every $\alpha : G \Rightarrow F \circ J$ there exists a unique $\hat{\alpha} : \mathsf{Lan}_J{G} \Rightarrow F$ such that $\alpha = (\hat{\alpha} \circ J) \cdot \mathsf{run}$ .
For $\mathsf{Ran}_J(G)$ there exists a universal natural transformation $\mathsf{run} : \mathsf{Ran}_J(G) \circ J \Rightarrow G$ such that for every $\alpha : F \circ J \Rightarrow G$ there exists a unique $\hat{\alpha} : F \Rightarrow \mathsf{Ran}_J(G)$ such that $\alpha = \mathsf{run} \cdot (\hat{\alpha} \circ J)$ .

So far, we have no insight into whether we can form left and right Kan extensions. Fortunately, there is some good news on this front, if $\mathcal{C}$ is a small category (has a set of objects):

If $\mathcal{E}$ is cocomplete, then $\mathsf{Lan}_J(G)$ exists for all $G$ .
If $\mathcal{E}$ is complete, then $\mathsf{Ran}_J(G)$ exists for all $G$ .

Under these conditions, there are explicit formulae for the Kan extensions in terms of the assumed (co)limits. These constructions are important, but we omit the details as we shall not need them in this post.

Example: It is common to consider functors between presheaf categories

$[\mathcal{D}^{op},\mathsf{Set}] \rightarrow [\mathcal{C}^{op},\mathsf{Set}]$

induced by precomposing with a functor $J : \mathcal{C} \rightarrow \mathcal{D}$ . By the result above, as $\mathsf{Set}$ is both complete and cocomplete, such functors always have both left and right adjoints, given by the two Kan extensions.

We note that in this way, every such $J$ induces both a monad and a comonad on $[\mathcal{D}^{op}, \mathsf{Set}]$ . These monads are not our main focus for today though.

There is another useful condition for the existence of certain Kan extensions in the presence of an adjunction. Assume $L \dashv R$ with unit and counit $\eta : \mathsf{Id} \Rightarrow R \circ L$ and $\epsilon : L \circ R \Rightarrow \mathsf{Id}$ . Then:

$\mathsf{Lan}_R(\mathsf{Id}) = L$ .
$\mathsf{Ran}_L(\mathsf{Id}) = R$ .

We also have that adjoints preserve Kan extensions in the following sense:

$L \circ \mathsf{Lan}_J(G) = \mathsf{Lan}(L \circ G)$ .
$R \circ \mathsf{Ran}_J(G) = \mathsf{Ran}(R \circ G)$ .

Kan Lifts

As an aside, we briefly mention there is a related concept of Kan lifts. These answer the question for functors $J : \mathcal{C} \rightarrow \mathcal{D}$ , and $G : \mathcal{D} \rightarrow \mathcal{E}$ of when we can “lift” $G$ to a functor $G' : \mathcal{C} \rightarrow \mathcal{E}$ . Notice the difference in direction of travel along $J$ versus Kan extensions. Again there are two possible answers, with universal properties given by natural bijections:

$\mathsf{Lift}_J(G) \Rightarrow F \quad\cong\quad G \Rightarrow J \circ F$ .
$J \circ F \Rightarrow G \quad\cong\quad F \Rightarrow \mathsf{Rift}_J(G)$ .

$\mathsf{Lift}_J(G)$ and $\mathsf{Rift}_J(G)$ are respectively the left and right Kan lifts of $G$ along $J$ . Again, if these exist for all $G$ , we have adjunctions, now involving post composition with $J$ :

$\mathsf{Lift}_J(-) \dashv J \circ (-) \qquad\text{and}\qquad J \circ (-) \dashv \mathsf{Rift}_J(-)$

One should be careful that not all the theory transfers as smoothly to lifts as it is for extensions. For example, I am not aware of an explicit construction in terms of (co)limits, or a construction similar to that we see in the next section.

Codensity Monads

For any functor

$J : \mathcal{C} \rightarrow \mathcal{D}$

we can consider the right Kan extension:

$\mathsf{Ran}_J(J) : \mathcal{D} \rightarrow \mathcal{D}$

of $J$ along itself. Assuming this exists, we have natural transformations:

$\widehat{\mathsf{id}_{\mathsf{Ran}_J(J)}} : \mathsf{Id}_{\mathcal{D}} \Rightarrow \mathsf{Ran}_J(J)$ .

and

$\widehat{ \mathsf{run} \cdot (\mathsf{Ran}_J(J) \circ \mathsf{run}) }: \mathsf{Ran}_J(J) \circ \mathsf{Ran}_J(J) \Rightarrow \mathsf{Ran}_J(J)$

(The hat should cover the whole term above, but we are reaching the limits of the latex formatting technology at our disposal).

So we have an endofunctor $\mathsf{Ran}_J(J)$ and two natural transformations with the right types to serve as a unit and multiplication for a monad. It turns out that this construction does in fact yield a monad.

If $\mathcal{D}$ is a complete category, and $\mathcal{C}$ is small, the required Kan extension always exists, so we can use this as another method to generate monads. We may return to this point in a future point, and consider concrete examples. Our aim for today is to understand exactly which monads can be constructed in this way.

Consider a monad $\mathbb{T}$ . Via the Eilenberg-Moore construction, this always arises from an adjunction $L \dashv R$ . From this, we know from the observations about Kan extensions and adjunctions above that:

$\mathsf{Ran}_L(\mathsf{Id}) = R$

and furthermore

$\mathsf{Ran}_R(R) = R \circ \mathsf{Ran}_L(\mathsf{Id}) = R \circ L = \mathbb{T}$

Therefore the endofunctor part of the monad always arises as the Kan extension of the right adjoint along itself. In fact, if we’re a bit more careful about tracking the unit and multiplication, we find that up to isomorphism, every monad arises as a codensity monad via this construction. Everything about this argument dualises smoothly, so every comonad arises as a density comonad, giving us another handle on the apparently wilder world of comonads.

Remark: Sometime you will see a claim that “this is a codensity monad”. Given that every monad is, what is normally meant by such a statement? I would normally interpret this as being about the concrete description of the monad. The Right Kan extension can be expressed as a limit, and often in a particular category a specific construction of limits is considered standard, pointing to a concrete representation of interest.

Conclusion

We have rather quickly run through some of the high-level theory of Kan extensions and codensity monads. There is a lot more to say here, particularly in terms of how specific monads arise from the codensity construction applied to mathematically natural choices of functors which aren’t merely resolutions of the chosen monad. We may return to concrete examples in later posts.

Further reading: For Kan extensions and related theory, and many other things, I would recommended “(Co)end Calculus” by Fosco Loregian. I would certainly suggest reading about the novel string diagrammatic approach to Kan extensions in “Kan Extensions for Program Optimisation Or: Art and Dan Explain an Old Trick” by my co-author Ralf Hinze. For intriguing examples of the codensity construction, “Codensity and the Ultrafilter Monad” by Leinster is a fascinating read.

2 thoughts on “Codensity Monads and Kan Extensions”

Pingback: Monad maps and Algebras Redux – Dan Marsden
Pingback: The Codensity Monad Transformer – Dan Marsden

Kan Extensions

Kan Lifts

Codensity Monads

Conclusion

Share this:

Like this:

Related

2 thoughts on “Codensity Monads and Kan Extensions”

Leave a Reply Cancel reply