# Kleisli category examples

Does anyone want to give four really interesting examples of Kleisli categories and their associated monads? I would also accept Eilenberg Moore categories.

-
Exactly four? ${}$ –  Qiaochu Yuan Jul 24 '12 at 2:09
For a ring $R$, the free (right) $R$-module monad $T : \textbf{Set} \to \textbf{Set}$ has Kleisli category equivalent to the category of free (right) $R$-modules. The same is true for any algebraic theory. In particular, if $R$ is a field, the Kleisli category and the Eilenberg–Moore category are equivalent! –  Zhen Lin Jul 24 '12 at 2:16
I like how Qiaochu's comment got exactly 4 bumps. I would bump it too, but then it would b 5. –  Ben Sprott Jul 25 '12 at 0:17

One may argue that Eilenberg–Moore categories are the more interesting of the two categories of algebras associated with a monad. Using Beck's monadicity theorem, one may prove the following:

Theorem. If $\mathbb{T}$ is an algebraic theory, i.e. a theory with a set of finitary operations and a set of (universally quantified) equational axioms, then the category of models of $\mathbb{T}$ is monadic over $\textbf{Set}$: this means there exists an adjunction $$F \dashv U : \mathbb{T}\textbf{-Mod} \to \textbf{Set}$$ such that $\mathbb{T}\textbf{-Mod}$ is equivalent (or, in this case, isomorphic) to the Eilenberg–Moore category for the monad $T = U F$ on $\textbf{Set}$.

This is proven in e.g. [CWM, Ch. VI, §8], and is widely applicable. For example, we could take $\mathbb{T}$ to be the theory of groups, or the theory of rings, or the theory of right $R$-modules for a given ring $R$... In this context, one also has a concrete interpretation of the Kleisli category for $T$: it is (canonically) isomorphic to the full subcategory of $\mathbb{T}\textbf{-Mod}$ spanned by the strict image of $T$. Indeed, recall that a morphism $X \to Y$ in the Kleisli category is a morphism $X \to T Y$ in base category, but there is a natural bijection between morphisms $X \to T Y$ and (homo)morphisms $F X \to F Y$.

I mentioned that the Kleisli category and Eilenberg–Moore category can coincide. This should be interpreted carefully. There is always a canonical functor from the Kleisli category to the Eilenberg–Moore category, but this is rarely an isomorphism of categories; rather, what is meant is that this functor is part of an equivalence of categories. For example, if $k$ is a field and $T$ is the "free $k$-vector space" monad, then the Kleisli and Eilenberg–Moore categories for $T$ are canonically equivalent in the above sense, but not canonically isomorphic.

There are also monads that do not come from theorems like the above. Here is an "algebraic" example: Let $P : \textbf{Set} \to \textbf{Set}$ be the covariant powerset functor, let $\eta : \textrm{id} \Rightarrow P$ be given by the singleton map $x \mapsto \{ x \}$, and let $\mu : P^2 \Rightarrow P$ be given by the union operation $S \mapsto \bigcup S$. I claim $P$ is a monad. A $P$-algebra is, unsurprisingly, a cocomplete semilattice (i.e. a partial order with all suprema), and a homomorphism of $P$-algebras is a cocontinuous (i.e. supremum-preserving) homomorphism of semilattices. Thus, the Eilenberg–Moore category for $P$ is isomorphic to the category of cocomplete semilattices and cocontinuous homomorphisms, and the Kleisli category for $P$ is equivalent to the full subcategory of free cocomplete semilattices – namely, the category of powersets and union-preserving monotone maps.

Now, it seems morally clear that the theory of cocomplete semilattices is algebraic theory in some sense, even though the obvious axiomatisation requires a proper class of operations of arbitrarily large arity. One could make this rigorous by appealing to a universe axiom, but some people have instead decided to define algebraic theory to mean more or less the same thing as a monad. However, this opens the door to some very unexpected examples of "algebraic" theories. Indeed, here is one that comes right out of general topology.

Let $\beta : \textbf{Set} \to \textbf{Set}$ be the ultrafilter monad, where the unit $\eta : \textrm{id} \Rightarrow \beta$ is the principal ultrafilter map, and $\mu : \beta^2 \Rightarrow \beta$ is the map that sends a ultrafilter $F$ on ultrafilters on $X$ to the set of subsets $S$ of $X$ such that the set of all ultrafilters containing $S$ is contained in $F$. It turns out that a $\beta$-algebra is the same thing as a compact Hausdorff space: roughly speaking, the structural map $\lambda : \beta X \to X$ takes an ultrafilter on $X$ to the unique point it converges to. Indeed, given a compact Hausdorff space $X$ and an ultrafilter $F$ on $X$, there exists a point whose neighbourhood filter is a subset of $F$ (by compactness) and it is unique (by the Hausdorff axiom). Conversely, if every ultrafilter on a topological space $X$ converges to a unique point, then $X$ must be a compact Hausdorff space. The Kleisli category for $\beta$ is in turn equivalent to the full subcategory of Stone–Čech compactifications of discrete sets.

Unsurprisingly, there is a connection between monoids and monads. Let $\mathcal{C}$ be a monoidal category. For clarity, we will suppress the coherence isomorphisms of $\mathcal{C}$. Suppose $M$ is an internal monoid in $\mathcal{C}$ with unit $e : I \to M$ and multiplication $m : M \otimes M \to M$. Then, there is an induced monad $- \otimes M : \mathcal{C} \to \mathcal{C}$, where the unit is given by $\textrm{id} \otimes e : X \to X \otimes M$ and the multiplication is given by $\textrm{id} \otimes m : X \otimes M \otimes M \to X \otimes M$. An algebra for this monad is called a right $M$-module. In the case $\mathcal{C} = \textbf{Ab}$, a monoid $M$ is the same thing as a ring, and a right $M$-module in this sense is the same thing as a right $M$-module in the traditional sense!

In particular, if we fix a set $S$, there is a symmetric monoidal category $\textbf{Span}(S, S)$ whose objects are triples $(X, s, t)$ where $X$ is a set and $s, t : X \to S$ are maps; the tensor product $X \otimes X'$ is given by the fibre product $\{ (x, x') \in X \times X' : s(x) = t'(x) \}$; a monoid in $\textbf{Span}(S, S)$ is the same thing as a small category $\mathbb{C}$ with underlying object set $S$, and a right $\mathbb{C}$-module is the same thing as a $S$-indexed family of presheaves on $\mathbb{C}$. (Note, however, that homomorphisms of monoids in this category are not quite the same thing as functors; rather, they are functors that act as the identity on objects.)

Of course, not every monad on $\mathcal{C}$ is of the above form. For example, if $\mathcal{C}$ has countable coproducts and $\otimes$ distributes over the coproduct $\coprod$, then one can define a free monoid monad on $\mathcal{C}$ given by $$X \mapsto \coprod_{n \in \mathbb{N}} X^{\otimes n}$$ whose algebras are internal monoids in $\mathcal{C}$. Notice that monads of the form $- \otimes M$ admit a canonical tensorial strength that is an isomorphism, whereas the free monoid monad in general does not.

Now consider the category $\textbf{End}(\mathcal{C})$ of endofunctors $\mathcal{C} \to \mathcal{C}$. This is a monoidal category under composition of endofunctors, and a monoid in $\textbf{End}(\mathcal{C})$ is exactly the same thing as a monad on $\mathcal{C}$! Moreover, if $\mathcal{C}$ has countable coproducts, then so does $\textbf{End}(\mathcal{C})$, and one may construct the free monad/monoid on any functor that preserves countable coproducts. On the face of it, it looks like we've constructed a monad whose algebras are also monads, but I don't think this is very useful in practice.

Finally, here is one piece of advice for learning category theory: when you encounter a definition, always ask what it means in the special case of a poset or a preorder. Often, things simplify.

So let us look at monads on posets. If $X$ is a poset, then a monad on $X$ is the same thing as an idempotent inflationary monotone map $T : X \to X$ – in other words, a (Moore) closure operator. Indeed, a functor $X \to X$ is the same thing as a monotone map $X \to X$, and the monad axioms imply $x \le T(x)$ and $T(T(x)) \le T(x)$, so we must have $T(T(x)) = T(x)$. One may check that Eilenberg–Moore category and Kleisli category for $T$ are canonically isomorphic to the subposet of fixpoints of $T$.

-
Very nice answer and a good selection of examples, but I think you miscounted: there should have been exactly four examples... Maybe you could insist a little more on the point that the Kleisli category looks like the "free guys" while the Eilenberg-Moore category looks like "all guys". –  t.b. Jul 25 '12 at 15:47
Regarding the special case of posets in last paragraph, I would expect both the Eilenberg-Moore category and the Kleisli category to coincide with the set of fixpoints of $T$: A $T$-algebra is an object $x$ together with a map $T(x) \leq x$. Together with the unit $x\leq T(x)$ this forces $T(x) = x$. –  Marc Olschok Jul 25 '12 at 16:36
You're right, of course. A think-o! –  Zhen Lin Jul 25 '12 at 16:38
Thanks for the nice answer. Are there any hints to find the adjoint pairs for these monads used in programming : state, environment or continuation (en.wikipedia.org/wiki/…) ? –  Romuald Mar 6 '13 at 8:21
You can always form the Kleisli or the Eilenberg–Moore category to get an adjunction. In short, every monad comes from an adjunction. –  Zhen Lin Mar 6 '13 at 9:20