What is known about the category of monads on Set? - MathOverflow

What is known about the category of monads on Set?

2011-02-12T04:31:40Z

Monads on the category Set of sets and functions are somehow fundamental objects of category theory, and moreover they have important applications to computer science. We know of a good number of monads on Set, but they all appear (at least to me) as isolated examples (other than three big classes of them I'll discuss below). I'm wondering what is known about the category of monads on Set; call it $Mon$. Below, I'll refer to a monad $(M,\eta,\mu)$ in $Mon$ simply by its functor, $M$.

Clearly, the category $Mon$ is not small because for any set $E$, there is a monad $X\mapsto X\amalg E$ and another monad $X\mapsto X^E$. It would be nice to "classify" monads so as to see these as two, rather than as a large number, of examples. Are there ways to "classify" objects in $Mon$ to notice more broad patterns? Here's another class of them for example: those coming from algebraic theories (e.g. the free group monad, the free ring monad, etc.)

For what types of diagrams does $Mon$ have limits or colimits? Clearly $Mon$ has an initial object (the identity monad) and a final object ($X\mapsto{\star}$).

Suppose given a monad $M\in Mon$, and suppose we know (1) the set $M(\emptyset),$ (2) the set $M({\star})$, and (3) the function $M(\emptyset\to{\star})$. Can we say anything else about $M$? Can we limit the three possible answers to (1),(2),(3) above for monads?

Are any other interesting facts known about $Mon$?

Answer by Tom Leinster for What is known about the category of monads on Set?

2011-02-12T12:18:52Z

I predict that someone such as Steve Lack or Mike Shulman will tell you about the existence of (co)limits in Mon, and they'll do it better than I would, so instead I'll address a question in the last paragraph: do $M(0)$, $M(1)$ and $M(0 \to 1)$ tell you much about the rest of $M$? The answer is basically no.

To see this -- and to understand monads -- it's helpful to observe that if $M$ is regarded as an algebraic theory then $M(n)$ is the set of words in $n$ letters, or equivalently $n$-ary operations in the theory. For example, if $M$ is the monad for groups then $M(n)$ is the set of words-in-the-group-theory-sense in $n$ letters, which are the same as the $n$-ary operations in the theory of groups. For example, $x^3 y^2 x^{-1}$ is a typical word in two letters, and $(x, y) \mapsto x^3 y^2 x^{-1}$ is a typical binary operation (way of turning a pair of elements of a group into a single element). Similarly, if $M$ is the monad for rings then $M(n)$ is the set of polynomials over $\mathbb{Z}$ in $n$ variables, which are the $n$-ary operations in the theory of rings.

(Personally I'm happy to think of any monad on Set as an algebraic theory, although others prefer a more restrictive definition of theory. Anyway, this point of view doesn't matter in what follows.)

In particular, $M(0)$ is the set of nullary operations, or constants, in the theory, and $M(1)$ is the set of unary operations. Now let's consider on the one hand the identity monad $I$, and on the other the monad $M$ corresponding to the theory generated by a single binary operation $\cdot$ subject to the equation $x\cdot x = x$. (Or if you want a more familiar but more complicated example, take $M$ to be the monad for [not necessarily bounded] lattices or semilattices; the point is that $x \vee x = x$.) We then have $I(0) = 0 = M(0)$ and $I(1) = 1 = M(1)$, hence also $$ I(0 \to 1) = (0 \to 1) = M(0 \to 1). $$ But $I$ and $M$ are very different monads.

On the positive side, I think you might be interested in the following result; it seems in the spirit of your question. Suppose there exists an $M$-algebra with more than one element. Then:

$M$ reflects isomorphisms
$M$ is faithful
the unit $\eta$ of $M$ is monic (i.e. the free $M$-algebra on a set of generators contains the generators as a subset -- it doesn't identify any of them).

What's more, all but two monads on Set have this property that there exists an algebra with more than one element. One of the exceptions is the monad $M$ with $M(A) = 1$ for all sets $A$; it's the theory generated by a single constant $e$ and the equation $x = e$. The other is the monad $M$ with $M(A) = 1$ for all nonempty sets $A$ and $M(0) = 0$; that's the theory generated by no operations and the equation $x = y$.

Edit David asked where a proof of this "positive" result could be found. I learned it from a Cambridge Part III problem sheet by Peter Johnstone, and it's probably out there somewhere in the literature (e.g. maybe in Johnstone's Sketches of an Elephant). But since consulting the literature means getting up from the couch, I'll type out a proof instead.

So, let $M = (M, \eta, \mu)$ be a monad on Set such that there exists at least one $M$-algebra with more than one element. Write $F: \mathrm{Set} \to \mathrm{Set}^M$ for the free algebra functor, and $U: \mathrm{Set}^M \to \mathrm{Set}$ for the underlying set functor; thus, $M = UF$.

First we show that $\eta: id \to M$ is monic. This means for each set $A$ and each $a, b \in A$ with $a \neq b$, we have $\eta_A(a) \neq \eta_A(b)$. By the universal property of $\eta_A$, this is equivalent to the assertion that for some $M$-algebra $X$ and map $f: A \to U(X)$ of sets, we have $f(a) \neq f(b)$. (I'd like to draw a commutative triangle to illustrate this.) Choose any $M$-algebra $X$ with more than one element: then such an $f$ can indeed be constructed.

Next we show that $F$ is faithful. It will follow that $M = UF$ is faithful, since $U$ (being monadic) is also faithful. Faithfulness of $F$ is in fact equivalent to each $\eta_A$ being monic, by general properties of adjunctions; I think that's in Categories for the Working Mathematician. Anyway, the proof is that if $f, g: A \to B$ are maps of sets with $Ff = Fg$ then $\overline{Ff} = \overline{Fg}$ (where the bar indicates transpose); but $\overline{Ff} = \eta_B \circ f: A \to UF(B)$ and similarly for $g$, and $\eta_B$ is monic, so $f = g$.

Finally we show that $F$ reflects isos. It will follows that $M = UF$ reflects isos, since $U$ (being monadic) also reflects isos. A faithful functor always reflects both epis and monos, and any map in Set that's both epi and mono is an iso. Hence any faithful functor out of Set reflects isos, and the result follows from the previous part.

Answer by Steve Lack for What is known about the category of monads on Set?

2011-02-13T23:25:10Z

The category of all monads on Set (often this is called $Mnd$, and $Mon$ means the category of monoids) is not just large, but has large hom-sets.

But if you restrict it to the full subcategory $Mnd_f$ of all finitary monads, then you get a beautiful category: it is not just complete and cocomplete but locally finitely presentable. It is even monadic over the category $Set^N$ of families of sets indexed by the natural numbers.

The finitary monads are the ones that correspond to finitary (one-sorted) algebraic theories, and so include the monads for monoids, commutative monoids, groups, rings, Lie algebras (over a given field), and so on. More formally, a monad is finitary when its endofunctor part $T:Set\to Set$ preserves filtered colimits, or equivalently when $T$ is the left Kan extension of its restriction to finite sets.

An example of a monad which is not finitary is the ultrafilter monad, whose algberas are compact Hausdorff spaces.

Instead of finitary monads, you can take monads of rank $\alpha$, for some regular cardinal $\alpha$ - these are the ones whose endofunctors preserve $\alpha$-filtered colimits, and which can be described in terms of $\alpha$-small operations and equations. The full subcategory $Mnd_\alpha$ of $Mnd$ consisting of the monads of rank $\alpha$ is also locally finitely presentable. For example $Mnd_f$ is just the case where $\alpha=\aleph_0$.

The inclusion $Mnd_\alpha\to Mnd$ does preserve colimits (in fact it has a right adjoint), and so $Mnd$ does have colimits of diagrams of monads with bounded rank.

An example of a monad which does not have a rank is the powerset monad, whose algebras are the complete semilattices.