Examples of Monads and their Algebras

Question

I'd like to get some examples of monads; specifically, I'd love a big list of different monads and a description of what their algebras are. Alternatively, online resources and especially exercices on monads and their algebras.

---

A recent question I asked (that hasn't received any answers yet), has sent me on an epic voyage of discovery through the world of lattices, monads, operads, lattice and poset homology. I'm a bit lost but very much enjoying the ride ^^

Anyway, I know that a pair of adjoint functors produce a monad, and conversely, it is my understanding that, given a monad, one can construct a new category and a pair of adjoint functors that will produce the original monad, so in a way the question is settled. However this is not very concrete to me.

Here are some monads encountered in various lecture notes (and the youtube video series by the Catsters)

• the monad on $\mathsf{Set}$ that associates to every set the set on words on it; its algebras are the monoids. Similarly there is the monad on $\mathsf{Set}$ that associates to every set the set underlying the free group on it; I guess the algebras associated to this one are the groups(?), or the monad on $\mathsf{Vect}_k$ that takes a vector space $V$ to the vector space underlying its tensor algebra: what are its algebras? These arise from classical adjuctions.
• the powerset monad. I've tried working out its algebras but I don't have a clue as to what they might be. An algebra would be a set $X$ and a map $\theta:\mathcal{P}(X)\rightarrow X$ such that for any $x\in X$ and family $(A_i:i\in I)$ of distinct subsets of $X$, $$\theta(\lbrace x\rbrace)=x\text{ and }\theta\left(\bigcup_{i\in I} A_i\right)=\theta\left(\lbrace \theta(A_i)\mid i\in I\rbrace\right)$$ However, I don't see what that actually means. EDIT I found a chapter of Mac Lane's Categories for the Working Mathematician online that features an exercise showing that the algebras for the powerset monad are the complete join semi-lattices.
• the intriguing ultrafilter monad on $\mathsf{Set}$ that sends a set $X$ to the set $\mathcal{U}X$ of all ultrafilters on $X$. According to Steve Lack's answer to this MO question, its "algberas are compact Hausdorff spaces". I read a short explanation somewhere on the net, but I haven't yet tried to grasp it, nor do I remember where it was...

Answer 1

It's often helpful to understand a general category-theoretic idea by looking at how it specializes to posets. In this case, a monad on a poset is precisely a closure operator, hence examples are given by any topological space $X$ (where the poset is the poset of subsets of $X$ and the closure operator is taking closures). The algebras are precisely the closed elements of the poset. Note how the relationship to adjoint functors specializes to the relationship between Galois connections and closure operators.

Note also how non-poset examples can be thought of in terms of closure. For example, the List monad, whose algebras are monoids, can be thought of as the result of "closing a set under concatenation."

Answer 2

My favorite monad at the moment is the Giry monad. I am actually not sure if the definition I have in mind is the same as the definition in the literature, but here is one version: there is a monad on $\text{Set}$ which takes a set $X$ to the set of all probability distributions on $X$. Its algebras are an infinitary version of convex spaces, but more importantly, its Kleisli category is the category of sets and random functions (functions $f : X \to Y$ which return, not an element of $Y$, but a probability distribution over elements of $Y$). This is an abstract way of thinking about stochastic matrices.

Answer 3

There is a certain monad which might well be considered the "mother of all monads", in much the same way as the endomorphism ring of an abelian group is the "mother of all rings". Indeed, some people even call it the endomorphism monad (especially in operadic circles), but it is perhaps more commonly known as the codensity monad. It has the following universal property:

• Let $\mathcal{C}$ be a locally small and complete category, let $\mathbb{T}$ be a monad on $\mathcal{C}$, and let $X : \mathcal{J} \to \mathcal{C}$ be a small diagram. Then the category of monad morphisms and monad transformations $\mathbb{T} \to \mathbb{E}\mathsf{nd}(X)$ is isomorphic to the category of factorisations of $X$ through the forgetful functor $U^\mathbb{T} : \mathcal{C}^\mathbb{T} \to \mathcal{C}$.

Now how might $\mathbb{E}\mathsf{nd}(X)$ be defined? The neatest way is by Kan extension: the underlying endofunctor of $\mathbb{E}\mathsf{nd}(X)$ is the right Kan extension of $X$ along $X$. Thus we have the following formula: $$\textrm{End}(X)(Y) = \int_{j : \mathcal{J}} (X j)^{\mathcal{C}(Y, X j)}$$ In particular, when $\mathcal{J}$ is the terminal category $\mathbb{1}$, $X$ just picks out an object of $\mathcal{C}$, and when $\mathcal{C} = \textbf{Set}$, the formula boils down to $$\textrm{End}(X)(Y) = X^{X^Y}$$ and so the double-dualisation monad is a special case of the endomorphism monad. This formula also shows what the algebraic theory corresponding to $\mathbb{E}\mathsf{nd}(X)$ is: it is the theory whose operations are functions $X^Y \to X$, and whose axioms are all the equations that these satisfy.

Answer 4

The Powerset Monad

Let $T$ be the powerset endofunctor on the category $\mathsf{Set}.$ For any set $X,~TX=\mathscr P(X)$ is its powerset, and for any map of sets $f:X\to Y,~Tf:\mathscr P(X)\to\mathscr P(Y)$ sends $A\subset X$ to $Tf(A)=f(A)$. There are natural transformations $\eta:1_{\mathsf{Set}}\Rightarrow T$ and $\mu:T^2\Rightarrow T$ defined by $$\eta_X(x)=\lbrace x\rbrace\text{ and }\mu_X\Big(\lbrace A_i:i\in I\rbrace\Big)=\bigcup_{i\in I} A_i$$ where $X$ is any set, $x\in X$ any point in $X$, and $\lbrace A_i\mid i\in I\rbrace$ is any set of distinct subsets of $X$. This defines indeed a monad.

Its Algebras

A $T$-algebra is a set $X$ and a morphism of sets $\theta:TX\rightarrow X$ i.e. a map that takes a subset of $X$ and sends it to an element in $X$. It being an $T$-algebra means that it has to be compatible with $\mu$ and $\eta$ as follows: for any $x\in X$ and for any collection of subsets $\mathscr{A}=\lbrace A_i: i\in I\rbrace$ of $X$,

$$\theta(\eta_X(x))=\theta(\lbrace x\rbrace)=x \text{ and } \theta\big(\mu_X(\mathscr A)\big)=\theta\big(T\theta(\mathscr A)\big)$$ where the last equality means $\theta\Big(\bigcup_{i\in I}A_i\Big)=\theta\Big(\lbrace\theta(A_i):i\in I\rbrace\Big)$

---

Define a binary relation $\preceq$ on $X$ by $$a\preceq b\Longleftrightarrow \theta\big(\lbrace a,b\rbrace\big)=b$$ Then $(X,\preceq)$ is a complete join-semilattice, and for any subset $A\subset X,~\bigvee A=\theta(A)$.

---

For any $x\in X,~x\preceq x$ since $\theta(\lbrace x,x\rbrace)=\theta(\lbrace x\rbrace)=x$, so $\preceq$ is reflexive. Also, if $x\preceq y$ and $y\preceq x$, then by definition $x=\theta(\lbrace x,y\rbrace)=y$, so $\preceq$ is antisymmetric. Finally, if $x\preceq y$ and $y\preceq z$. Then we have $$\begin{array}{ccccc} \theta(\lbrace x,y,z\rbrace)&=&\theta(\mu_X(\lbrace \lbrace x,y\rbrace,\lbrace y,z\rbrace\rbrace))\\ &&\Vert&&\\ &&\theta(T\theta(\lbrace\lbrace x,y\rbrace,\lbrace y,z\rbrace\rbrace))&=\theta(\lbrace y,z\rbrace)&=&z\end{array}$$ thus $$\begin{array}{ccccc}\theta(\lbrace x,z\rbrace)&=&\theta(T\theta(\lbrace\lbrace x\rbrace,\lbrace y,z\rbrace\rbrace))\\ &&\Vert&&\\ &&\theta(\mu_X(\lbrace\lbrace x\rbrace,\lbrace y,z\rbrace\rbrace))&=&\theta(\lbrace x,y,z\rbrace)=z\end{array}$$ i.e. $x\preceq z$ and so $\preceq$ is transitive. This shows that $(X,\preceq)$ is a poset.

---

For any subset $A\subset X,~\theta(A)\in X$ is its join. Indeed, there is nothing to show if $A=\emptyset$, and otherwise, for any $a\in A,$ $$\begin{array}{ccccc} \theta(\lbrace a,\theta(A)\rbrace)&=&\theta( T\theta(\lbrace \lbrace a\rbrace,A\rbrace))&&\\ &&\Vert&&\\ &&\theta(\mu_X(\lbrace \lbrace a\rbrace,A\rbrace))&=&\theta(\lbrace a\rbrace\cup A)=\theta(A) \end{array}$$ so for any $a\in A,~a\preceq \theta(A)$. Now if $b\in X$ has $a\preceq b$ for all$a\in A$, then $$\begin{array}{c} \theta(\lbrace \theta(A),b\rbrace)&=&\theta(T\theta(\lbrace A,\lbrace b\rbrace\rbrace))&&\\ &&\Vert&&\\ &&\theta(\mu_X(\lbrace A,\lbrace b\rbrace\rbrace))&&\\ &&\Vert&&\\ &&\theta(A\cup\lbrace b\rbrace)&=&\theta(\bigcup_{a\in A}\lbrace a,b\rbrace)\\ &&&&\Vert\\ &&&&\theta(\mu_X(\lbrace \lbrace a,b\rbrace:a\in A\rbrace))\\ &&&&\Vert\\ &&&&\theta(T\theta(\lbrace \lbrace a,b\rbrace:a\in A\rbrace))\\ &&&&\Vert\\ &&&&\theta(\lbrace \underbrace{\theta(\lbrace a,b\rbrace)}_{=b}:a\in A\rbrace)&=& \theta(\lbrace b\rbrace)=b \end{array}$$ i.e. for any set $A$ and any upper bound $b,~\theta(A)\preceq b$ so $\theta(A)$ is $A$'s lower upperbound, thus $(X,\preceq)$ is a complete join -semilattice.

---

Conversely, any join-semilattice $(X,\leq)$ gives rise to a map $\bigvee$ from the powerset of $X$ to $X,$ $A\mapsto \bigvee A$, and it is easily seen that this is a $T$-algebra.