A large class of monads is actually derived from operads: basic examples form monads in the category of sets and associate to a set X a set TX of abstract “terms” made of elements of X. For example, the monad of vector spaces I mentioned in the previous post is such a monad, and associates to a set the abstract linear combinations of its elements.

Operads are a generic structure giving a more precise definition of these terms. An operad is an abstract set of operations of various arities (an ugly word to precise the number or arguments taken by an operation: a ternary operation is said to have arity three), subject to relations between them or their compositions. For example, the operad of vector spaces consists of two basic operations: sum and product by scalars (which are actually infinitely many operations), which are tied by distributivity, commutativity and associativity among other relations. An example of operation in this operad is $(x,y,z) to 2x+3y+z$, which is a ternary operation.

An operad T defines a natural associated monad, which associates to a set X the set TX of terms built on X, which is defined inductively by the following rules: atoms are the elements of X, and for any n-ary operation $o in T$ , and terms $t_1, dots, t_n$, $o(t_1, t_2, dots, t_n)$ is a term (several terms should be identified if the operad says they correspond to equivalent operations). Since ordinary definitions of operads already assume that it contains all compositions of operations, we usually only need $t_i$ to be elements of X, which kills the need for recursion. However, this readily shows why T behaves like a monad: there is a natural map $X to TX$, and the map $TTX to TX$ comes from the fact that a term over TX is an operation taking terms of X as abstract inputs. It becomes a term over X by replacing these abstract inputs by real inputs and calculating the resulting composition.

An algebra over a monad T is a set equipped with a morphism $TX to X$, with the additional requirement that the associated morphism $TTX to TX$ be exactly the composition of the monad T. In the case of an operad, this amounts to set a value in X for each term, that is, defining internal operations on X mimicking the properties of the abstract operations of the operad. For example, an algebra over the monad of vector space is exactly what we usually call a vector space. We already know examples of algebras over an arbitrary monad T: since it comes with natural morphisms $TTX to TX$, TX itself is always a T-algebra. We say that it is the free T-algebra over X. A free vector space over a set is the vector space having this set as a basis, a free commutative ring is a polynomial ring over indeterminates given by the base set, a free algebra over the monad/operad of groups is a free group, etc.

Let X be a set and $TY to Y$ be a T-algebra structure on a set Y. Any map $f:X to Y$ defines naturally a map $Tf:TX to Y$ which is $TX to TY to Y$. This corresponds to the fact that giving images for generators $X$ produces maps from the free object $TX$ to $Y$. Head-aching abstract nonsense proves actually that this correspondance is a bijection $mathrm{Map}(X, mathrm{Set}(Y)) = mathrm{Hom}_T(TX, Y)$.

Indeed, a map $f:TX to Y$ conversely restricts to $Rf: X to Y$ defined on the generators. Given a map $f: X to Y$, $f: X to Y = (X to Y to TY) to Y = (X to TX to TY) to Y = RTf$. Given a map $f: TX to Y$, we know that $Rf: X to TX to Y$ becomes $T(Rf): TX to TTX to TY$ where $TTX to TY = Tf$. Thus $TRf: TX to TTX to TY to Y = RTf = f$.

We say that the forgetful functor sending a T-algebra Y to the ordinary set Y is (right) adjoint to the free T-algebra functor $X to TX$.

Entry filed under: algebra, categories, english, monads in mathematics. Tags: , , , , , .

• 1. Edward Kmett  |  4 March 2009 at 5:07 pm

Great article. =)

One terribly minor typo: ‘An example of operation of this monad’ shouldn’t that be ‘An example of operation of this operad’ as it comes before you bridge together operads and monads?

• 2. remyoudompheng  |  4 March 2009 at 5:55 pm

Oh, yes, of course…