Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
@David: $Mon$ is the category of monoids in the strict monoidal category of endofunctors on $Set$ under composition. It's my understanding that such categories are, as it were, as nice as you could possibly want, provided the underlying monoidal category has good properties. It's a well-known defect, however, that ordinary morphisms of monads are somehow not good enough to support a very rich theory. Fioré-Kock have some papers that you might find interesting, where they give a good characterization of a double category of monads, where the new vertical morphisms repair the defect. –  Harry Gindi Feb 12 '11 at 4:43
    
You should check out this page on the nLab: ncatlab.org/nlab/show/category+of+monoids . However, to talk about $Mon$ at all, you have to use universes or doubly-large categories (might as well use universes at that point). I hope the nLab reference gives you some information you didn't know (for instance that $Mon$ has all pushouts). –  Harry Gindi Feb 12 '11 at 4:56
    
@Harry Gindi: "It's my understanding that such categories [of monoids] are, as it were, as nice as you could possibly want". Because as everyone knows, the category of affine schemes is particularly well-behaved :). Anyway, I'd say "yes and no" to this statement. In many common situations (e.g. presentable category with cocontinuous tensor product), it's the category of comonoids that's particularly nice. The category of monoids is generally not nice (it includes algebraic geometry, for example), but rather "rich". –  Theo Johnson-Freyd Feb 12 '11 at 5:57
    
The category of affine schemes is categorically well-behaved.. on its own. The trouble with it comes from embedding it into the category of Zariski/étale/fppf sheaves living over it, then restricting to geometric objects (schemes or algebraic spaces). In particular, it's complete-cocomplete. But anyway, what does that have to do with monoidal categories? –  Harry Gindi Feb 12 '11 at 9:19
    
I know that V. Trnková studied and try do a classification of $Set$ endofunctors, in the book "Automata and ALgebra in Categories" (J Adamek, V. Trnkova) there is a deep study of these arguments in connection by (abstract formal) automata theory. at pag.317-19 of this book there are some observations about $Set$ monads too... MAy be you can write to J. Adamek. –  Buschi Sergio Feb 12 '11 at 12:43
show 1 more comment

2 Answers 2

up vote 10 down vote accepted

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.

share|improve this answer
    
Thanks Tom. Where can I find this nice result? –  David Spivak Feb 12 '11 at 14:04
    
You're welcome. See the edit above. –  Tom Leinster Feb 12 '11 at 15:57
    
Tom, do you know if any work has been done on actually founding mathematics on the category of monads on Set? (Rather than Set itself). I will ask Steve the same question. –  goblin Jun 13 at 9:55
    
No, I'm afraid I don't. –  Tom Leinster Jul 8 at 12:40
add comment

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.

share|improve this answer
    
Surely the ultrafilter monad also does not have a rank? –  Mike Shulman Feb 14 '11 at 5:06
    
No, it doesn't. But I can see that from what I've written you could be excused for thinking it did. –  Steve Lack Feb 14 '11 at 5:53
    
Thanks Steve. Considering finitary monads is a great suggestion. –  David Spivak Feb 15 '11 at 15:03
    
Steve, do the ultrafilter and powerset monad live in any nice category of monads? –  Harry Gindi Feb 15 '11 at 18:00
    
Harry: not that I know of. They have various interesting properties, but I don't know of a nice category containing them. –  Steve Lack Feb 15 '11 at 21:07
show 2 more comments

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.