### Where Do Monads Come From?

#### Posted by Tom Leinster

If you know some category theory, you probably know that every functor with
a left adjoint induces a monad. But much less well known — and
undeservedly so — is that you don’t need your functor to have an
adjoint in order for it to induce a monad! Even a functor *without* a
left adjoint induces a monad, just as long as certain limits exist.

This is called the **codensity monad** of the functor. I’ve just
arXived a paper about them
(and ultrafilters, which I won’t
get to today). This is the first of a short series of posts explaining
what’s in my paper.

Today I’ll explain what a codensity monad is.

Here’s the grammar of it: a functor $G: \mathbf{B} \to \mathbf{A}$ may or may not have a codensity monad. If it does, it’s a monad on $\mathbf{A}$, and I’ll call it $T^G$. In the event that $G$ has a left adjoint, $F$, the codensity monad does exist, and it’s simply $G F$.

I’ll state the definition of codensity monad in four ways, using varying amounts of categorical vocabulary.

1. The slickest definition: the codensity monad of $G$ is the right Kan extension of $G$ along itself. (This may or may not exist.) The monad structure comes from the universal property of Kan extensions.

2. Slightly more explicitly, the codensity monad $T^G$ can be defined as an end: for $A \in \mathbf{A}$,

$T^G(A) = \int_B [\mathbf{A}(A, G B), G B].$

Here $[\mathbf{A}(A, G B), G B]$ is a power in $\mathbf{A}$: that is, it’s the product of lots of copies of the object $G B$, one for each element of the set $\mathbf{A}(A, G B)$. The end might or might not exist.

3. If you’re not comfortable with ends, maybe you’ll prefer the same formula expressed as a limit. Let $A \in \mathbf{A}$. Let $A/G$ be the comma category whose objects are maps $f\colon A \to G B$ (or more exactly, pairs $(B, f)$ where $B \in \mathbf{B}$ and $f \in \mathbf{A}(A, G B)$). There’s a functor $A/G \to \mathbf{A}$ sending this object to $G B$, and $T^G(A)$ is defined to be its limit (if it exists).

4. Here’s a fourth and final way to say it. For this, let’s assume that $\mathbf{B}$ is small and $\mathbf{A}$ has small limits. Then, à la Kan, the functor $G$ induces an adjunction

$Hom(-, G) : \mathbf{A} \stackrel{\longleftarrow}{\rightarrow} [\mathbf{B}, \mathbf{Set}]^{op} : Hom(-, G)$

where I’m calling both functors $Hom(-, G)$, though they’re not the same.
The left adjoint $Hom(-, G): \mathbf{A} \to [\mathbf{B}, Set]^{op}$ is defined by $(Hom(A,
G))(B) = \mathbf{A}(A, G B)$. I’ll skip the description of the right adjoint —
see the
paper if you want to know. Of
course, the right adjoint is determined by the *fact* that it’s a
right adjoint: explicitly,

$Hom_{\mathbf{A}}(A, Hom(Y, G)) \cong Hom_{[\mathbf{B}, \mathbf{Set}]}(Y, Hom(A, G))$

whenever $A \in \mathbf{A}$ and $Y \in [\mathbf{B}, \mathbf{Set}]$. Anyway, being an adjunction, it induces a monad, and this is the codensity monad of $G$.

**Example** Suppose $G$ has a left adjoint, $F$. Using any of the
descriptions above, you can show that the codensity monad $T^G$ is just
the ordinary monad $G F$ (Proposition 6.1 of my paper, but known for
donkeys’ years).

**Example** Every set $S$ has a monoid of endomorphisms $\mathbf{End}(S)$,
and an action of a monoid $M$ on $S$ can be described as a map $M \to
\mathbf{End}(S)$ of monoids. Modules over rings, representations of groups,
algebras for operads, etc., can all be described in a similar way.

What seems less well known is that algebras for monads can also be
described in this way. Let $A$ be an object of a category $\mathbf{A}$. Under mild
hypotheses, $A$ has an **endomorphism monad** $\mathbf{End}(A)$, whose crucial
feature is that for any other monad $S$ on $\mathbf{A}$, an $S$-algebra structure on
$A$ can be described as a map $S \to \mathbf{End}(A)$ of monads. It is, in fact,
the codensity monad of the functor $\mathbf{1} \to \mathbf{A}$ that picks out the single
object $A$.

Explicitly, this monad $\mathbf{End}(A)$ sends an object $X$ of $\mathbf{A}$ to the power $[\mathbf{A}(X, A), A]$. (That’s a special case of the end or limit formula above.) Why is it the case that an $S$-algebra structure on $A$ amounts to a monad map $S \to \mathbf{End}(a)$? Keep reading to find out.

**Example** Here’s something a bit more substantial. Take the
category $\mathbf{Ring}$ of commutative rings, its full subcategory $\mathbf{Field}$, and the
inclusion functor $G\colon \mathbf{Field} \hookrightarrow \mathbf{Ring}$.

There’s probably no canonical way of turning a ring into a field, and as a matter of fact, $G$ doesn’t have a left adjoint. Why not? Here’s one of many possible arguments. The category $\mathbf{Ring}$ has an initial object, $\mathbb{Z}$, and any left adjoint would send $\mathbb{Z}$ to an initial object of $\mathbf{Field}$. But $\mathbf{Field}$ has no initial object, since there are no homomorphisms between fields of different characteristics.

So, we don’t get an induced monad on $\mathbf{Ring}$ by the standard monad-from-adjunction method.

But we *do* get a codensity monad, $T^G$. It does its best to turn rings
into fields. What it actually does is turn a ring into a *product* of
fields: for a ring $A$,

$T^G(A) = \prod_{p \in Spec(A)} Frac(A/p)$

where $Spec(A)$ is the set of prime ideals of $A$ and $Frac(A/p)$ is the field of fractions of the quotient ring $A/p$.

You might wonder whether the unit map $A \to T^G(A)$ *embeds* our original ring $A$ into a product of fields (in other words, whether it’s injective). An obvious necessary condition is that $A$ contains no nilpotent elements other than zero. In fact, some basic commutative algebra implies that this is also a sufficient condition (Example 5.1 of my paper).

For instance,

$T^G(\mathbb{Z}) = \mathbb{Q} \times (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/3\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z}) \times \cdots$

which is the product of one copy each of the prime fields. (It contains $\mathbb{Z}$ as a subring.) Also, for $n \geq 1$,

$T^G(\mathbb{Z}/n\mathbb{Z}) = \prod_{primes p | n} \mathbb{Z}/p\mathbb{Z}.$

You can rewrite this as

$T^G(\mathbb{Z}/n\mathbb{Z}) = \mathbb{Z}/rad(n)\mathbb{Z}$

where $rad(n)$ is the **radical** of $n$. If you’ve been reading about
the ABC conjecture recently, you’ll have met the radical: it’s the product
of the distinct prime factors of $n$.

I want to finish by convincing you that codensity monads really do deserve to be thought of as substitutes for monads induced by adjunctions, usable in situations where no adjoint exists.

The first example above was one piece of evidence for this point of view: that if $G$ does have a left adjoint, then the codensity monad is the same thing as the monad induced by the adjunction. So, the two constructions agree where they’re both defined, but codensity monads are defined more often.

Here’s some stronger evidence that we’re doing the categorically right thing. Take, as before, a functor $G\colon \mathbf{B} \to \mathbf{A}$, and suppose that the codensity monad $T^G$ exists. Then it’s a theorem that given any monad $S$ on $\mathbf{A}$, there’s a natural one-to-one correspondence between:

- maps of monads $S \to T^G$, and
- functors $\mathbf{B} \to \mathbf{Alg}(S)$ over $\mathbf{A}$.

Here “over $\mathbf{A}$” refers to the fact that both $\mathbf{B}$ and $\mathbf{Alg}(S)$ come equipped with functors into $\mathbf{A}$ (namely, $G$ and the forgetful functor); the functor $\mathbf{B} \to \mathbf{Alg}(S)$ is required to make the obvious triangle commute. If you want a proof, you can find this as Proposition 6.2 of my paper.

(Back in the example of endomorphism monads, maybe you wondered why maps $S \to \mathbf{End}(A)$ were the same thing as $S$-algebra structures on $A$. It’s because of the result just mentioned: just take $G\colon \mathbf{1} \to \mathbf{A}$ to be the functor picking out the object $A$.)

So: the process of constructing codensity monads is adjoint to the process of constructing the category of algebras for a monad. This can be put precisely in a couple of ways, which you can find in Section 6 of my paper. I’ll just mention one.

Fix a category $\mathbf{A}$. Not every functor into $\mathbf{A}$ has a codensity monad, and certainly not every functor into $\mathbf{A}$ is monadic. Write:

- $\mathbf{CAT}/\mathbf{A}$ for the slice category of $\mathbf{CAT}$ over $\mathbf{A}$
- $(\mathbf{CAT}/\mathbf{A})_{CM}$ for the full subcategory consisting of those functors that have a codensity monad
- $(\mathbf{CAT}/\mathbf{A})_{mndc}$ for the full subcategory of monadic functors.

These are successively smaller, since any monadic functor has a left adjoint and therefore (by our very first example) a codensity monad. So we have

$(\mathbf{CAT}/\mathbf{A})_{mndc} \subseteq (\mathbf{CAT}/\mathbf{A})_{CM}.$

The theorem now is that it’s a *reflective* subcategory. That is, the
inclusion functor $(\mathbf{CAT}/\mathbf{A})_{mndc} \hookrightarrow (\mathbf{CAT}/\mathbf{A})_{CM}$ has a left
adjoint. The adjoint takes a functor $G\colon \mathbf{B} \to \mathbf{A}$ and turns it into
the forgetful functor $\mathbf{Alg}(T^G) \to \mathbf{A}$.

In other words, the canonical way to force a functor to be monadic is to first take its codensity monad, then form the corresponding monadic functor.

In future installments: ultrafilters, ultraproducts, and: what could it sensibly mean for a vector space to be compact?

## Re: Where Do Monads Come From?

This has actually been somewhat common knowledge for a bit now amongst people who are interested in both category theory and Haskell. There we have a

`Monad`

type class:that identifies monads over the category Hask, which has Haskell types as objects and Haskell functions as arrows, and is enriched in itself (or, something along those lines). Quantifiers enforce (di)naturality conditions, so one can define:

Which is the above end (and always exists). And it was known that a

`Monad`

definition could be given without knowing anything about f (it is necessarily Hask-valued, but we don’t care what kind of weird category with Hask’s objects we have to make up to make f actually a functor).I have, of course, never seen anything on the more rigorous category theory side about this, so I was never sure how flukey it was (the above is kind of like saying that for all Set-valued functors that come from a category with Set’s objects but not necessarily its morphisms, the above end exists and is a monad on Set). It’s interesting to see it generalized.

We also of course have (made up syntax for ease of presentation):

for the dual, which always has an implementation of a Comonad class.

(Also, this fact was known even earlier for a continuation passing style monad:

f is irrelevant to the

`Monad`

definition for`ContT f r`

.)