...

From my recollections, the terminology monad was suggested by P. May as a replacement for triple. The terminology was intended to match with "operad". At the time, S. Mac Lane has taken up that suggestion. In his book "Categories for the working mathematician" Mac Lane uses the terminology monad and comonad rather than triple and cotriple.

If Peter May participates in this board I am sure he will react. Johannes

A question just came up at the Midland Graduate School (actually in the functional programming lecture): Where does the word monad come from?

I know that a monad is a monoid in the category of endofunctors, but what is the logic monoid => monad?

Btw, I frequently encounter monads in a categories of functors which are not endofunctors. An example are finite dimensional vectorspaces which can be constructed via a monoid in the category of functors FinSet -> Set, here I is the embedding and (x) can be constructed from the left kan extension and composition. The unit is given by the Kronecker delta and join can be constructed from Matrix multiplication. Should one call these beasts monads as well? Is there a good reference for this type of construction?

Cheers, Thorsten

Cher Thorsten, toutes mes excuses pour ce message en français. Le terme "monade" a été employé par Benabou (LNM Springer no 47, si je ne me trompe) et dans un sens abstrait : pseudofoncteur 1 --> B de la bicatégorie finale 1 vers une bicatégorie arbitraire B. Par la suite il a été convenu de le résever au cas particulier où B=Cat (en remplacement du terme "triple"). A mon avis, le terme est remarquable car il combine ceux de "monoides" et de "monades", concept utilisé par Leibnitz, mais qui, indépendement de l'usage fait par ce philosophe, signifie : unité simple, indécomposable. Cette simplicité, cette indécomposabilité est celle de la bicatégorie 1. Aujourd'hui, on appelle monoide, les monades au sens général de Benabou. (Personnellement, je ne trouve cela imparfait car un vrai monoide est une structure beaucoup plus riche : exemple x |--> x^2 n'a pas de sens en general.) amitiés, Albert Thorsten Altenkirch <txa@Cs.Nott.AC.UK> a écrit :

A question just came up at the Midland Graduate School (actually in the functional programming lecture): Where does the word monad come from?

I know that a monad is a monoid in the category of endofunctors, but what is the logic monoid => monad?

Btw, I frequently encounter monads in a categories of functors which are not endofunctors. An example are finite dimensional vectorspaces which can be constructed via a monoid in the category of functors FinSet -> Set, here I is the embedding and (x) can be constructed from the left kan extension and composition. The unit is given by the Kronecker delta and join can be constructed from Matrix multiplication. Should one call these beasts monads as well? Is there a good reference for this type of construction?

Cheers, Thorsten

Dear All, As usual, there have been plenty of people with comments about history. There was also a second part to the question:

Btw, I frequently encounter monads in a categories of functors which are not endofunctors. An example are finite dimensional vectorspaces which can be constructed via a monoid in the category of functors FinSet -> Set, here I is the embedding and (x) can be constructed from the left kan extension and composition. The unit is given by the Kronecker delta and join can be constructed from Matrix multiplication. Should one call these beasts monads as well? Is there a good reference for this type of construction?

The category of functors from FinSet to Set is equivalent to the category of endofunctors of Set which preserve filtered colimits: such endofunctors are usually called finitary. Thus a monoid in [FinSet,Set] with respect to this tensor product is the same thing as a monad on Set whose endofunctor part is finitary: this is called a finitary monad. These finitary monads on Set are equivalent to Lawvere theories and so in turn to (finitary, single-sorted) varieties. Finitary monads can also be considered on other base categories than Set, especially on locally finitely presentable ones. It is true that vector spaces are the algebras for a finitary monad on Set. There is no need to restrict to finite-dimensional vector spaces; in fact it is not true that there is a monad on Set whose algebras are the finite-dimensional vector spaces. Steve.

* The Cup or Monad, a text in the Corpus Hermetica from the Wiki

Je trouverais normal que le modérateur ne permette pas cette intervention. C'est en partie à titre de plaisanterie et en complément à une information de Jim que je la fait. Pour des sources mystiques sur la monade : http://www.esotericarchives.com/dee/monade.htm on y trouve des théorèmes inédits en théorie des catégories. Albert

Patrik Eklund wrote: In my view there is no logic monoid => monad... It's pretty much been said, but I'll say it again: We can generalize the concept of monoid from Set to any monoidal category and then to any bicategory. A monoid in Cat is then a monad. Indeed, most people seem to call a "monoid" in a bicategory a "monad". Best, jb

Patrik Eklund wrote:

"Operads" are like sets of operations.

A monad is an extension of a functor. If the functor is the term functor, then the operations of the signature lies inside the functor, and the "operations" eta and mu are identities, or at least something very isomorphic to identities.

In the filter functor eta is point filters and mu is Kowalsky's diagonalization.

In my view there is no logic monoid => monad, and I cannot see the full idea behind using "operads", so help me Mona.

In one paragraph, a monad can be understood as a set T of operations graded by their arity X, that is, a variable set T(X) where the set X is the parameter of variation. This set is made a monoid by the operation of substitution interpreted as the multiplication of the monoid. Substitution is associative (terms of height three can be built top-down or bottom-up) and has a two-sided identity interpretable ambiguously as the identity operation of T (when applied to the top of a term) and substitution of variables for themselves (when applied to the bottom of a term). The back-to-back talks of Walter Taylor on his general theory of varieties and Fred Linton on monads at the Universal Algebra and Category Theory (UACT) meeting held at MSRI in 1993 were like ships passing in the night. No one thought to mention, either before, during, or after the talks, that they were describing essentially the same thing (or if they did both George McNulty and I missed it), with the result that many of the algebraists at the meeting just assumed that these were unrelated talks. Monads can be explained in terms of their associated Kleisli category, or their Eilenberg-Moore category, or as the composition UF of any set-valued functor U with its left adjoint. After Fred's talk I had lunch with George and tried out the third of these on him. However we got bogged down in the definition of adjunction. In hindsight I think the quickest way to explain a monad to an algebraist is to do so directly in terms of T, \mu, and \eta, without the distraction of the additional machinery of the three above methods. It would go something like the following, which of the above three is closest to the Kleisli category approach. I'll ignore the inconsistent monads, those axiomatized by x=y, for which T(X) = 1 for nonempty X and T(0) <= 1. A monad specifies the language and equations of an equational theory. The functor T specifies the language by providing for each set X the set of operations (more properly polynomials or abstract terms) of arity X, e.g. T(2) is the set of binary operations of the theory. The multiplication \mu_X: T(T(X)) --> T(X) specifies the theory by mapping terms of height at most two to operations (identified with terms of height at most one). Terms s and t of height two identified by \mu, e.g. x(y+z) = xy+xz in the case of ring theory, constitute the axioms s = t of the theory determined by \mu. Hardware types and visual thinkers can picture T(X) as a black box containing all operations of arity X. X can be thought of as a row (or any other layout, I like the unit interval [0,1] of reals for picturing an uncountable set as a row) of input sockets on one side and T(X) as a row of output plugs on the opposite side, one per operation. The unit \eta_X: X --> T(X) at X, necessarily an injection, ensures that the operations include the variables, qua (formal) projections. Thinking of T(X) as consisting of terms, define the height of each variable to be zero and that of the remaining operations of T(X) as one. Since T can take any set of variables it can take in particular T(X), whence there is also a box with input set T(X) and output set T(T(X)). The boxes containing T(X) and T(T(X)) can be plugged together to form a single black box with set X of inputs and set T(T(X)) of outputs. However this latter set must now be interpreted as consisting of entities of arity X instead of arity T(X). Viewed syntactically (taking into account the separate contents of the two boxes and how they attach) we can consider the outputs of T(T(X)) as terms of height two in the variables in X, or rather at most two since the unit of the monad embeds X in T(X) and T(X) in T(T(X)). One can then ask whether any of these terms realize some operation not among those of T(X). The function \mu_X: T(T(X)) --> T(X) accomplishes three things. (i) It interprets every term of height up to two as an operation of T(X), a form of abstract evaluation that hides the two-level term structure. (ii) In so doing it answers the above question in the negative: no new operations, all terms of height up to two realize operations already present in T(X). In this sense T as a graded set of operations is closed under substitution. (iii) As noted above it axiomatizes the equational theory associated with the monad with all equations of that theory involving terms of height at most two, namely all equations s = t such that \mu_X maps s and t to the same operation of T(X). \mu can be extended to evaluate terms of height h inductively. If \mu_h: T^h --> T evaluates terms of height up to h then the vertical composite \mu T(\mu_h): T^{h+1} --> T^2 --> T evaluates terms of height up to h+1, starting from \mu_2 = \mu. (So \mu_h = \mu T(\mu) T^2(\mu)...T^{h-2}(\mu).) This is the categorical counterpart of using equational logic to inductively build up the height of equations in the theory one level at a time via \mu, starting from the equations constituting the kernel of \mu. (Although height is always finite there is no such restriction on arity and hence on width of a term, which can be any set. Even for a finitary monad an operation can take uncountably many arguments, e.g. for the monad for Vct_R as the variety of vector spaces over the reals, each operation in T(T(2)) takes as many parameters as there are linear combinations ax+by, namely uncountably many, though it depends on only finitely many of them because Vct_R is a finitary variety in the sense Steve Lack referred to on Friday.) If the boxes really do consist of operations then the two pluggings required to form a chain T(X), T(T(X)), T(T(T(X))) of three black boxes should have the same operational effect regardless of the order in which they're performed. The associativity axiom for a monad enforces this property of black boxes containing operations. The above inductive definition of \mu_h was bottom-up (T^{h+1} = TT^h) but there is an equivalent top-down one (T^h T) producing the same \mu_h. The Eilenberg-Moore category of a monad is the variety of algebras it axiomatizes, modulo details of the treatment of the associated signature. In general the signature will be a proper class but in many cases encountered in practice one can pick out of this class a (small) set sufficient for a basis of operations, e.g. +, -, and the scalar multiplications for Vct_k, or NAND and a constant for Boolean algebra. The variety of sigma-algebras is not finitary although it can still be furnished with a small signature, but this is not possible for the varieties of complete semilattices and of complete atomic Boolean algebras, which old-school algebraists would not consider varieties for that reason. The Kleisli category is the full subcategory of the variety consisting of its free algebras. The latter is intimately linked to the above intuitions, and amounts to an equivalent way of seeing that T is closed under substitution by formulating substitution as the composition of the Kleisli category. The essential point of departure from the usual notion of a monoid as a fixed set is that for the type T^2 --> T of multiplication, T^2 is defined via composition instead of cartesian product. Monads are therefore simply monoids adapted in this way to accommodate their variability. Monads need not be sets. Just as a ring can be defined as a monoid object in Ab, with the domain of multiplication being formed via cartesian product in Ab, so can a monad be a monoid object in the category of endofunctors of Ab, with the domain of multiplication being formed by functor composition in Ab^Ab. Although not all categories have finite products, T^2 is defined for every category C and endofunctor T: C --> C. Vaughan Pratt

On Fri, Apr 3, 2009 at 12:28 AM, Steve Lack <s.lack@uws.edu.au> wrote:

Finitary monads can also be considered on other base categories than Set, especially on locally finitely presentable ones.

It is true that vector spaces are the algebras for a finitary monad on Set. There is no need to restrict to finite-dimensional vector spaces; in fact it is not true that there is a monad on Set whose algebras are the finite-dimensional vector spaces.

there is something similar in algebraic logic. The class of locally finite cylindric/polyadic algebras is not a variety and the forgetful functor to Set is not monadic (l.f. means that all relations are of finite arities). In categorical logic (hyperdoctrines), these algebras are considered in many-sorted signatures, in fact, as algebras over graphs, and their theory becomes equational (= the corresponding forgetful functor to Graph is monadic). Probably, it's a general phenomenon wrt specifying finitary objects: by indexing them with finite sets (contexts, supports,arities), we get equational theories over graph-like structures. In a wider (and partly speculative) setting, the shift from classical algebraic to categorical logic is a shift from simple signatures and complex theories to complex signatures and simple theories. In a sense, this is what category theory does wherever it applies to classical problems: it greatly simplifies the logic (and the internal structure), but pays for this by a complex vocabulary (the external structure, interface). A typical example is classical vs. categorical set theories. Thus, a categorical model is a device with a structurally complex interface and simple internal logic. An average user prefers, of course, simple-looking interfaces of classical theories (and eventually has to pay for this choice but it happens later on...). So, for marketing categorical models, it's important to provide good manuals for their complicated interfaces -- what Vaughan just did for monads. Zinovy

Dear Thorsten, I'm not familiar with the notation that you are using, although I can guess what is meant in some cases

I am not sure I completely understand your comments. I guess it may be helpful to be more precise:

F : FinSet -> Set F A = Real -> A

I assume you mean A->Real. It's true that the monad for vector spaces sends a finite set A to R^A, which can be seen as the set of functions from A to R. For a general set A (not necessarily finite) FA is the set of functions from A to R of finite support. Equivalently, FA is the set of formal finite linear combinations of elements of A.

I suspect my eta and >>= give then rise to a monad on Set? However, I don't see how to do this if the vector spaces are not finite.

Yes, this gives a monad on Set whose algebras are vector spaces, not necessarily finite dimensional. I'm not sure what it is you claim to be doing when you "do this". In any case there is a monad on Set whose algebras are vector spaces; there is not a monad on Set whose algebras are finite dimensional vector spaces. You can see this last statement by noting that the category of algebras for a monad on Set is always cocomplete.

Btw, I only used this as an example. My question was rather wether people have studied monoids in categories of functors which are not endofunctors. I believe this notion is useful in functional programming and Type Theory as a natural generalisation of the notion of a monad.

Yes, monoids in categories of functors are useful concepts. Of course to define a monoid you need a monoidal structure on the ambient category. There may be many possibilities, and for some of them the corresponding notion of monoid looks more like a monad than for others. For some monoidal structures one should really think of the monoids as not generalizations of monads, but special cases of monads. Your example of finitary monads is a good example. So are operads. There are more examples in the paper "notions of Lawvere theory" available from my home page or as arXiv:0810.2578. Regards, Steve Lack.