Monad (category theory)
In category theory, a branch of mathematics, a monad is an endofunctor, 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 and are a pair of adjoint functors, with left adjoint to, then the composition is a monad. If and 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, is discussed under the dual theory of comonads.Formal definition
Throughout this article denotes a category. A monad on consists of an endofunctor together with two natural transformations: and . These are required to fulfill the following conditions :- ;
- .
See the article on natural transformations for the explanation of the notations and, or see below the commutative diagrams not using these notions:
The first axiom is akin to the associativity in monoids if we think of as the monoid's binary operation, and the second axiom is akin to the existence of an identity element. Indeed, a monad on can alternatively be defined as a monoid in the category whose objects are the endofunctors of 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 on the category : For a set let be the power set of and for a function let be the function between the power sets induced by taking direct images under. For every set, we have a map, which assigns to every the singleton. The functiontakes 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, which is equipped with the multiplication given by composition of endofunctors.Comonads
The categorical dual definition is a formal definition of a comonad ; this can be said quickly in the terms that a comonad for a category is a monad for the opposite category . It is therefore a functor from 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 adjunctiongives 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 of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:
Double dualization
The double dualization monad, for a fixed field k arises from the adjunctionwhere both functors are given by sending a vector space V to its dual vector space. The associated monad sends a vector space V to its double dual. This monad is discussed, in much greater generality, by. Another instance of the same paradigm, discussed by, is the double power set monad, which is the monad on the category of sets, sending a set X to
where 2 denotes a 2-element set, and is the power set of a set X.
Closure operators on partially ordered sets
For categories arising from partially ordered sets , then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.Free-forgetful adjunctions
For example, let be the forgetful functor from the category Grp of groups to the category Set of sets, and let be the free group functor from the category of sets to the category of groups. Then is left adjoint of. In this case, the associated monad takes a set and returns the underlying set of the free group.The unit map of this monad is given by the maps
including any set into the set 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, so monads can also be seen as generalizing varieties of universal algebras.
Another monad arising from an adjunction is when is the endofunctor on the category of vector spaces which maps a vector space to its tensor algebra, and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of into its tensor algebra, and a natural transformation corresponding to the map from to 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 inclusiondoes 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 monad is a submonad of the above-mentioned double power set monad. This and similar examples are discussed in.
Algebras for a monad
Given a monad on a category, it is natural to consider -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 is an object of together with an arrow of called the structure map of the algebra such that the diagramscommute.
A morphism of -algebras is an arrow of such that the diagram commutes. T-algebras form a category called the Eilenberg–Moore category and denoted by. 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.
Another example is the distribution monad on the category of sets. It is defined by sending a set X to the set of functions with finite support and such that. By 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 for subject to axioms resembling the behavior of convex linear combinations in Euclidean space.
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 adjunctionwhose left adjoint sends an object X to the free T-algebra T. However, there are usually several distinct adjunctions giving rise to a monad: let be the category whose objects are the adjunctions such that and whose arrows are the morphisms of adjunctions that are the identity on. Then the above free–forgetful adjunction involving the Eilenberg–Moore category is a terminal object in. An initial object is the Kleisli category, which is by definition the full subcategory of consisting only of free T-algebras, i.e., T-algebras of the form for some object x of C.
Monadic adjunctions
Given any adjunction with associated monad T, the functor G can be factored asi.e., G 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 yields an equivalence of categories between D and the Eilenberg–Moore category. By extension, a functor is said to be monadic if it has a left adjoint 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 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 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 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 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 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. 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.