Monads Comonads and Their Algebras — Examples

The data include an input with empty output, and all displayed values are finite words of the required types.

Substitution and concatenation give $(g\star f)(0)=[p,q,p,p]$, $(g\star f)(1)=[]$, and $(g\star f)(2)=[q,p]$.

Define $h(p)=[r]$ and $h(q)=[s,r]$. Then $(h\star (g\star f))(0)=[r,s,r,r,r]$, while $(h\star g)(a)=[r]$ and $(h\star g)(b)=[s,r,r]$, so $((h\star g)\star f)(0)$ is the same word.

Define $T(f)$ to act by $f$ on $Y$ and fix $\mathrm{\perp }$, let ${\eta }_Y$ be the inclusion of $Y$, and let ${\mu }_Y:T(TY)\to TY$ fix elements of $Y$ and send both the inner and outer undefined values to $\mathrm{\perp }$. Direct inspection of the defined and undefined cases proves the unit and associativity laws in [L1].

A function $u:X\to Y\bigsqcup \{\mathrm{\perp }\}$ determines the partial function with domain $D_u=\{x:u(x)\in Y\}$ and value $u(x)$ there. Conversely, a partial function on $D\subseteq X$ extends uniquely by assigning $\mathrm{\perp }$ outside $D$.

These constructions are inverse. Expanding Kleisli composition shows that $v\star u$ is defined exactly where $u$ is defined and $v$ is defined at $u(x)$, with value $v(u(x))$; this is the usual maximal-domain composition of partial functions.

The displayed beginning contains the empty word, the words $[a],[b]$, and the words $[a,a],[a,b],[b,a],[b,b]$; $T(X)$ continues with all finite words in $a$ and $b$.

One has ${\eta }_X(a)=[a]$, ${\eta }_X(b)=[b]$, ${\mu }_X([[a,b],[],[b],])=[a,b,b]$, ${\mu }_X([])=[]$, and ${\mu }_X([[]])=[]$.

The unit samples flatten $[[a],]$ to $[a]$ and the list of singleton words to the original word; nested concatenation gives the same word under either bracketing. Thus the displayed calculations agree with the general monad equations.

Define $T(f)=f\times 1_M$, ${\eta }_X(x)=(x,e)$, and ${\mu }_X((x,m),n)=(x,mn)$. These formulas have the required types.

Naturality follows because the formulas do not change the $M$-coordinate except by multiplication. The two monad unit composites send $(x,m)$ to $(x,em)$ and $(x,me)$, both equal to $(x,m)$ by [L1].

On an element $(((x,m),n),p)$, the two associativity composites produce $(x,(mn)p)$ and $(x,m(np))$, equal by associativity in $M$.

$T$ is an endofunctor of $\mathbf{S}\mathbf{e}\mathbf{t}$: $T(1_X)=1_G\times 1_X=1_{G\times X}$, and $T(f^{\mathrm{\prime }}\circ f)=1_G\times (f^{\mathrm{\prime }}\circ f)=(1_G\times f^{\mathrm{\prime }})\circ (1_G\times f)=T(f^{\mathrm{\prime }})\circ T(f)$, since both sides send $(g,x)$ to $(g,f^{\mathrm{\prime }}(f(x)))$.

$\eta$ is natural: for $f:X\to Y$, both $T(f)\circ {\eta }_X$ and ${\eta }_Y\circ f$ send $x$ to $(u,f(x))$. And $\mu$ is natural: for $f:X\to Y$, both $T(f)\circ {\mu }_X$ and ${\mu }_Y\circ T(T(f))$ send $(g_1,(g_2,x))$ to $(g_1{g}_2,f(x))$.

Associativity holds componentwise: on $(g_1,(g_2,(g_3,x)))$ the composite ${\mu }_X\circ T({\mu }_X)$ gives $(g_1(g_2{g}_3),x)$ and ${\mu }_X\circ {\mu }_{TX}$ gives $((g_1{g}_2)g_3,x)$, and these agree because multiplication in $G$ is associative.

The unit laws hold componentwise: on $(g,x)$ the composite ${\mu }_X\circ T({\eta }_X)$ gives $(gu,x)$ and ${\mu }_X\circ {\eta }_{TX}$ gives $(ug,x)$, and both equal $(g,x)$ because $u$ is a two-sided identity of $G$. Hence $(T,\eta ,\mu )$ is a monad by [L1].

Let $h:G\times X\to X$ be a structure map. By [L2] the unit law $h\circ {\eta }_X=1_X$ says $h(u,x)=x$ for every $x$, and the associativity law $h\circ T(h)=h\circ {\mu }_X$ evaluated at $(g_1,(g_2,x))$ says $h(g_1,h(g_2,x))=h(g_1{g}_2,x)$. Writing $g\cdot x:=h(g,x)$, these are exactly the two clauses of [L3], so $h$ is a left action of $G$ on $X$.

Conversely, a left action of $G$ on $X$ is a function $h:G\times X\to X$ with $h(u,x)=x$ and $h(g_1{g}_2,x)=h(g_1,h(g_2,x))$ by [L3], which are the two $T$-algebra laws of [L2] read backwards. So the $T$-algebras with underlying set $X$ are precisely the left actions of $G$ on $X$.

For algebras $(X,h)$ and $(Y,k)$ and a function $f:X\to Y$, the homomorphism condition $f\circ h=k\circ T(f)$ of [L2] evaluated at $(g,x)$ reads $f(h(g,x))=k(g,f(x))$, that is $f(g\cdot x)=g\cdot f(x)$, which is $G$-equivariance in the sense of [L4].

By [L6] the Eilenberg–Moore category of this monad therefore has the $G$-sets as objects and the $G$-equivariant maps as morphisms. This proves the stated claim.

Applying [L2] to [L1] gives $T(X)=(X\times S{)}^S$.

The unit is ${\eta }_X(x)(s)=(x,s)$. For $k\in T(TX)$, write $k(s)=(c,s^{\mathrm{\prime }})$ with $c:S\to X\times S$ and define ${\mu }_X(k)(s)=c(s^{\mathrm{\prime }})$: the outer computation selects the inner computation and intermediate state, then the inner computation runs at that state.

Evaluating at any initial state, either unit inserts a computation that returns its input without changing state, and either associativity bracketing runs the same outer, selected middle, and selected inner computations in order. If $S=\mathrm{\varnothing }$, every relevant function has empty domain and the same equations hold vacuously.

On $\mathcal{P}(X)$ ordered by inclusion, [L1] says $A\mapsto \bar{A}$ is monotone and satisfies $A\subseteq \bar{A}$.

The identity $\overline{\stackrel{‾}{A}}=\bar{A}$ gives the multiplication comparison and, with step 1.1, makes closure a monad by [L2].

By [L3], its algebra objects are the subsets $A$ with $\bar{A}=A$, exactly the closed subsets. The boundary subsets $\mathrm{\varnothing }$ and $X$ are fixed by [L1].

If $A\subseteq B$, then $\mathrm{int}(A)$ is an open subset of $B$, so maximality in [L1] gives $\mathrm{int}(A)\subseteq \mathrm{int}(B)$. Also [L1] gives $\mathrm{int}(A)\subseteq A$, and, since $\mathrm{int}(A)$ is open, it gives $\mathrm{int}(\mathrm{int}(A))=\mathrm{int}(A)$. These arguments include $A=\mathrm{\varnothing }$ and the empty ambient space.

By [L2], the interior operator therefore defines a comonad.

By [L3], a coalgebra structure on $A$ is the inclusion $A\subseteq \mathrm{int}(A)$. Together with the reverse inclusion from [L1], this is equality, which holds exactly when $A$ is open.

Union with a fixed subset is monotone, extensive, and idempotent. Thus $S$ and $T$ are closure-operator monads by [L1].

For every $A$, $S(T(A))=A\cup \{a,b\}=T(S(A))$. This equality gives $\lambda :ST\Rightarrow TS$; all diagrams in [L2] commute because $P$ is thin and the parallel arrows have the displayed common endpoints.

On $\mathrm{\varnothing },\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}$, both composites respectively give $\{a,b\},\{a,b\},\{a,b\},\{a,b,c\},\{a,b\},\{a,b,c\},\{a,b,c\},\{a,b,c\}$. This checks the formula at every object, including the empty set.

By [L3], the distributive law makes $TS$ a monad; its unit is the inclusion $A\subseteq A\cup \{a,b\}$ and its multiplication is the idempotence equality for the closure operator adjoining both fixed points.

By [L1]–[L4], the free-$\mathbb{Z}$-module on $X$ is ${\mathbb{Z}}^{(X)}$. For a function $u:X\to A$ into an abelian group, the unique extension sends ${\sum }_x{n}_x[x]$ to ${\sum }_x{n}_{x}u(x)$, so this is also exactly the universal property of the free abelian group on $X$.

Its unit is $x\mapsto 1[x]$. Its multiplication flattens ${\sum }_i{n}_i[{\sum }_j{m}_{ij}[x_{ij}]]$ to ${\sum }_{i,j}{n}_i{m}_{ij}[x_{ij}]$.

Every $\mathbb{Z}$-module is an abelian group under addition. Conversely, on an abelian group define $n\cdot x$ by repeated addition for positive $n$, by $0$ for $n=0$, and by negatives for negative $n$; the abelian-group laws give the module laws, and group homomorphisms are exactly the resulting $\mathbb{Z}$-linear maps. Hence the algebras are precisely abelian groups.

If $X$ is nonempty and finite, [L5] makes its singleton partition finite, and its union $X$ belongs to every ultrafilter. Repeated use of [L1] selects a singleton $\{x\}$, and no distinct singleton can also belong because their intersection is empty.

Upward closure now shows that the ultrafilter consists exactly of the subsets containing $x$, namely ${\eta }_X(x)$. Thus ${\eta }_X$ is bijective for nonempty finite $X$. If $X=\mathrm{\varnothing }$, no proper filter exists because the whole carrier is also empty, so $\beta X=\mathrm{\varnothing }$ and ${\eta }_X$ is again bijective.

Naturality in [L2] makes these bijections a natural isomorphism on finite sets. Under the identification, ${\eta }_X$ is the identity and ${\mu }_X$ sends the principal ultrafilter at ${\eta }_X(x)$ to ${\eta }_X(x)$, so the restricted monad is naturally isomorphic to the identity monad.

Assuming [L3], let $\mathcal{U}$ be the nonprincipal ultrafilter on $\mathbb{N}$ supplied there. Every value of ${\eta }_{\mathbb{N}}$ is principal, so $\mathcal{U}$ is outside its image and that unit component is not invertible.

The multiplication table is $1\cdot 1=1$, $1\cdot e=e\cdot 1=e$, and $e\cdot e=e$. The element $1$ is an identity, and every triple product containing $e$ evaluates to $e$, so multiplication is associative.

Hence $M$ is a monoid and therefore an Eilenberg–Moore algebra by [L2].

The free monoid on the empty set is a singleton. On a nonempty set, choosing a generator $x$ yields the distinct words $[],[x],[x,x],\dots$, so the free monoid is infinite. Therefore the two-element algebra $M$ is not free.

Reduction modulo $2$ coequalizes $f$ and $g$. If a group homomorphism $h:\mathbb{Z}\to H$ satisfies $hf=hg$, then $h(2n)$ is the identity for every $n$, so $h$ kills $2\mathbb{Z}$ and factors uniquely through $\mathbb{Z}\mathrm{/}2\mathbb{Z}$. Thus this is the group coequalizer by [L1]–[L2].

In $\mathbf{S}\mathbf{e}\mathbf{t}$, the generated equivalence relation identifies every even integer with $0$, because the generating pairs are $(2n,0)$. No odd integer occurs in such a pair, so each odd integer remains a singleton equivalence class. The quotient map coequalizes $f$ and $g$, and every function $u$ with $uf=ug$ is constant on the even class and therefore factors uniquely through this quotient, proving its Set universal property.

The set coequalizer is therefore infinite, while the underlying set of the group coequalizer has the residue classes of $0$ and $1$. The underlying-set functor, including the one in the free-group adjunction of [L3], does not preserve this coequalizer.

A function $X\to \mathcal{P}(Y)$ is the characteristic assignment of a relation $R\subseteq X\times Y$; transposing $R$ gives a function $Y\to \mathcal{P}(X)$. This natural bijection $\mathbf{S}\mathbf{e}\mathbf{t}(X,\mathcal{P}Y)\cong \mathbf{S}\mathbf{e}\mathbf{t}(Y,\mathcal{P}X)$ supplies the self-adjunction by [L1].

Applying [L2], the induced endofunctor is $T(X)=\mathcal{P}\mathcal{P}X$, and its unit is ${\eta }_X(x)=\{A\subseteq X:x\in A\}$.

For $\mathbb{W}\in \mathcal{P}(\mathcal{P}(\mathcal{P}(\mathcal{P}X)))$, the multiplication is ${\mu }_X(\mathbb{W})=\{A\subseteq X:\{\mathcal{A}\subseteq \mathcal{P}X:A\in \mathcal{A}\}\in \mathbb{W}\}$. This has type $T^{2}X\to TX$. In particular, the construction does not assert a natural map $\mathcal{P}\mathcal{P}X\to X$.