Monad (category theory)

In category theory, a branch of mathematics, a monad (also triple, triad, standard construction and fundamental construction) is an endofunctor (a functor mapping a category to itself), together with two natural transformations required to fulfill certain coherence conditions. Monads are used in the theory of pairs of adjoint functors, and they generalize closure operators on partially ordered sets to arbitrary categories.
Introduction and definition.
A monad is a certain type of endofunctor. For example, if formula_1 and formula_2 are a pair of adjoint functors, with formula_1 left adjoint to formula_2, then the composition formula_5 is a monad. If formula_1 and formula_2 are inverse functors, the corresponding monad is the identity functor. In general, adjunctions are not equivalences—they relate categories of different natures. The monad theory matters as part of the effort to capture what it is that adjunctions 'preserve'. The other half of the theory, of what can be learned likewise from consideration of formula_8, is discussed under the dual theory of "comonads".
Formal definition.
Throughout this article formula_9 denotes a category. A "monad" on formula_9 consists of an endofunctor formula_11 together with two natural transformations: formula_12 (where formula_13 denotes the identity functor on formula_9) and formula_15 (where formula_16 is the functor formula_17 from formula_9 to formula_9). These are required to fulfill the following conditions (sometimes called coherence conditions):
We can rewrite these conditions using the following commutative diagrams:
See the article on natural transformations for the explanation of the notations formula_27 and formula_28, or see below the commutative diagrams not using these notions:
The first axiom is akin to the associativity in monoids if we think of formula_29 as the monoid's binary operation, and the second axiom is akin to the existence of an identity element (which we think of as given by formula_30). Indeed, a monad on formula_9 can alternatively be defined as a monoid in the category formula_32 whose objects are the endofunctors of formula_9 and whose morphisms are the natural transformations between them, with the monoidal structure induced by the composition of endofunctors.
The power set monad.
The "power set monad" is a monad formula_34 on the category formula_35: For a set formula_36 let formula_37 be the power set of formula_36 and for a function formula_39 let formula_40 be the function between the power sets induced by taking direct images under formula_41. For every set formula_36, we have a map formula_43, which assigns to every formula_44 the singleton formula_45. The function
takes a set of sets to its union. These data describe a monad.
Remarks.
The axioms of a monad are formally similar to the monoid axioms. In fact, monads are special cases of monoids, namely they are precisely the monoids among endofunctors formula_47, which is equipped with the multiplication given by composition of endofunctors.
Composition of monads is in general, not a monad. For example, double power set monad formula_48 does not admit any monad structure.
Comonads.
The categorical dual definition is a formal definition of a "comonad" (or "cotriple"); this can be said quickly in the terms that a comonad for a category formula_9 is a monad for the opposite category formula_50. It is therefore a functor formula_51 from formula_9 to itself, with a set of axioms for "counit" and "comultiplication" that come from reversing the arrows everywhere in the definition just given.
Monads are to monoids as comonads are to "comonoids". Every set is a comonoid in a unique way, so comonoids are less familiar in abstract algebra than monoids; however, comonoids in the category of vector spaces with its usual tensor product are important and widely studied under the name of coalgebras.
Terminological history.
The notion of monad was invented by Roger Godement in 1958 under the name "standard construction." In the 1960s and 1970s, many people used the name "triple." The now standard term "monad" is due to Saunders Mac Lane.
Examples.
Monads arising from adjunctions.
Any adjunction
gives rise to a monad on "C". This very widespread construction works as follows: the endofunctor is the composite
This endofunctor is quickly seen to be a monad, where the unit map stems from the unit map formula_55 of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:
In fact, any monad can be found as an explicit adjunction of functors using the Eilenberg–Moore category formula_57 (the category of formula_25-algebras).
Double dualization.
The "double dualization monad", for a fixed field "k" arises from the adjunction
where both functors are given by sending a vector space "V" to its dual vector space formula_60. The associated monad sends a vector space "V" to its double dual formula_61. This monad is discussed, in much greater generality, by .
Closure operators on partially ordered sets.
For categories arising from partially ordered sets formula_62 (with a single morphism from formula_63 to formula_64 iff formula_65), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.
Free-forgetful adjunctions.
For example, let formula_2 be the forgetful functor from the category Grp of groups to the category Set of sets, and let formula_1 be the free group functor from the category of sets to the category of groups. Then formula_1 is left adjoint of formula_2. In this case, the associated monad formula_70 takes a set formula_71 and returns the underlying set of the free group formula_72.
The unit map of this monad is given by the maps
including any set formula_71 into the set formula_72 in the natural way, as strings of length 1. Further, the multiplication of this monad is the map
made out of a natural concatenation or 'flattening' of 'strings of strings'. This amounts to two natural transformations.
The preceding example about free groups can be generalized to any type of algebra in the sense of a variety of algebras in universal algebra. Thus, every such type of algebra gives rise to a monad on the category of sets. Importantly, the algebra type can be recovered from the monad (as the category of Eilenberg–Moore algebras), so monads can also be seen as generalizing varieties of universal algebras.
Another monad arising from an adjunction is when formula_25 is the endofunctor on the category of vector spaces which maps a vector space formula_78 to its tensor algebra formula_79, and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of formula_78 into its tensor algebra, and a natural transformation corresponding to the map from formula_81 to formula_79 obtained by simply expanding all tensor products.
Codensity monads.
Under mild conditions, functors not admitting a left adjoint also give rise to a monad, the so-called codensity monad. For example, the inclusion
does not admit a left adjoint. Its codensity monad is the monad on sets sending any set "X" to the set of ultrafilters on "X". This and similar examples are discussed in .
Algebras for a monad.
Given a monad formula_84 on a category formula_9, it is natural to consider "formula_25-algebras", i.e., objects of "C" acted upon by "T" in a way which is compatible with the unit and multiplication of the monad. More formally, a "T"-algebra formula_87 is an object formula_63 of formula_9 together with an arrow formula_90 of formula_9 called the "structure map" of the algebra such that the diagrams
commute.
A morphism formula_92 of formula_25-algebras is an arrow formula_94 of formula_9 such that the diagram commutes. "T"-algebras form a category called the "Eilenberg–Moore category" and denoted by formula_57.
Examples.
Algebras over the free group monad.
For example, for the free group monad discussed above, a "T"-algebra is a set "X" together with a map from the free group generated by "X" towards "X" subject to associativity and unitality conditions. Such a structure is equivalent to saying that "X" is a group itself.
Algebras over the distribution monad.
Another example is the distribution monad formula_97 on the category of sets. It is defined by sending a set formula_71 to the set of functions formula_99 with finite support and such that their sum is equal to formula_100. In set-builder notation, this is the setformula_101By inspection of the definitions, it can be shown that algebras over the distribution monad are equivalent to convex sets, i.e., sets equipped with operations formula_102 for formula_103 subject to axioms resembling the behavior of convex linear combinations formula_104 in Euclidean space.
Algebras over the symmetric monad.
Another useful example of a monad is the symmetric algebra functor on the category of formula_105-modules for a commutative ring formula_105.formula_107sending an formula_105-module formula_109 to the direct sum of symmetric tensor powersformula_110where formula_111. For example, formula_112 where the formula_105-algebra on the right is considered as a module. Then, an algebra over this monad are commutative formula_105-algebras. There are also algebras over the monads for the alternating tensors formula_115 and total tensor functors formula_116 giving anti-symmetric formula_105-algebras, and free formula_105-algebras, soformula_119where the first ring is the free anti-symmetric algebra over formula_105 in formula_121-generators and the second ring is the free algebra over formula_105 in formula_121-generators.
Commutative algebras in E-infinity ring spectra.
There is an analogous construction for commutative formula_124-algebraspg 113 which gives commutative formula_36-algebras for a commutative formula_124-algebra formula_36. If formula_128 is the category of formula_36-modules, then the functor formula_130 is the monad given byformula_131whereformula_132formula_133-times. Then there is an associated category formula_134 of commutative formula_36-algebras from the category of algebras over this monad.
Monads and adjunctions.
As was mentioned above, any adjunction gives rise to a monad. Conversely, every monad arises from some adjunction, namely the free–forgetful adjunction
whose left adjoint sends an object "X" to the free "T"-algebra "T"("X"). However, there are usually several distinct adjunctions giving rise to a monad: let formula_137 be the category whose objects are the adjunctions formula_138 such that formula_139 and whose arrows are the morphisms of adjunctions that are the identity on formula_9. Then the above free–forgetful adjunction involving the Eilenberg–Moore category formula_57 is a terminal object in formula_137. An initial object is the Kleisli category, which is by definition the full subcategory of formula_57 consisting only of free "T"-algebras, i.e., "T"-algebras of the form formula_144 for some object "x" of "C".
Monadic adjunctions.
Given any adjunction formula_145 with associated monad "T", the functor "G" can be factored as
i.e., "G"("Y") can be naturally endowed with a "T"-algebra structure for any "Y" in "D". The adjunction is called a monadic adjunction if the first functor formula_147 yields an equivalence of categories between "D" and the Eilenberg–Moore category formula_57. By extension, a functor formula_149 is said to be monadic if it has a left adjoint formula_1 forming a monadic adjunction. For example, the free–forgetful adjunction between groups and sets is monadic, since algebras over the associated monad are groups, as was mentioned above. In general, knowing that an adjunction is monadic allows one to reconstruct objects in "D" out of objects in "C" and the "T"-action.
Beck's monadicity theorem.
"Beck's monadicity theorem" gives a necessary and sufficient condition for an adjunction to be monadic. A simplified version of this theorem states that "G" is monadic if it is conservative (or "G" reflects isomorphisms, i.e., a morphism in "D" is an isomorphism if and only if its image under "G" is an isomorphism in "C") and "C" has and "G" preserves coequalizers.
For example, the forgetful functor from the category of compact Hausdorff spaces to sets is monadic. However the forgetful functor from all topological spaces to sets is not conservative since there are continuous bijective maps (between non-compact or non-Hausdorff spaces) that fail to be homeomorphisms. Thus, this forgetful functor is not monadic.
The dual version of Beck's theorem, characterizing comonadic adjunctions, is relevant in different fields such as topos theory and topics in algebraic geometry related to descent. A first example of a comonadic adjunction is the adjunction
for a ring homomorphism formula_152 between commutative rings. This adjunction is comonadic, by Beck's theorem, if and only if "B" is faithfully flat as an "A"-module. It thus allows to descend "B"-modules, equipped with a descent datum (i.e., an action of the comonad given by the adjunction) to "A"-modules. The resulting theory of faithfully flat descent is widely applied in algebraic geometry.
Uses.
Monads are used in functional programming to express types of sequential computation (sometimes with side-effects). See monads in functional programming, and the more mathematically oriented Wikibook module .
In categorical logic, an analogy has been drawn between the monad-comonad theory, and modal logic via closure operators, interior algebras, and their relation to models of S4 and intuitionistic logics.
Generalization.
It is possible to define monads in a 2-category formula_9. Monads described above are monads for formula_154.