## Posts filed under ‘categories’

### Cardboard associahedron

After the dodecahedron comes the cardboard associahedron : it represents the combinatorics of moving parentheses to calculate an associative product of five things step by step. The vertices of the associahedron are thus the 14 different binary trees with 5 leaves.

Given four factors, there are exactly five ways of multiplying them using a binary operation: by moving parentheses according to the associativity rule, you go through five different trees in a cyclic way. This is known as MacLane’s pentagon coherence rule, which states that in not too weak notions of monoid, checking coherence for pentagon diagrams ensures that the definition of the product is well-behaved.
(more…)

### Monads in mathematics 4 : the bar and cobar constructions

The use of monads and comonads in homological algebra is as old as the theory: Godement’s standard construction refers to the use of monads in cohomology theory, and is said to be the first study of a general method for constructing acyclic resolutions. Later the theory was explored in greater depth by Eilenberg, Moore, Barr, Beck. The term bar resolution is now most commonly used to describe the process. Monads derived from operads were also studied by Lawvere, Mitchell, Bénabou, under the name of algebraic theories, with aim towards topoi and logic.

Bar resolutions (see J. Baez website and the LNM Seminar on Triples and Categorical Homology Theory) are a way to canonically (i.e. functorially) describe an arbitrary algebra over a monad using only free algebras. It is a particular case of definition with generators and relations which is often the only way to describe infinite mathematical objects with finite expressions (computer algebra systems usually deal with finitely generated objects, and use generators and relations to describe their elements), but bar resolutions somehow are the universal way of doing this.

Most cohomology theories fit in the framework of bar constructions, though in various apparently unrelated ways. However, a visible common denominator of most constructions is the use of simplicial methods. This makes them of some use in homotopical algebra: bar resolutions are used to define canonical cofibrant resolutions of objects, which explains their uses in definition of derived functors.
(more…)

The adjunction property between two functors, $T: C_1 \to C_2$ and $U: C_2 \to C_1$, says that there is a natural bijection between morphisms $\mathrm{Hom}_1(A, UB)$ (in the first category) and $\mathrm{Hom}_2(TA, B)$ (in the second category). Here natural means that these bijection is compatible with composition with morphisms $B \to B'$, $UB \to UB'$ or $A' \to A$ and $TA' \to TA$.

Adjunctions are naturally created by the use of monads or operads. For example, the functor $V_k: \mathrm{Set} \to \mathrm{Vect}_k$ mapping a set X to the free vector space $V_k(X) = k^{(X)}$ with basis X, has a adjoint, $U: \mathrm{Vect}_k \to \mathrm{Set}$, mapping a vector space to the set of its elements. The meaning of the adjunction is that a morphism $V_k(X) \to W$ is equivalent to the choice $X \to W$ of images of basis vectors where W is considered as as set. Similar adjunctions exist for other free objects (free algebras, free groups, free modules).
(more…)

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.
(more…)

### Monads in mathematics 1 : examples

Category theory studies in an abstract way how structures and constructions of mathematics are related. A category is a collection of (mathematical) objects. Usually, interesting categories contain objects sharing the same properties (there is a category of sets, a category of groups, a category of rings, and so on). A category need also have a definition of arrows, which often correspond to the usual definition of functions, maps or morphisms. But it is possible to define categories having more complicated arrows. A (not so) stupid non-trivial category is the opposite category Cop of a given category C, which has arrows going the other way.

A monad M on a category C is a functor: it associates to any object X in C another object MX of C in a so-called functorial way, which means that any arrow $X to Y$ should give rise to an arrow $MX to MY$. But in order to call M a monad, we require several other properties: there should be natural transformations $X to MX$ (so that $X to MX to MY$ and $X to Y to MY$ are the same, which can be expressed by a commutative square), and $MMX to MX$ such that $MX to MMX to MX$ is the identity (notice that there are two ways to obtain an arrow $MX to MMX$). MacLane in Categories for the Working Mathematician gives a good account of the theory along with a bit of history and references.

Most examples of monads arising in mathematics are derived from two concepts: operads, which combine monads with much richer structure (but correspond to really tangible examples), and adjunctions (a framework in which monads can actually fit). I should write about these later, and concentrate on examples. Monads are also used in computer science, because they model a construction scheme which is widely spread. The programming language Haskell formulates many concepts in the language of monads. Marco Maggesi wrote a small introduction to monads (in Italian), which covers monads appearing in Haskell. (more…)