# When does an endofunctor derive from an adjunction?

This is the first of two talks based on Andrea Schalk’s very good introduction to monads, which can be retrieved HERE

In the following, if $\mathcal{C}$ is a category, we indicate by $|\mathcal{C}|$ the collection of objects of $\mathcal{C}$, and by $\mathcal{C}(A,B)$ the collection of morphisms in $\mathcal{C}$ from $A$ to $B$.

As we know, there are two basic ways of defining an adjunction:

Definition 1. Let $\mathcal{C}$ and $\mathcal{D}$ be categories; let $F : \mathcal{C} \to \mathcal{D}$ and $G : \mathcal{D} \to \mathcal{C}$ be functors. An adjunction from $F$ to $G$, written $F \dashv G$, is a quadruple $(F,G,\eta,\varepsilon)$ where $\eta: \mathrm{Id}_\mathcal{C} \to GF$ (the unit of the adjunction) and $\varepsilon: FG \to \mathrm{Id}_\mathcal{D}$ (the counit) are natural transformations such that , for every $A \in |\mathcal{C}|$ and $S \in |\mathcal{D}|$, $G\varepsilon_S \circ \eta_{GS} = \mathrm{id}_{GS}$ and $\varepsilon_{FA} \circ F\eta_{A} = \mathrm{id}_{FA}$.

Definition 2. Let $\mathcal{C}$ and $\mathcal{D}$ be categories. We call adjunction quadruple a quadruple $(F, G, \eta, (\cdot)^\sharp)$ such that:

1. $G : \mathcal{D} \to \mathcal{C}$ is a functor,
2. $F : |\mathcal{C}| \to |\mathcal{D}|$ is a mapping, and
3. $\eta$ associates to every object $A$ a morphism $\eta_A : A \to GFA$ so that
4. for every $f : A \to GS$ there exists a unique $f^\sharp : FA \to S$ such that $Gf^\sharp \circ \eta_A = f$.

The two definitions above are equivalent in the following sense. If $(F, G, \eta, \varepsilon)$ is an adjunction according to Definition 1, and $f^\sharp = \varepsilon_S \circ Ff$, then $(F, G, \eta, (\cdot)^\sharp)$ is an adjunction quadruple according to Definition 2. On the other hand, if $(F, G, \eta, (\cdot)^\ast)$ is an adjunction quadruple according to Definition 2, and $(\cdot)_\flat$ is the inverse operation of $(\cdot)^\sharp$—that is, $g_\flat = f$ if and only if $f^\sharp = g$—then necessarily $\eta_A = (\mathrm{id}_{FA})_\flat$, and by putting $Ff = (\eta_B \circ f)^\sharp$ for $f \in \mathcal{C}(A,B)$ and $\varepsilon_S = (\mathrm{id}_{GS})^\sharp$ for $S \in |\mathcal{D}|$ we define an adjunction according to Definition 1.

If $(F,G, \eta, \varepsilon)$ is an adjunction, then $T = GF : \mathcal{C} \to \mathcal{C}$ is an endofunctor.The first question that comes to our mind is:

when does an endofunctor derive from an adjunction?

Let us check some basic properties such an endofunctor must satisfy. First of all, $\mu : T^2 \to T$ defined by $\mu_A = G\varepsilon_{FA}$ is a natural transformation and satisfies

$\mu_A \circ T\eta_A = \mu_A \circ \eta_{TA} = \mathrm{id}_{TA} \;\; \forall A \in |\mathcal{C}|$

Moreover, as $\varepsilon : FG \to \mathrm{Id}_{\mathcal{D}}$ is a natural transformation, by choosing $f = \varepsilon_{FA}$ we get $\varepsilon_{FA} \circ \varepsilon_{FGFA} = \varepsilon_{FA} \circ FG\varepsilon_{FA}$, which after an application of $G$ yields

$\mu_A \circ \mu_{TA} = \mu_A \circ T\mu_A \;\; \forall A \in |\mathcal{C}|$

It will turn out that these two properties are precisely what we need.

Definition 3. A monad on a category $\mathcal{C}$ is a triple $T = (T, \eta, \mu)$ where:

1. $T : \mathcal{C} \to \mathcal{C}$ is an endofunctor,
2. $\eta : \mathrm{Id}_\mathcal{C} \to T$ and $\mu: T^2 \to T$ are natural transformations, and
3. for every $A \in |\mathcal{C}|$ we have $\mu_A \circ \eta_{TA} = \mu_A \circ T\eta_A = \mathrm{id}_{TA}$ and $\mu_A \circ \mu_{TA} = \mu_A \circ T\mu_A$,

As a very basic example, the free monoid construction is a monad on $\mathbf{Set}$, where $TA = A^\ast$, $Tf(s) = [f(a) \; \mathtt{for} \; a \; \mathtt{in} \; s]$, $\eta_A(a) = [a]$, and $\mu_A([[a^1_1, \ldots, a^1_{n_1}], \ldots, [a^m_1, \ldots, a^m_{n_m}]] = [a^1_1, \ldots, a^1_{n_1}, \ldots, a^m_1, \ldots, a^m_{n_m}]$.

As a less basic example, suppose $\mathcal{C} = (S, \leq)$ is a poset: what is a monad on $\mathcal{C}$? First of all, an endofunctor on a poset is a monotone function; next, if there is $\eta_A : A \to TA$, then $A \leq TA$; finally, if there is $\mu_A : T^2A \to TA$, then $T^2A \leq TA$, which together with the previous inequality yields $T^2A = TA$. On the other hand, any nondecreasing idempotent is the endofunctor component of a monad: the monad equations are actually ensured by $\mathcal{C}$ being a poset, so that any two maps with same domain and same codomain are equal.

We then restate our original problem as follows:

given a monad $T = (T, \eta, \mu)$, find an adjunction $(F, G, \eta, \varepsilon)$ such that $T = GF$ and $\mu = G \varepsilon_F$

If the adjunction $(F, G, \eta, \varepsilon)$ solves the problem above, we say that it generates the monad $T$.

The first solution to this problem was given by the Swiss mathematician Heinrich Kleisli, and is based on an alternative way of defining monads, as it is the case with adjunctions. Let us suppose $T = GF$ with $F \dashv G$. If $f : A \to TB = G(FB)$, then $f^\sharp : FA \to FB$, so that $Gf^\sharp : TA \to TB$: and we know from the definition of monad that $Gf^\sharp \circ \eta_A = f$. We can thus define an operator $(\cdot)^\ast$ that takes $f \in \mathcal{C}(A,TB)$ into $f^\ast \in \mathcal{C}(TA,TB)$ in a way such that $f^\ast \circ \eta_A = f$ whatever $f$ is. The simplest example is $f = \eta_A$ itself, so that $(\eta_A)^\ast \circ \eta_A = \eta_A$, and $(\eta_A)^\ast = \mathrm{id}_{TA}$ by uniqueness in the definition of adjunction quadruple. Moreover, if $f : A \to TB$ and $g : B \to TC$, then

$g^\ast \circ f = Gg^\sharp \circ (Gf^\sharp \circ \eta_A) = (g^\ast \circ f^\ast) \circ \eta_A \;,$

which implies $(g^\ast \circ f)^\ast = g^\ast \circ f^\ast$ by uniqueness.

This is the base of Kleisli’s solution to our problem, which we will discuss in a future talk.