Monads in mathematics 2 : algebras over monads and operads

26 February 2009 at 12:50 am 2 comments

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: , , , , , .

Monads in mathematics 1 : examples LaTeXing monads

2 Comments Add your own

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed



%d bloggers like this: