nLab
monad

Contents

This entry is about the notion of monad in category theory. For other notions see monad (disambiguation).


Context

Higher algebra

2-Category theory

Contents

The entry is about monads in the sense of category theory, for another concept see also monad in nonstandard analysis.

Idea

A monad is a structure that is a lot like a monoid, but that lives in a bicategory rather than a monoidal category. In other words, the concept of a monad is a horizontal categorification of that of a monoid.

Monads are among the most pervasive structures in category theory and its applications: for example, they are central to the category-theoretic account of universal algebra, as well as underlying the theory of simplicial objects and thus, via the Dold-Kan correspondence, much of homological algebra.

Definition

Monads

A monad in a bicategory KK is given by

  • an object aa, together with

  • an endomorphism t:aat \colon a \to a, and

  • 2-cellsη:1 at\eta \colon 1_a \to t (the unit of tt) and μ:ttt\mu \colon t \circ t \to t (the multiplication)

such that the diagrams

t ηt tt tη t μ t ttt μt tt tμ μ tt μ t \array{ t & \stackrel{\eta t}{\to} & t t & \stackrel{t \eta}{\leftarrow} & t \\ & \searrow & \downarrow \mathrlap{\mu} & \swarrow & \\ & & t & & } \qquad \qquad \array{ t t t & \stackrel{\mu t}{\to} & t t \\ \mathllap{t \mu} \downarrow & & \downarrow \mathrlap{\mu} \\ t t & \stackrel{\mu}{\to} & t }

commute (where certain coherence isomorphisms have been omitted).

The name “monad” and the terms “unit”, “multiplication” and “associativity” bear a clear analogy with monoids (but see also at monad (disambiguation)). Indeed, one can define a monad on an object aa of a bicategory KK as just a monoid in the endomorphism category K(a,a)K(a,a). Alternatively, monads can be taken as more fundamental, and a monoid in a monoidal category CC can be defined as a monad in BC\mathbf{B} C, the one-object bicategory corresponding to CC.

A third and somewhat less obvious definition says that a monad in KK is a lax 2-functor from the terminal bicategory 11 to KK: the unique object *\ast of 11 is sent to the object aa, the morphism 1 a1_a becomes tt, and η\eta and μ\mu arise from the coherent 2-cells expressing lax functoriality. This in turn is equivalent to saying that a monad is a category enriched in a bicategory with a single object and single morphism. Among higher-category theorists, it’s tempting to suggest that this is the most fundamental definition, and the most basic reason for the ubiquity and importance of monads. Regardless of this, however, the earlier more elementary definitions are both practically and pedagogically essential.

Finally, a monad can be defined in terms of the “Kleisli operation” taking any map aTba \to T b to a map TaTbT a \to T b; see extension system.

We can picture a monad in KK as an image of the third oriental in KK. See the remarks at monoidal category.

The data of and axioms for a monad can be expressed graphically as string diagrams. Writing T:CC,η,μT \colon C \to C, \eta, \mu for the monad in question (this notation being the standard one when K=CatK = Cat), these data can be represented as

String diagrams of the monad data (for "Monad")

Thanks to the distinctive shapes, one can usually omit the labels:

String diagrams of the monad data, unlabeled (for "Monad")

The axioms then appear as:

String diagrams of the monad axioms, unlabeled (for "Monad")

Monads in CatCat are sometimes, mostly in older literature, also called triples (alluding to the triple of data (A,μ,i)(A,\mu,i)), following Eilenberg and Moore. In even older literature, they are also referred to as standard constructions, the original term used by Godement when he introduced the idea. For terminological remarks by Ross Street see category-list here.

The bicategory of monads

Given the equivalence between monads in KK and lax functors 1K1 \to K it is straightforward to define the bicategory Mnd(K)Mnd(K) of monads in KK to be the lax functor category [1,K] [1,K]_\ell, which consists of lax functors, lax transformations and modifications.

Spelling this out, we see that an object of Mnd(K)Mnd(K) is a monad (a,t,η,μ)(a,t,\eta,\mu) in KK. A morphism of monads (a,t)(b,s)(a,t) \to (b,s) is given by 1-cell x:abx \colon a \to b together with a 2-cell λ:sxxt\lambda \colon s x \to x t satisfying

x η sx sx xη t λ xt 1 xtssx sλ sxt λt xtt μ sx xμ t sx λ xt \array{ x & \stackrel{\eta^s x}{\to} & s x \\ \mathllap{x \eta^t} \downarrow & & \downarrow \mathrlap{\lambda} \\ x t & \stackrel{1}{\to} & x t }\qquad \qquad \array{ s s x & \stackrel{s \lambda}{\to} & s x t & \stackrel{\lambda t}{\to} & x t t \\ \mathllap{\mu^s x} \downarrow & & & & \downarrow \mathrlap{x \mu^t} \\ s x & & \stackrel{\lambda}{\to} & & x t }

Finally, a 2-cell (x,λ)(y,κ)(x,\lambda) \Rightarrow (y, \kappa) is given by a 2-cell m:xym \colon x \Rightarrow y satisfying

sx sm sy λ κ xt mt yt \array{ s x & \stackrel{s m}{\to} & s y \\ \mathllap{\lambda} \downarrow & & \downarrow \mathrlap{\kappa} \\ x t & \stackrel{m t}{\to} & y t }

Algebras/modules over a monad

Given that a monad in a bicategory \mathcal{B} is nothing but a monoid in a hom-category (a,a)\mathcal{B}(a,a), it is natural to consider a module over this monoid: a module for a monad. This notion of module is more general than a module in a monoidal category, however, since it need not live in (a,a)\mathcal{B}(a,a) but can be in (b,a)\mathcal{B}(b,a) (for left modules) or (a,c)\mathcal{B}(a,c) (for right modules).

In a Cat-like bicategory, left modules over a monad are usually called algebras over the monad. This terminology is confusing from the point of view of monads as monoids, but is justified because in Cat itself, such algebras with domain 1 are just algebras for a monad in the classical sense. Such algebras are a powerful tool to encode general algebraic structures; this is the topic of universal algebra. The algebras over a monad form its Eilenberg-Moore category, which is characterized by a universal property.

Some monads arise from operads, in which case algebras for the monad are the same as algebras for the operad. A Lawvere theory is another special sort of monad in CatCat.

Properties

Relation to adjunctions and monadicity

Every adjunction (LR)(L \dashv R) induces a monad RLR \circ L and a comonad LRL \circ R. There is in general more than one adjunction which gives rise to a given monad this way, in fact there is a category of adjunctions for a given monad. The initial object in that category is the adjunction over the Kleisli category of the monad and the terminal object is that over the Eilenberg-Moore category of algebras. (e.g. Borceux, vol. 2, prop. 4.2.2) The latter is called the monadic adjunction.

Moreover, passing from adjunctions to monads and back to their monadic adjunctions constitutes itself an adjunction between adjunctions and monads, called the semantics-structure adjunction.

Examples

Monads in SetSet

Many of these monads also have standard usages as monads in computer science.

Example

The free-forgetful adjunction between pointed sets and sets induces an endofunctor () *:SetSet(-)_* : Set \to Set which adds a new disjoint point. This is called the maybe monad in computer science.

Example

The free-forgetful adjunction between monoids and sets induces an endofunctor T:SetSetT : Set \to Set defined by

TA:= n0A nTA := \bigsqcup_{n \ge 0} A^n

giving the free monoid monad. This also goes by the name list monad or Kleene-Star? in computer science. The components of the unit η A:ATA\eta_A : A \to T A give inclusions sending each element of AA to the corresponding singleton list. The components of the multiplication μ A:T 2ATA\mu_A : T^2 A \to T A are the concatenation functions, sending a list of lists to the corresponding list (Known as flattening in computer science). This monad can be defined in any monoidal category with coproducts that distribute over the monoidal product.

Example

For a fixed set of “states” SS, the (S×() SS \times - \dashv (-)^S)-adjunction induces a monad (S×) S(S \times -)^S on SetSet called the state monad. This is a commonly used monad in computer science. In functional programming languages such as Haskell, states can be used to model “side effects” of computations.

Example

The contravariant power set functor is its own right adjoint, giving Set(A,PB)Set(B,PA)\Set(A,P B) \cong \Set (B, P A). Note that hom(A,PB)=hom(A,hom(B,Ω)hom(A×B,Ω)=P(A×B)\hom(A, P B) = \hom(A, \hom(B,\Omega) \cong \hom( A \times B, \Omega) = P(A \times B) inducing a double power set monad taking a set AA to P 2AP^2 A. The components of the unit are the principle ultrafilter functions η A:AP 2A\eta_A : A \to P^2 A which send an element aa to the set of subsets of AA that contain aa. The components of the multiplication μ A\mu_A is the inverse image function for the map μ PA:PAP 3A\mu_{P A} : P A \to P^3 A. Which can be painfully stated as: the function taking a set of sets of sets of subsets to the set of subsets of AA with the property that one of the sets of sets of subsets is the set of all sets of subsets of AA that include that particular subset as an element.

Replacing the two element power object Ω\Omega with any other set gives similar monads. In computer science contexts these are known as continuation monads. This construction can also be generalised for any other cartesian closed category. For example there is a similar double dual monad* on Vect k\Vect_k.

Example

function monad

Algebra

Example

The free-forgetful adjunction between sets and the category of RR-modules. This induces the free RR-module monad R[]:SetSetR[-] : Set \to Set. The free abelian group monad and free vector speace monad are special cases.

Example

The free-forgetful adjunction between sets and the category of groups gives the free group monad F:SetSetF : Set \to Set that sends AA to the set F(A)F(A) of finite words in the letters aAa \in A together with inverses a 1a^{-1}.

Topology

Example

There is a forgetful functor U:TopSetU : \Top \to \Set taking a topological space to its underlying set. It is right adjoint to the discrete space functor D:SetTopD: \Set \to \Top taking a set to its discrete topology. There is also an adjoint pair βU\beta \dashv U' between the category of compact Hausdorff topological spaces and the category of topological spaces, where β\beta is the Stone-Cech compactification. The composites of these two adjoint pairs gives a monad β:SetSet\beta : \Set \to \Set sending a set to its underlying set of the Stone-Cech compactification of its discrete space. It is also known as the ultrafilter monad as β\beta can be thought of as the functor taking a set to its set of ultrafilters.

Monads in Cat

Monads are often considered in the 2-category Cat where they are given by endofunctors with a monoid structure on them. In particular, monads in Cat on Set are equivalent to the equational theories studied in universal algebra. In this context, a monad abstracts the concept of an algebraic theory (such as “group” or “ring”), giving a general notion of extra structure on an object of a category.

Classically, if T\mathbf{T} is an algebraic theory (e.g. the theory of groups), a T\mathbf{T}-structure on a set tells us how to interpret various terms (e.g. (ac)(a\cdot c)) formed from elements of the set, subject to certain axioms (e.g. (a(bc))=((ab)c)(a\cdot (b\cdot c))=((a\cdot b)\cdot c)). A monad collects this up into a functor TT. For a set XX, TXT X is the set of all terms of the theory formed from elements of XX, with terms identified if axioms force them to be equal. For groups, TXT X is thus the (underlying set of the) free group of formal words absa \cdot b \cdot \cdots \cdot s from XX; the fact that TT gives free structures turns out to be typical.

To capture the theory fully, we need to include a little more data: a natural map η X:XTX\eta_X : X \to T X recording how each aXa \in X gives a trivial term aa, and a map μ X:TTXTX\mu_X:T T X \to T X recording how further terms built from terms are already present as terms in TXT X.

Given a monad in Cat on a category CC, one can always produce a canonical resolution of any object of CC.

Other examples

Monads in higher category theory

There is a vertical categorification of monads to (∞,1)-categories. See (∞,1)-monad.

in section 3 of

References

Introductions:

Detailed accounts:

Relation to universal algebra:

  • Martin Hyland and John Power, The category theoretic understanding of universal algebra: Lawvere theories and monads (pdf).

  • Anthony Voutas, The basic theory of monads and their connection to universal algebra (pdf)

In higher category theory:

Last revised on March 5, 2019 at 16:37:08. See the history of this page for a list of all contributions to it.