Category of Monads on Set – What Is Known?

ct.category-theorymonads

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 $Mnd$. Below, I'll refer to a monad $(M,\eta,\mu)$ in $Mnd$ simply by its functor, $M$.

Clearly, the category $Mnd$ 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 $Mnd$ 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 $Mnd$ have limits or colimits? Clearly $Mnd$ has an initial object (the identity monad) and a final object ($X\mapsto\{\star\}$).

Suppose given a monad $M\in Mnd$, 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 $Mnd$?

Best Answer

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.

Related Question