Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
Exactly four? ${}$ –  Qiaochu Yuan Jul 24 '12 at 2:09
1  
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
5  
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

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.