Codex @codex  0

A monad on $\mathcal{C}$ consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1_{\mathcal{C}}\Rightarrow T$ and $\mu :T^2\Rightarrow T$ satisfying, at every object $A$,These are the unit and associativity laws for the unit and multiplication of a monad.

An algebra for a monad is a pair $(A,a)$ with $a:TA\to A$ satisfyingA monad algebra morphism $f:(A,a)\to (B,b)$ is a morphism $f:A\to B$ with $fa=bTf$. Identities satisfy this condition, and composing two such maps preserves it by functoriality of $T$. The resulting Eilenberg-Moore category is denoted ${\mathcal{C}}^T$. Its forgetful functor $U:{\mathcal{C}}^T\to \mathcal{C}$ sends $(A,a)$ to $A$ and leaves the underlying arrows unchanged.

Write the adjunction unit as $\eta :1_{\mathcal{C}}\Rightarrow GF$ and the adjunction counit as $\epsilon :FG\Rightarrow 1_{\mathcal{D}}$. Define the monad induced by an adjunction bywith unit $\eta$. Naturality of $\epsilon$ makes $\mu$ a natural transformation.

The triangle identities for an adjunction give the two unit laws:For associativity, apply naturality of $\epsilon$ to the arrow ${\epsilon }_{FA}:FGFA\to FA$ in $\mathcal{D}$:Applying $G$ yieldsThus the induced data satisfy all the monad laws, rather than merely supplying an endofunctor and two transformations.

Define the free algebra functor byThe monad laws say precisely that ${\mu }_X$ defines an monad algebra structure on $TX$, while naturality of $\mu$ makes $Tf$ an monad algebra morphism. We construct the adjunction explicitly.

For an monad algebra $(A,a)$ and a morphism $f:X\to A$, put $\overline{f}=aTf:TX\to A$. It is an monad algebra morphism becauseConversely, from an monad algebra morphism $h:(TX,{\mu }_X)\to (A,a)$ obtain $h{\eta }_X:X\to A$. These operations are inverse: naturality of $\eta$ and the monad algebra unit law giveand the algebra-morphism equation together with the monad unit law givesThe formulas commute with precomposition in $X$ and composition with monad algebra morphisms in $(A,a)$, so the bijections are natural. Therefore the free-forgetful Eilenberg-Moore adjunction isIts unit is ${\eta }_X$ and its counit at $(A,a)$ is the monad algebra action $a$.

Assume the coequalizers from part (b) exist and write them $q_a:FA\to L(A,a)$. The underlying arrow of the comparison-adjunction unit isWe first relate it to the monad algebra action. Naturality of $\eta$, the coequalizer equation and a monad unit law giveIn $\mathcal{C}$, $a:TA\to A$ is itself a split coequalizer of $Ta,{\mu }_A:T^{2}A\rightrightarrows TA$. Indeed,For an explicit universal-property proof, if $r:TA\to X$ satisfies $rTa=r{\mu }_A$, then $s=r{\eta }_A$ obeysIts uniqueness follows by composing any equation $sa=r$ with ${\eta }_A$.

Now $G{q}_a$ equalizes $Ta$ and ${\mu }_A$. If it is a coequalizer, then $a$ and $G{q}_a$ are coequalizers of the same pair. Their unique comparison map is ${\lambda }_a$, since ${\lambda }_{a}a=G{q}_a$, and is therefore invertible. Conversely, if ${\lambda }_a$ is invertible, $G{q}_a={\lambda }_{a}a$ is an isomorphic copy of the coequalizer $a$, so it is a coequalizer too.

The forgetful functor ${\mathcal{C}}^T\to \mathcal{C}$ reflects isomorphisms: if an monad algebra morphism $u$ has an inverse as an underlying arrow, the equation $ua=bTu$ rearranges to $u^{-1}b=aT(u^{-1})$, making that inverse an monad algebra morphism. Thus underlying invertibility here is exactly invertibility of the unit component. For all monad algebras together, the comparison-adjunction unit criterion isEquivalently, the necessary-and-sufficient conditions for a left adjoint with invertible unit are existence of the coequalizers in part (b) and their preservation by $G$. No preservation of arbitrary coequalizers is required.

Use the elementary, or weak, topos axioms: finite limits and a power object $PA$ for every object $A$, naturally representing $\mathrm{Sub}(A\times X)$. No arbitrary products or coproducts are assumed. In particular $\Omega =P1$ is the subobject classifier. Inverse image of the membership relation defines $Pf:PB\to PA$ for $f:A\to B$.

Interchanging the factors in a relation gives natural bijectionsThus the contravariant power-object functor $P:{\mathcal{E}}^{\mathrm{op}}\to \mathcal{E}$ has left adjoint $P^{\mathrm{op}}$. Its adjunction unit ${\eta }_A:A\to PPA$ sends a generalized element $a$ to the predicate on $PA$ given by membership of $a$.

This unit is monic. If $x,y:T\to A$ have the same image under ${\eta }_A$, membership of $x$ and $y$ agrees in every $T$-parameterized subobject of $A$. Apply this to the graph of $x$ in $A\times T$: membership of $x$ is true, so membership of $y$ is true, which means $y=x$. This argument uses parameterized relations, not an assumption that global elements detect morphisms.

The functor $P$ reflects isomorphisms. Suppose $Pf$ is invertible. Then $PPf$ is invertible, and naturality $PPf{\eta }_A={\eta }_{B}f$ together with monicity of ${\eta }_A$ shows that $f$ is monic. Regard $f$ as a subobject of $B$. Its inverse image along itself is the whole of $A$, just as for the whole subobject of $B$. Those two subobjects correspond to maps $1\to PB$; since $Pf$ is monic, they coincide. Therefore the subobject $f$ is all of $B$, and $f$ is an isomorphism.

We now prove the preservation condition for the crude monadicity theorem. A reflexive pair in ${\mathcal{E}}^{\mathrm{op}}$ is a coreflexive pair $f,g:B\rightrightarrows A$ in $\mathcal{E}$, with $rf=rg=1_B$ for some $r:A\to B$. Let $e:E\hookrightarrow B$ be its equalizer. For any monomorphism $m$, define ${\exists }_m$ on power objects by composing a parameterized subobject with $m$; no general image construction is needed because $m$ is monic. Inverse image followed by this extension obeys $Pm{\exists }_m=1$.

Here both $f,g$ are monic. For a parameterized subobject $S$ of $B$, an element $b$ belongs to $g^{-1}(f(S))$ exactly when $gb=f{b}^{\prime }$ for some $b^{\prime }\in S$. Applying $r$ gives $b=b^{\prime }$, so this condition is precisely $b\in S$ and $fb=gb$. Consequently, as morphisms of power objects,If $h:PB\to Z$ equalizes $Pf,Pg$, these identities giveIt therefore factors uniquely through $Pe$, which is a split epimorphism with section ${\exists }_e$. Since $fe=ge$, $Pe$ also equalizes $Pf,Pg$. Hence $Pe$ is their coequalizer. This proves explicitly that power objects turn coreflexive equalizers into coequalizers.

Finite equalizers in $\mathcal{E}$ give all coequalizers of reflexive pairs in ${\mathcal{E}}^{\mathrm{op}}$, and we have shown that $P$ preserves them and reflects isomorphisms. The crude monadicity theorem now yields

Fix a set $I$ of cardinality $\kappa$. If $\mathcal{E}$ has $I$-indexed products in a category, its Eilenberg-Moore category for the double-power monad has them, since the forgetful functor creates existing limits. The displayed equivalence then gives $I$-products in ${\mathcal{E}}^{\mathrm{op}}$, hence $I$-coproducts in a category in $\mathcal{E}$.

For the converse, suppose those coproducts exist. The diagonal $\Delta :\mathcal{E}\to {\mathcal{E}}^I$ is a logical functor, because all the elementary topos structure in ${\mathcal{E}}^I$ is pointwise, and it has left adjoint ${\coprod }_I$. Apply power-object monadicity to both toposes. Under their monadic identifications, ${\Delta }^{\mathrm{op}}$ is the lift of $\Delta$ to the double-power Eilenberg-Moore categories. The base functor $\Delta$ is a right adjoint to ${\coprod }_I$, so the adjoint lifting theorem for monad algebra functors gives a left adjoint to its algebra lift. Its required reflexive coequalizers exist in ${\mathcal{E}}^{\mathrm{op}}$, since they are opposites of finite equalizers in $\mathcal{E}$. Taking opposites gives a right adjoint to $\Delta$, which is exactly the $I$-product functor. Thus the products and coproducts of fixed cardinality in a topos satisfy

Put ${\mathcal{C}}_0=\mathbf{Set}$. The initial free construction $L_0:\mathbf{Set}\to {\mathcal{C}}_1$ sends $A$ to $A\times \mathbb{N}$ with ${\alpha }_1(a,k)=(a,k+1)$. A function $f:A\to UB$ extends uniquely by $(a,k)\mapsto {\beta }_1^k(f(a))$. Its induced monad is $T_{0}A=A\times \mathbb{N}$, with unit $a\mapsto (a,0)$ and multiplication $(a,k,l)\mapsto (a,k+l)$. An algebra for a monad is determined by the action of $1\in \mathbb{N}$, so its Eilenberg-Moore category is ${\mathcal{C}}_1$. Thus this first free–forgetful adjunction is a monadic adjunction without needing the given assumption for $n=0$.

The monadic length counts successive Eilenberg-Moore comparison functor steps until the comparison becomes an equivalence. Fix $0\le m<n$. For $m\ge 1$, the free construction in the preceding part adds the $(m+1)$st operation with no fixed points. For $m=0$, the free first operation also has no fixed points. Consequently the left adjoint $F_{n,m}$ to the composite forgetful functor $U_{n,m}:{\mathcal{C}}_n\to {\mathcal{C}}_m$ is obtained by the one-step free construction, followed by empty higher operations. In particular, its underlying object of ${\mathcal{C}}_m$, unit and multiplication are exactly those of the one-step adjunction:as monads, not merely as object functions. The multiplication agrees because both counits evaluate the same first new operation and the same chains; no later operation has a value on a free object.

By the assumed one-step monadic adjunction property, or the explicit argument above when $m=0$, the Eilenberg-Moore category ${\mathcal{C}}_m^{T_m}$ is equivalent to ${\mathcal{C}}_{m+1}$. Under this equivalence the comparison ${\mathcal{C}}_n\to {\mathcal{C}}_m^{T_m}$ is precisely $U_{n,m+1}$. Indeed, its algebra action evaluates each newly adjoined chain using ${\alpha }_1$, and evaluates the first new value using ${\alpha }_{m+1}$; it retains that operation and ignores all higher ones. The comparison has a left adjoint by the same explicit free extension. Thus the whole monadic tower for nested partial unary operations iswith the remaining comparison at stage $m$ equal to $U_{n,m}$, and stage $n$ the identity.

It does not terminate earlier. If $m<n$, take the same underlying two-element set in two objects of ${\mathcal{C}}_n$, making every operation up to $m$ the identity. In the first object make all remaining operations identities; in the second make ${\alpha }_{m+1}$ exchange the two elements, and leave all subsequent operations undefined. Both satisfy the nesting rule. The identity function is a morphism after forgetting to ${\mathcal{C}}_m$, but is not a morphism between the original objects. Thus $U_{n,m}$ is not a full functor, and cannot be an equivalence. Therefore

Write $\eta :1_{\mathcal{C}}\to GF$ and $\epsilon :FG\to 1_{\mathcal{D}}$ for the unit and counit of an adjunction. The induced monad hasThe Eilenberg-Moore comparison functor sends $D\in \mathcal{D}$ to the algebra for a monadand sends $v:D\to D^{\prime }$ to $Gv$. The triangle identities for an adjunction give the algebra unit law, and naturality of the counit gives the algebra multiplication law and the algebra-morphism equation for $Gv$.

If $\mathcal{D}$ has coequalizers, define the Left adjoint to the Eilenberg-Moore comparison functor at an algebra $(A,a:TA\to A)$ byThe parallel pair is reflexive through $F{\eta }_A$. A morphism $L(A,a)\to D$ is equivalently an arrow $b:FA\to D$ with $bFa=b{\epsilon }_{FA}$. Under $F⊣G$, its transpose is $\bar{b}=Gb{\eta }_A:A\to GD$. The transpose of $bFa$ is $\bar{b}a$, while the transpose of $b{\epsilon }_{FA}$ is $G{\epsilon }_{D}T\bar{b}$. Hence the coequalizer condition is exactlythe equation for a morphism of algebras for a monad $(A,a)\to K(D)$. This supplies the natural bijection proving $L⊣K$, and also defines $L$ on algebra morphisms by the coequalizer universal property.

A monad $\mathbb{T}=(T,\eta ,\mu )$ consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1_{\mathcal{C}}\Rightarrow T$ and $\mu :T^2\Rightarrow T$ satisfyingAn algebra for a monad is $(A,a)$ with $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $a{\mu }_A=aT(a)$. A morphism of algebras for a monad $h:(A,a)\to (B,b)$ obeys $ha=bT(h)$. The functor laws show that identities and composites obey this equation, giving the Eilenberg-Moore category ${\mathcal{C}}^{\mathbb{T}}$.

For an adjunction $F⊣G$, let $\eta$ be its adjunction unit and $\epsilon$ its adjunction counit. The monad induced by an adjunction isThe two unit laws are $G{\epsilon }_{FA}{\eta }_{GFA}=1_{GFA}$ and $G({\epsilon }_{FA}F{\eta }_A)=1_{GFA}$, respectively the two triangle identities for an adjunction.

For associativity, naturality of the adjunction counit at ${\epsilon }_{FA}:FGFA\to FA$ saysApply $G$ to obtain ${\mu }_A{\mu }_{TA}={\mu }_{A}T{\mu }_A$. The composites defining $\eta$ and $\mu$ are natural transformations, so all monad axioms have been checked, not only their underlying objectwise types.

Define the forgetful functor $G^{\mathbb{T}}(A,a)=A$, acting as the identity on underlying morphisms. Define the free algebra functor byThe monad laws make ${\mu }_X$ an algebra for a monad structure, and naturality of $\mu$ makes $T(h)$ an monad algebra morphism.

For $(A,a)$, define the transpose mapsThe map $\Psi (k)$ is an monad algebra morphism, because naturality of $\mu$ and the algebra associativity law giveFor $k:X\to A$, naturality of $\eta$ gives $\Phi \Psi (k)=aT(k){\eta }_X=a{\eta }_{A}k=k$. Conversely, if $h$ is an monad algebra morphism, thenPrecomposing by a map into $X$ or postcomposing by an monad algebra morphism respects both formulas. Thus the bijection is natural and $F^{\mathbb{T}}⊣G^{\mathbb{T}}$. This is the free-forgetful Eilenberg-Moore adjunction.

Its adjunction unit is the given ${\eta }_X$; its adjunction counit at $(A,a)$ is the monad algebra morphism $a:(TA,{\mu }_A)\to (A,a)$. Hence $G^{\mathbb{T}}{F}^{\mathbb{T}}=T$, and the induced multiplication is the underlying counit at $(TX,{\mu }_X)$, namely ${\mu }_X$. Therefore this adjunction induces exactly the original monad, including its unit and multiplication of a monad.

For the monad $(T,\eta ,\mu )$, an algebra for a monad is $(A,a:TA\to A)$ with $a{\eta }_A=1_A$ and $aT(a)=a{\mu }_A$. A morphism of algebras for a monad $f:(A,a)\to (B,b)$ satisfies $fa=bTf$. These objects and arrows form the Eilenberg-Moore category ${\mathcal{C}}^T$.

The free algebra functor sends $A$ to $(TA,{\mu }_A)$ and $f$ to $Tf$. The monad identities verify the algebra laws. For the forgetful functor $U$, the free adjunction iswith inverse $v\mapsto bTv$. The algebra law makes the latter an monad algebra morphism. The identities $h{\eta }_A\mapsto bT(h{\eta }_A)=h{\mu }_{A}T{\eta }_A=h$ and $bTv{\eta }_A=b{\eta }_{B}v=v$ prove the bijection.

In the category of adjunctions inducing a fixed monad, objects are adjunctions $F⊣G$ with their induced monad identified with $T$. A morphism to $F^{\prime }⊣G^{\prime }$ is a functor $H$ between the right-hand categories satisfying $G^{\prime }H=G$, $HF=F^{\prime }$ and compatibility with units and counits. With these strict identifications, defineThe triangle identities give the unit algebra law; naturality of $\epsilon$ at ${\epsilon }_B$ gives the multiplication law. Naturality at $f$ makes $Gf$ an monad algebra morphism. Moreover $UK=G$, $KF=F^T$ because $G{\epsilon }_{FA}={\mu }_A$, and $K{\epsilon }_B$ is the free-adjunction counit at $K(B)$. Hence $K$ is a morphism into the Eilenberg-Moore adjunction.

For any other such $H$, its underlying object at $B$ must be $GB$. Counit compatibility forces its algebra action to be $G{\epsilon }_B$, and the forgetful functor, which is a faithful functor, forces $H(f)=Gf$. Thus $H=K$. This proves terminality of the Eilenberg-Moore adjunction. If adjunctions are specified only up to coherent isomorphisms, the same argument gives uniqueness up to the corresponding compatible natural isomorphism.

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 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)$.

Write $F:\mathcal{X}\to \mathcal{A}$ and $G:\mathcal{A}\to \mathcal{X}$, with adjunction counit $\epsilon$. The induced monad has $T=GF$ and $\mu =G\epsilon F$. Define the Eilenberg-Moore comparison functor byThe action $a_A=G{\epsilon }_A:TGA\to GA$ satisfies $a_A{\eta }_{GA}=1_{GA}$ by a triangular equation. Naturality of $\epsilon$ at ${\epsilon }_A:FGA\to A$ givesApplying $G$ yields $a_{A}T(a_A)=a_A{\mu }_{GA}$, the other algebra identity. For $f:A\to A^{\prime }$, naturality givesso $Gf$ is a monad algebra morphism. Identities and compositions are respected because $G$ is a functor. Finally,and the same equalities hold on morphisms. Thus both comparison identities hold, strictly when $\mathbb{T}$ is the specified induced monad: