Algebras for a Monad — Eilenberg–Moore and Kleisli

Summary

Every monad $(T,\eta ,\mu )$ on $\mathsf{C}$ arises from an adjunction — in two canonical, universal ways. A $T$-algebra is a pair $(A,a:TA\to A)$ whose action satisfies a unit law $a\cdot {\eta }_A={\mathrm{id}}_A$ and an associativity law $a\cdot Ta=a\cdot {\mu }_A$; these form the Eilenberg–Moore category ${\mathsf{C}}^T$ (the category of $T$-algebras), with a free $⊣$ forgetful adjunction $F^T⊣U^T$ recovering $T$. The Kleisli category ${\mathsf{C}}_T$ has the same objects as $\mathsf{C}$ but morphisms $A\to TB$, and gives another adjunction $F_T⊣U_T$ recovering $T$; it is (equivalent to) the full subcategory of free $T$-algebras. Among all adjunctions inducing $T$, Kleisli is initial and Eilenberg–Moore is terminal, and the comparison functor $K:{\mathsf{C}}_T\to {\mathsf{C}}^T$ is full and faithful with image the free algebras.

Overview

Lemma 5.1.3 shows every adjunction induces a monad. Conversely, every monad arises from an adjunction: “perhaps surprisingly, the answer is yes — and from two (typically distinct) adjunctions that are moreover universal with this property.” A monad is a syntactic presentation of algebraic structure; its algebras are the actual structured objects (e.g. for the free-monoid monad, the algebras are monoids). This note gives both constructions and the comparison between them; whether the comparison to ${\mathsf{C}}^T$ is an equivalence is the subject of Beck’s Monadicity Theorem.

Main Content

$T$-algebra and the Eilenberg–Moore category ${\mathsf{C}}^T$ (Definition 5.2.4)

Let $(T,\eta ,\mu )$ be a monad on $\mathsf{C}$. The Eilenberg–Moore category ${\mathsf{C}}^T$, or category of $T$-algebras, has:

• objects = pairs $(A,a:TA\to A)$ ($a$ is the algebra structure map) such that the diagrams (5.2.5) commute:
  • unit: $a\cdot {\eta }_A={\mathrm{id}}_A$ ($A\stackrel{{\eta }_A}{\to }TA\stackrel{a}{\to }A$ equals the identity);
  • associativity: $a\cdot Ta=a\cdot {\mu }_A:T^{2}A\to A$;
• morphisms $f:(A,a)\to (B,b)$ = $T$-algebra homomorphisms: maps $f:A\to B$ in $\mathsf{C}$ such that the square commutes, $f\cdot a=b\cdot Tf$.

Composition and identities are as in $\mathsf{C}$.

Free $T$-algebra and the free functor (Definition 5.2.8)

For each $A\in \mathsf{C}$ the free $T$-algebra is $(TA,{\mu }_A:T^{2}A\to TA)$; the algebra axioms (5.2.5) hold by the monad’s own unit and associativity laws. This is functorial: the free functor $F^T:\mathsf{C}\to {\mathsf{C}}^T$ sends $A\mapsto (TA,{\mu }_A)$ and $f:A\to B$ to the homomorphism $F^{T}f:=Tf:(TA,{\mu }_A)\to (TB,{\mu }_B)$ (a homomorphism by naturality of $\mu$).

Eilenberg–Moore adjunction $F^T⊣U^T$ (Lemma 5.2.9)

For any monad $(T,\eta ,\mu )$ on $\mathsf{C}$ there is an adjunction

$$\mathsf{C}\underset{U^T}{\stackrel{F^T}{\rightleftarrows }}{\mathsf{C}}^T$$

whose underlying monad is $(T,\eta ,\mu )$. Here $U^T$ is the forgetful functor $(A,a)\mapsto A$ and $F^T$ is the free functor; note $U^T{F}^T=T$. The unit is $\eta :{\mathrm{id}}_{\mathsf{C}}\Rightarrow T$, and the counit $ϵ:F^T{U}^T\Rightarrow {\mathrm{id}}_{{\mathsf{C}}^T}$ has components given by the algebra structure map itself:

$${ϵ}_{(A,a)}:=((TA,{\mu }_A)\stackrel{a}{\to }(A,a)).$$

In particular $U^TϵF^T=\mu$, so the monad underlying $F^T⊣U^T$ is exactly $(T,\eta ,\mu )$.

Kleisli category ${\mathsf{C}}_T$ (Definition 5.2.10)

The Kleisli category ${\mathsf{C}}_T$ is defined by:

• objects = the objects of $\mathsf{C}$;
• morphisms $A⇝B$ = morphisms $A\to TB$ in $\mathsf{C}$.

The identity on $A$ is ${\eta }_A:A\to TA$. The composite of $f:A\to TB$ with $g:B\to TC$ is the Kleisli composite

$$A\stackrel{f}{\to }TB\stackrel{Tg}{\to }{T}^{2}C\stackrel{{\mu }_C}{\to }TC.$$

(Associativity and unitality of this composition are the monad laws.)

Kleisli adjunction $F_T⊣U_T$ (Lemma 5.2.12)

For any monad on $\mathsf{C}$ there is an adjunction $F_T⊣U_T:\mathsf{C}\rightleftarrows {\mathsf{C}}_T$ whose underlying monad is $(T,\eta ,\mu )$. The left adjoint $F_T$ is the identity on objects and sends $f:A\to B$ to $F_{T}f:={\eta }_B\cdot f(A⇝B)$; the right adjoint $U_T$ sends $A\mapsto TA$ and a Kleisli map $g:A⇝B$ (i.e. $g:A\to TB$) to $U_{T}g:={\mu }_B\cdot Tg:TA\to TB$. The hom-set isomorphism is ${\mathsf{C}}_T(F_{T}A,B)\cong \mathsf{C}(A,U_{T}B)$, both $\cong \mathsf{C}(A,TB)$.

Universal property: Kleisli initial, Eilenberg–Moore terminal (Proposition 5.2.13)

Let ${\mathsf{Adj}}_T$ be the category of adjunctions $F⊣U:\mathsf{C}\rightleftarrows \mathsf{D}$ that induce the monad $(T,\eta ,\mu )$ on $\mathsf{C}$ (morphisms = functors commuting with both adjoints). Then the Kleisli adjunction is initial and the Eilenberg–Moore adjunction is terminal: for any $F⊣U$ inducing $T$ there exist unique functors

$${\mathsf{C}}_T\stackrel{J}{\to }\mathsf{D}\stackrel{K}{\to }{\mathsf{C}}^T$$

commuting with the left and right adjoints.

The comparison functor (Lemma 5.2.14)

The canonical comparison functor $K:{\mathsf{C}}_T\to {\mathsf{C}}^T$ (from Prop 5.2.13, $D={\mathsf{C}}_T$) is full and faithful, and its image consists exactly of the free $T$-algebras: $Kc=(Tc,{\mu }_c)$. Thus the Kleisli category embeds as the full subcategory of free $T$-algebras and all maps between them. Consequently ${\mathsf{C}}_T\simeq {\mathsf{C}}^T$ iff every algebra is free — e.g. for the free vector space monad (every vector space is free on a basis), or the maybe monad (${\mathsf{Set}}_{\partial }\simeq {\mathsf{Set}}_{\ast }$).

Examples

Algebras = the expected structured objects

• Free-monoid (list) monad (Example 5.2.6(iii) / p. 188): a $T$-algebra is a set $A$ with an $n$-ary operation for each $n$ (a map ${\coprod }_{n\ge 0}{A}^n\to A$); the unit law forces the unary operation to be the identity and the associativity square forces the operations to come from a single associative binary operation with unit. The category of algebras is isomorphic to $\mathsf{Monoid}$.
• Maybe monad (Example 5.2.6(i)): a $T$-algebra is a set with a chosen basepoint (the image of $\ast$); ${\mathsf{Set}}^{(-{)}_{+}}\cong {\mathsf{Set}}_{\ast }$.
• $R{\otimes }_{\mathbb{Z}}-$ monad on $\mathsf{Ab}$ (Example 5.2.6(ii)): an algebra is an $R$-module.
• Affine-combination monad ${\mathrm{Aff}}_{\mathbb{k}}$ (Definition 5.2.3): an algebra is precisely an affine space.
• Closure operator (Example 5.2.6(iv)): an algebra for the closure operator on subsets of a space is exactly a closed subset; dually a coalgebra for the interior operator is an open subset.

Kleisli categories in computation

• Maybe monad (Example 5.2.11(i)): Kleisli maps $A⇝B$ are partially-defined functions $A\to B$; ${\mathsf{Set}}_T\cong {\mathsf{Set}}_{\partial }$.
• Free-monoid monad (5.2.11(ii)): a Kleisli map is a function $A\to {\coprod }_n{B}^n$ (each input yields a list of outputs).
• State monad $S\times (-)⊣(-{)}^S$ (5.2.11(iii)): a Kleisli map is a function $A\times S\to B\times S$ — input + current state ↦ output + updated state; this models stateful computation (“side effects”) in functional languages.
• Giry monad (5.2.11(iv)): Kleisli maps are Markov kernels; an endomorphism is a discrete-time Markov chain.

Connections

• Definitions reuse the monad laws: the algebra axioms of Definition 5.2.4 are the monad’s own unit & associativity laws, now for an action $a:TA\to A$ rather than $\mu :T^2\to A$.
• Closes the loop with Adjunctions Induce Monads: both $F^T⊣U^T$ and $F_T⊣U_T$ have underlying monad $(T,\eta ,\mu )$, proving every monad comes from an adjunction.
• Sets up monadicity: an adjunction is monadic exactly when its comparison $K:\mathsf{D}\to {\mathsf{C}}^T$ is an equivalence — see Beck’s Monadicity Theorem. For an idempotent monad, ${\mathsf{C}}^T$ is a reflective subcategory and ${\mathsf{C}}_T\simeq {\mathsf{C}}^T$ (Proposition 5.3.3, Exercise 5.3.i).
• Canonical presentations (§5.4): every algebra $(A,a)$ is a coequalizer $(T^{2}A,{\mu }_{TA})\rightrightarrows (TA,{\mu }_A)\twoheadrightarrow (A,a)$ of free algebras (Proposition 5.4.2) — the categorical “generators and relations.” See Beck’s Monadicity Theorem.

See Also

• Monads and the Monad Laws
• Adjunctions Induce Monads
• Beck’s Monadicity Theorem
• Adjoint Functors · Units and Counits · Monads - Overview
• Source: Riehl - Category Theory in Context.pdf