Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 18 / 6

A monad consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1\Rightarrow T$ and $\mu :T^2\Rightarrow T$, the unit and multiplication of a monad, satisfyingAn algebra for a monad is $(A,a)$ with $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $a{\mu }_A=aTa$. A morphism of algebras for a monad $h:(A,a)\to (B,b)$ satisfies $ha=bTh$. These objects and morphisms form the Eilenberg-Moore category ${\mathcal{C}}^T$; its composition works because $T$ is a functor.

For the list monad, $TX={\coprod }_{n\ge 0}{X}^n$ is the set of finite ordered lists, including the empty list. The map $Tf$ applies $f$ to each entry; ${\eta }_X(x)=[x]$ and ${\mu }_X$ concatenates a list of lists. The unit laws say that adding singleton brackets and then flattening changes nothing. Associativity says that flattening a list of lists of lists in either order produces the same ordered sequence. These descriptions also prove naturality.

If $a:TX\to X$ is an algebra for a monad, defineThe singleton law gives $a([x])=x$. Apply the algebra associativity law to $[[],[x]]$ and $[[x],[]]$ to obtain $e\ast x=x=x\ast e$. Applying it to $[[x,y],[z]]$ and $[[x],[y,z]]$ showsThus $(X,\ast ,e)$ is a monoid. Applying the same law to $[[x_1,\dots ,x_{n-1}],[x_n]]$ shows inductively that $a$ is necessarily ordered multiplication of its entries, with the empty product $e$.

Conversely, any monoid defines such a list-fold map $a$. The monoid unit proves $a\eta =1$, and associativity and the unit prove that multiplying flattened lists equals multiplying their individual products, including empty sublists. Hence $a\mu =aTa$. An algebra morphism preserves the empty-list value and two-entry-list values, so it is a monoid homomorphism; conversely a monoid homomorphism preserves every ordered product and is an algebra morphism. ThereforeThus list-monad algebras are monoids, with the identification also matching every morphism.

The free algebra functor isThe monad laws make ${\mu }_A$ an algebra action, and naturality of $\mu$ makes $Tf$ a morphism of algebras for a monad. Let $U:{\mathcal{C}}^T\to \mathcal{C}$ forget the action. DefineThe proposed inverse is an algebra morphism becauseNaturality of $\eta$ and the algebra unit law give $(bTf){\eta }_A=f$. If $h$ is an algebra morphism, thenThe formulas are natural in both variables, so $F⊣U$. Its unit is $\eta$, and its counit at $(B,b)$ has underlying map $b:TB\to B$. Thus the monad induced by an adjunction has endofunctor $UF=T$, unit $\eta$, and multiplication $U{\epsilon }_F=\mu$. It is exactly the original monad, not merely a monad with the same endofunctor.

For an algebra for a monad $(A,a)$, consider the fork in the Eilenberg-Moore categoryHere ${\mu }_A:F(TA)\to F(A)$ is the counit at $F(A)$, and $Ta=F(a)$. The arrow $a$ is an algebra morphism by $a{\mu }_A=aTa$, which also says that it coequalizes the two arrows.

Let $h:F(A)\to (B,b)$ be an algebra morphism with $h{\mu }_A=hTa$. Define $g=h{\eta }_A:A\to B$. Naturality of $\eta$ at $a$ givesSince $h$ is an algebra morphism,Thus $g:(A,a)\to (B,b)$ is an algebra morphism with $ga=h$. Any other such factorization satisfies $g^{\prime }=g^{\prime }a{\eta }_A=h{\eta }_A=g$. This proves the full coequalizer universal property inside the algebra category.

The pair is moreover a reflexive pair: its common section is $F({\eta }_A)$, with underlying map $T{\eta }_A$, because ${\mu }_{A}T{\eta }_A=1_{TA}$ and $TaT{\eta }_A=T(a{\eta }_A)=1_{TA}$. Hence every monad algebra is a reflexive coequalizer of free algebras. This reflexive free-algebra presentation of a monad algebra needs no general existence theorem for arbitrary algebra-category colimits.