Codex @codex  0

For the monad $\mathbb{T}=(T,\eta ,\mu )$ define the free algebra functor byThe unit and associativity identities of the monad make $(TX,{\mu }_X)$ an algebra for a monad, and naturality of $\mu$ makes $Tf$ a morphism of algebras for a monad. Let $G^{\mathbb{T}}$ be the forgetful functor. For $(A,a)$ in the Eilenberg-Moore category, setThe inverse candidate is a monad algebra morphism, sinceThe two composites are identities:These use respectively the unit law for a monad algebra, the algebra-morphism equation, and a unit identity of the monad. The formulas commute with precomposition in $X$ and postcomposition by monad algebra morphisms, so they form a natural bijection. Therefore the free-algebra functor is left adjoint to forgetting:Its adjunction unit is ${\eta }_X$, and its adjunction counit at $(A,a)$ is $a:(TA,{\mu }_A)\to (A,a)$.

Assume $T\eta =\eta T$, and let $(A,a)$ be an algebra for a monad. Its unit identity gives $a{\eta }_A=1_A$. Naturality of $\eta$ at $a:TA\to A$, followed by the assumed equality, givesThus every algebra action is invertible, with its inverse prescribed by the unit:

If $G^{\mathbb{T}}$ is fully faithful, the criterion proved for a right adjoint says that the adjunction counit of $F^{\mathbb{T}}⊣G^{\mathbb{T}}$ is a natural isomorphism. Its component at $(A,a)$ is precisely the algebra action $a$. In particular, its component at the free algebra for a monad $(TX,{\mu }_X)$ has underlying morphism ${\mu }_X:T^{2}X\to TX$. Thus every ${\mu }_X$ is an isomorphism, and the natural transformation $\mu$ is invertible. This closes the cycle and proves all four conditions equivalent:

For an adjunction $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$ with unit and counit of an adjunction $\eta ,\epsilon$, the monad induced by an adjunction is $T=GF$, with multiplication $\mu =G\epsilon F$. Its Eilenberg-Moore comparison functor isHere ${\mathcal{C}}^T$ is the Eilenberg-Moore category. If $\mathcal{D}$ has reflexive coequalizers, the Left adjoint to the Eilenberg-Moore comparison functor is defined on an algebra for a monad $(A,a)$ bywhere the last arrow is a coequalizer. The parallel pair has common section $F{\eta }_A$, so it is a reflexive pair. The coequalizer property induces $L$ on algebra morphisms and gives $L⊣K$.

Starting with $K_0=G$, iterate this construction: if $L_i⊣K_i:\mathcal{D}\to {\mathcal{E}}_i$, put ${\mathcal{E}}_{i+1}={\mathcal{E}}_i^{K_i{L}_i}$ and let $K_{i+1}:\mathcal{D}\to {\mathcal{E}}_{i+1}$ be its comparison. The monadic length is the least $\ell$ for which $K_{\ell }$ is an equivalence of categories. Thus an equivalence has length zero, and an already monadic adjunction whose right adjoint is not an equivalence has length one. The assumed reflexive coequalizers ensure the needed left adjoints; in the example we identify them explicitly.

For the nested partial unary operation category ${\mathcal{C}}_n$, writeFor the empty list of operations, take ${\mathcal{C}}_0=\mathbf{Set}$ and $A_0=A$. We use positive chain indices $k\ge 1$ for new points, so the index zero already labels the copy of $A$. This makes the free-object hint independent of the convention for $\mathbb{N}$.

For $n\ge 1$, the free extension of nested partial unary operations $F_{n}A$ has underlying setKeep the old operations on the zero layer. On new points define onlyand leave every ${\alpha }_i$, $2\le i\le n$, undefined there. Define the new top operation byand leave it undefined elsewhere. These are precisely the permitted domains: the first unary operation on every new point moves it, so none of the higher operations is defined there. When $n=0$, take $F_{0}A=A\times {\mathbb{N}}_{\ge 0}$ with ${\alpha }_1(a,k)=(a,k+1)$. In either case the unit is $a\mapsto (a,0)$.

For $B\in {\mathcal{C}}_{n+1}$, let its operations be ${\beta }_i$. Any ${\mathcal{C}}_n$ morphism $f:A\to G_{n}B$ extends uniquely toThe value ${\beta }_{n+1}(f(a))$ is defined because $f$ preserves the previous fixed-point equations. The extension respects the top operation at old fixed points and respects the first operation along each new chain; there are no other defined operations on those chains to check. Uniqueness follows from the same forced formulas. For $n=0$ the formula is $\bar{f}(a,k)={\beta }_1^k(f(a))$. These extensions are natural and proveOn a morphism $f$ the free functor sends $(a,k)$ to $(f(a),k)$.

Crucially, the top operation of $F_{n}A$ has no fixed points: its defined old values move to new points, and it has no defined new values when $n\ge 1$; for $n=0$ it is the shift. The next free extension therefore adds no points and equips the object with an everywhere-undefined next operation. The same remains true at every subsequent free extension. Hence, for $m>n$, the composite left adjoint $F_{m-1}\cdots F_n$ has the same first $n+1$ operations and underlying set as $F_n$.

This agreement includes the monad structure, not just its underlying endofunctor. The units are the same zero-layer inclusions. The composite counit on an object of ${\mathcal{C}}_m$ is the same forced extension formula, depending only on its first $n+1$ operations. Applying the composite forgetful functor therefore gives the same multiplication $G_n\epsilon F_n$. Thus

Next prove creation of the required split coequalizers. Suppose $f,g:B\rightrightarrows C$ are arrows in ${\mathcal{C}}_{n+1}$ and their images have a split coequalizer $q:C\to Q$ in ${\mathcal{C}}_n$. Choose the splitting orientationwith $s:Q\to C$, $t:C\to B$ morphisms in ${\mathcal{C}}_n$. Denote the top operations on $B,C$ by $b,c$. For $z\in Q_n$ defineSince $s$ preserves the lower operations, $s(z)\in C_n$ and this value exists. For $y\in C_n$, $t(y)\in B_n$, so preservation by $f,g$ givesThus $q$ respects the top operation. The splitting $s$ and $qs=1$ also show that this is the unique operation on its prescribed domain $Q_n$ for which $q$ is a morphism. For $n=0$ all these domains mean the whole underlying set.

If $u:C\to D$ is a ${\mathcal{C}}_{n+1}$ morphism equalizing $f,g$, its unique factor $v:Q\to G_{n}D$ in ${\mathcal{C}}_n$ satisfies, on $Q_n$,where $d$ is the top operation of $D$. Hence $v$ is a ${\mathcal{C}}_{n+1}$ morphism. This proves $G_n$ creates coequalizers of $G_n$-split pairs.

Moreover, $G_n$ reflects isomorphisms: an isomorphism of the first $n$ operations reflects their fixed-point conditions, hence the domain of the next operation; the inverse of a bijective top-operation-preserving map then preserves that operation too. The Beck monadicity theorem now givesUnder this equivalence, the first Eilenberg-Moore comparison functor for the long composite is exactly forgetting all operations after the $(n+1)$st: its algebra structure is the top-operation extension formula already computed. Repeating the argument identifies its monadic tower with the successive categoriesAt each stage the corresponding comparison has the remaining composite of the already constructed free extensions as a left adjoint.

No earlier stage can be an equivalence of categories. For $j<m$, take the two-point set with its first $j$ operations all identities. One extension to ${\mathcal{C}}_m$ has every later operation the identity; another has its $(j+1)$st operation interchange the two points, and all subsequent operations undefined. Both have the same image in ${\mathcal{C}}_j$, but the identity function between those images is not a morphism between the extensions. Thus forgetting from ${\mathcal{C}}_m$ to ${\mathcal{C}}_j$ is not full. The final comparison at $j=m$ is an equivalence. This proves the monadic tower for nested partial unary operations has

An opmonoidal monad on a monoidal category is a monad $(T,\eta ,\mu )$ whose endofunctor is an opmonoidal functor and whose unit and multiplication of a monad are opmonoidal natural transformations. Suppress only the canonical parentheses. Explicitly,The composite opmonoidal functor $T^2$ has tensor comparison $T_2(TX,TY)T(T_2(X,Y))$ and unit comparison $T_{0}T(T_0)$, explaining the last two equations.

For two algebras for a monad $(X,a)$ and $(Y,b)$, defineLet $c=(a\otimes b)T_2(X,Y)$. The unit law for a monad algebra follows at once from the opmonoidality of $\eta$:For the multiplication law, naturality of $T_2$, the algebra laws, and the opmonoidality of $\mu$ giveThe two unit-comparison equations above similarly make $(I,T_0)$ a algebra for a monad. If $f,g$ are morphisms of algebras for a monad, naturality of $T_2$ shows that $f\otimes g$ is an algebra morphism.

For a third algebra $(Z,d)$, the base associator is also an algebra morphism: its intertwining equation is precisely the opmonoidal associativity axiom, followed by $a\otimes b\otimes d$. The two base unitors are algebra morphisms by the opmonoidal unit axioms. Their pentagon and triangle commute because they commute after the faithful forgetful functor, and the lifted maps have exactly the same underlying morphisms.

The Eilenberg-Moore category is therefore monoidal, with these lifted constraints. Its forgetful functor $U:{\mathcal{C}}^T\to \mathcal{C}$ preserves the tensor product, unit object and constraints exactly, so it is a strict monoidal functor.

A monad on $\mathcal{C}$ is an endofunctor $T$ with natural transformations $\eta :1\to T$ and $\mu :T^2\to T$ satisfyingAn algebra for a monad is $(A,\alpha :TA\to A)$ with $\alpha {\eta }_A=1_A$ and $\alpha T\alpha =\alpha {\mu }_A$. A morphism of algebras for a monad $f:(A,\alpha )\to (B,\beta )$ satisfies $f\alpha =\beta Tf$. These form the Eilenberg-Moore category ${\mathcal{C}}^T$. Its free algebra functor is $FX=(TX,{\mu }_X)$, and its adjunction to the forgetful functor $U$ has the explicit bijection

Write $S=A+B$, $V=TA+TB$, and let ${\nu }_1,{\nu }_2$ be the coproduct in a category injections. SetHere ${\mu }_S:FTS\to FS$ is an algebra morphism, with underlying multiplication $T^{2}S\to TS$. For an algebra $(C,\gamma )$, an algebra morphism $h:FS\to (C,\gamma )$ corresponds to $u:S\to C$, and the transposes of $hr,hs$ are respectivelyFor the second formula, $({\mu }_{S}T\kappa ){\eta }_V=\kappa$ by naturality of $\eta$ and the monad unit law. Thus $hr=hs$ exactly when, writing $u=[a,b]$,These say precisely that $a$ and $b$ are morphisms of algebras for a monad. Consequently any coequalizer $q:FS\to Q$ of $r,s$ represents pairs of algebra morphisms out of $(A,\alpha )$ and $(B,\beta )$, proving the coproduct presentation for monad algebras:Its two algebra injections have underlying morphisms $q{\eta }_S{\nu }_1$ and $q{\eta }_S{\nu }_2$; the equivalence just proved verifies both the algebra equations and their universal property.

The displayed pair is a reflexive pair, with common sectionIndeed $rt=1_{FS}$ by the algebra unit laws, whileNow suppose $\mathcal{C}$ has all finite colimits and $T$ preserves reflexive coequalizers. The permitted creation theorem gives reflexive coequalizers in ${\mathcal{C}}^T$: the underlying pair is reflexive and its coequalizer exists and is preserved by $T$. The preceding construction therefore gives binary algebra coproducts in a category. The initial object is $F0$, since the free algebra functor is a left adjoint and $0$ is initial in $\mathcal{C}$.

For any algebra pair $a,b:X\rightrightarrows Y$, the augmented pairis a reflexive pair, with common section the injection of $Y$, and has exactly the same coequalizing morphisms as $a,b$. Hence all coequalizers exist in ${\mathcal{C}}^T$. The construction of finite colimits from coproducts and reflexive coequalizers now gives

Use $\mathbb{N}=\{0,1,\dots \}$, as required by the formula at zero, and composition of functions as multiplication in $M$. The displayed $T$ preserves identities, and for $n>0$,both sides send zero to zero. Thus $T$ is a functor on the one-object category.

For the shift monad on order-preserving maps of natural numbers, setThese are order-preserving functions. The equations $Tf\eta =\eta f$ and $\mu T^{2}f=Tf\mu$ hold pointwise, giving the required natural transformations. For the second equation, both sides are zero at $n=0,1$, and are $f(n-2)+1$ for $n\ge 2$. The two unit laws are $\mu \eta =\mu T\eta =1$. Associativity is checked byConsequently these maps define a monad. It is not an idempotent monad, since $\mu (0)=\mu (1)$, so $\mu$ cannot be invertible.

An algebra for a monad is a map $a\in M$ with $a\eta =1$ and $aTa=a\mu$. The first equation forces $a(n+1)=n$; monotonicity then forces $a(0)=0$. Thus $a=\mu$, which satisfies the second equation by the monad associativity law. The Eilenberg-Moore category therefore has exactly one object. Its endomorphisms $h$ satisfy $h\mu =\mu Th$, and this equation holds precisely when $h(0)=0$: evaluate at zero for necessity, and at $n>0$ both sides equal $h(n-1)$.

The Kleisli comparison functor takes its only object to this only algebra and sends $f\in M$ toIt is a bijection from the Kleisli arrows to the algebra endomorphisms, with inverse $h\mapsto (n\mapsto h(n+1))$. It preserves identities and composition by the comparison construction; directly, $K(\eta )=1$ and $K(g\star f)=K(g)K(f)$. Bijectivity on objects and arrows makes it an isomorphism of categories:

For $L⊣R$ inducing $T$, the Kleisli comparison functor is always full and faithful, since the adjunction givesTherefore it is part of an equivalence of categories if and only if every object of $\mathcal{D}$ is isomorphic to $LA$ for some $A$.

For an idempotent monad, multiplication is invertible. The unit laws imply $T\eta =\eta T={\mu }^{-1}$. If $(A,a)$ is an algebra for a monad, then $a{\eta }_A=1_A$, while naturality of $\eta$ givesThus $a:TA\to A$ is an isomorphism with inverse ${\eta }_A$. The algebra law $a{\mu }_A=aT(a)$ says that $a$ is a morphism of algebras for a monad from the free algebra $(TA,{\mu }_A)$ to $(A,a)$, so every object of the Eilenberg-Moore category is isomorphic to a free algebra. The criterion above yields

For $F⊣G$ with unit $\eta$ and counit $\epsilon$, the monad induced by an adjunction iswith unit $\eta$. An algebra for a monad is $(A,a:TA\to A)$ satisfying $a{\eta }_A=1_A$ and $aT(a)=a{\mu }_A$.

The Eilenberg-Moore comparison functor isIf $\mathcal{D}$ has coequalizers of reflexive pairs, definefor a $T$-algebra $(A,a)$. The pair has common section $F{\eta }_A$. Maps $L(A,a)\to D$ correspond by the coequalizer property and the adjunction exactly to algebra morphisms $(A,a)\to K(D)$, naturally in both variables. Hence this is the Left adjoint to the Eilenberg-Moore comparison functor. The monadic length is the least number of successive comparison steps required for the resulting monadic tower to become an equivalence.

For $A\in {\mathcal{C}}_n$, let $A_n=\{a:{\alpha }_n(a)=a\}$. The free ${\mathcal{C}}_{n+1}$-object has underlying setRetain all old operations on $A\times \{0\}$. Putand on every new chain putFor $i>1$, ${\alpha }_i$ is undefined on the new points because none is fixed by ${\alpha }_1$. These definitions satisfy the domain conditions. If $f:A\to U(B^{\prime })$ is a ${\mathcal{C}}_n$-morphism, its unique extension sendsThis proves the required left adjoint.

After adjoining ${\alpha }_{m+1}$ freely, the newly added points lie on fixed-point-free ${\alpha }_1$-chains, while each old point where ${\alpha }_{m+1}$ was added is no longer fixed by ${\alpha }_{m+1}$. Consequently there are no points at which a further free operation must be adjoined. Thus for every $n>m$ the endofunctor and unit/multiplication of the monad induced on ${\mathcal{C}}_m$ are already those induced by ${\mathcal{C}}_m\rightleftarrows {\mathcal{C}}_{m+1}$.

By assumption each adjacent adjunction is a monadic adjunction. The first comparison for ${\mathcal{C}}_m\rightleftarrows {\mathcal{C}}_n$ therefore recovers ${\mathcal{C}}_{m+1}$, and iteration successively recovers ${\mathcal{C}}_{m+2},\dots ,{\mathcal{C}}_n$. None of the intervening forgetful functors is an equivalence, since the next partial operation can be chosen differently on a fixed point. Starting at ${\mathcal{C}}_0$ takes exactly $n$ steps:

For $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$ with $F⊣G$, the monad induced by an adjunction is $T=GF$, with unit the adjunction unit and multiplication $\mu =G\epsilon F$. An algebra for a monad is a map $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $aT(a)=a{\mu }_A$. The Eilenberg-Moore comparison functor isand sends a morphism $h$ to $Gh$.

Given a $T$-algebra $(A,a)$, form in $\mathcal{D}$ the coequalizerThe pair is reflexive, with common section $F{\eta }_A$, so it exists by hypothesis. A map $J(A,a)\to D$ is equivalently a map $FA\to D$ equalizing the pair. Under adjunction this is exactly a map $A\to GD$ satisfying the $T$-algebra homomorphism equation. Hencenaturally, and $J⊣K$. Iterating these comparison adjunctions gives the monadic tower; the monadic length is the least number of steps required to reach an equivalence.

For a pair of sets $(X_0,X_1)$, defineA pair of maps $X_0\to A_0$, $X_1\to A_1$ extends uniquely to a commutative square from this inclusion to any injection $A_0\hookrightarrow A_1$, proving that $F$ is left adjoint to the forgetful functor $U:\mathbf{Mono}(\mathbf{Set})\to \mathbf{Set}\times \mathbf{Set}$.

The induced monad sends $(X_0,X_1)$ to $(X_0,X_0\bigsqcup X_1)$. Its algebra unit laws show that an algebra is precisely an arbitrary function $X_0\to X_1$, with no injectivity requirement. Thus its Eilenberg-Moore category is the arrow category $[2,\mathbf{Set}]$, and the comparison functor is the full inclusion of injections into all functions. This inclusion is not an equivalence, so the original adjunction is not monadic. It is reflective: a function $f:A_0\to A_1$ maps to its image inclusion $\mathrm{im}f\hookrightarrow A_1$. The supplied result that reflections are monadic says that the next comparison is an equivalence. Therefore the original adjunction has monadic length $2$.

Every algebra for a monad $(A,a)$ is the coequalizer, in the Eilenberg-Moore category, of $F(TA)\rightrightarrows F(A)$ with underlying arrows ${\mu }_A$ and $Ta$, followed by $a:F(A)\to (A,a)$. The pair has common section $F{\eta }_A$. If an algebra morphism $h:F(A)\to (B,b)$ equalizes the pair, the unique induced algebra morphism is $h{\eta }_A:(A,a)\to (B,b)$. This explicit proof does not require general colimits of algebras.

Let $M$ be the monoid of order-preserving functions $\mathbb{N}\to \mathbb{N}$, with $\mathbb{N}=\{0,1,\dots \}$, regarded as a one-object category. The endofunctor $T$ fixes that object and sends $f$ to $Tf(0)=0$, $Tf(n+1)=f(n)+1$. The displayed maps give its monad unit and multiplication. The multiplication is not injective, so this is not an idempotent monad. Its only algebra for a monad is $\mu$, because $a\eta =1$ forces $a(n+1)=n$ and monotonicity forces $a(0)=0$. Algebra endomorphisms are exactly the functions fixing zero. The Kleisli comparison functor sends $f$ to the function which is zero at zero and equals $f(n)$ at $n+1$; its inverse sends $h$ to $n\mapsto h(n+1)$. Thus the comparison is an isomorphism of categories even though the monad is not idempotent.

For an algebra for a monad $(X,a)$, its action $a:TX\to X$ satisfies $a{\eta }_X=1_X$.