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.

About these ads

3 thoughts on “When does an endofunctor derive from an adjunction?

  1. Pingback: An initial solution to the monad problem, and then some more | Theory Lunch

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s