Monad (category theory)

From Wikipedia, the free encyclopedia

For the uses of monads in computer software, see monads in functional programming.

In category theory, a monad or triple is an (endo-)functor, together with two associated natural transformations. They are important in the theory of pairs of adjoint functors, and they generalize closure operators on posets to arbitrary categories.

The notion of "algebras for a monad" generalizes classical notions from universal algebra, and in this sense, monads can be thought of as "theories".

1 Introduction
2 Formal definition
3 Comonads and their importance
4 Examples
5 Algebras for a monad
6 Monads and adjunctions
7 Uses
8 See also
9 References
10 External links

[edit] Introduction

If F and G are a pair of adjoint functors, with F left adjoint to G, then the composition $G \circ F$ is a monad. Therefore, a monad is a functor from a category to itself. If F and G 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 $F \circ G$ , is discussed under the dual theory of comonads.

The monad axioms can be seen at work in a simple example: let G be the forgetful functor from the category Grp of groups to the category Set of sets. Then as F we can take the free group functor.

This means that the monad

$T = G \circ F$

takes a set X and returns the underlying set of the free group Free(X). In this situation, we are given two natural morphisms:

$X \rightarrow T(X)$

by including any set X in Free(X) in the natural way, as strings of length 1. Further,

$T(T(X)) \rightarrow T(X)$

can be made out of a natural concatenation of 'strings of strings'. This amounts to two natural transformations

$I \rightarrow T$

and

$T \circ T \rightarrow T$

They will satisfy some axioms about identity and associativity that result from the adjunction properties.

Those axioms are formally similar to the monoid axioms. They are taken as the definition of a general monad (not assumed a priori to be connected to an adjunction) on a category.

If we specialize to categories arising from partially ordered sets (P, ≤) (with a single morphism from x to y iff x ≤ y), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.

Every monad arises from some adjunction, in fact typically from many adjunctions. Two constructions introduced below, the Kleisli category and the category of Eilenberg-Moore algebras, are extremal solutions of the problem of constructing an adjunction that gives rise to a given monad.

The example about free groups given above 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 universal algebras. Even more generally, any adjunction is said to be monadic (or tripleable) if it shares this property of being (equivalent to) the Eilenberg-Moore category of its associated monad. Consequently Beck's monadicity theorem, which gives a criterion for monadicity, can be used to show that an arbitrary adjunction can be treated as a category of algebras in this way.

The language of monads belongs to the school of Mac Lane, and members of the school of Grothendieck often only work with adjoint functors, not mentioning monads directly.

[edit] Formal definition

If C is a category, a monad on C consists of a functor T : C → C together with two natural transformations: η : 1_C → T (where 1_C denotes the identity functor on C) and μ : T² → T (where T² is the functor T o T from C to C). These are required to fulfill the following conditions (sometimes called coherence conditions):

μ o Tμ = μ o μT (as natural transformations T³ → T);
μ o Tη = μ o ηT = 1_T (as natural transformations T → T; here 1_T denotes the identity transformation from T to T).

With commutative diagrams:

See the article on natural transformations for the explanation of the notations Tμ and μT, or see below the commutative diagrams not using these notions:

The first axiom is akin to the associativity in monoids, the second axiom to the existence of an identity element. Indeed, a monad on C can alternatively be defined as a monoid in the category End_C whose objects are the endofunctors of C and whose morphisms are the natural transformations between them, with the monoidal structure induced by the composition of endofunctors.

[edit] Comonads and their importance

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 C is a monad for the opposite category C^op. It is therefore a functor U from C to itself, with a set of axioms for counit and comultiplication that come from reversing the arrows everywhere in the definition just given.

Since a comonoid is not a basic structure in abstract algebra, this is less familiar at an immediate level.

The importance of the definition comes in a class of theorems from the categorical (and algebraic geometry) theory of descent. What was realised in the period 1960 to 1970 is that recognising the categories of coalgebras for a comonad was an important tool of category theory (particularly topos theory). The results involved are based on Beck's theorem. Roughly what goes on is this: while it is simple set theory that a surjective mapping of sets is as good as the imposition of the equivalence relation 'in the same fiber', for geometric morphisms what you should do is pass to such a coalgebra subcategory.

[edit] Examples

The most important examples to think about when hearing the term "monad" are the free group example mentioned above, and closure operators. Another example, on the category Set: for a set A let T(A) be the power set of A and for a function f : A → B let T(f) be the function between the power sets induced by taking direct images under f. For every set A, we have a map η_A : A → T(A), which assigns to every element a of A the singleton {a}. A function

μ_A : T(T(A)) → T(A)

can be given as follows: if L is a set whose elements are subsets of A, then taking the union of these subsets gives a subset η_A(L) of A. These data describe a monad.

[edit] Algebras for a monad

Suppose that $(T,η,μ)$ is a given monad on a category C.

A T-algebra $(x, h)$ is an object x of C together with an arrow $h:Tx\to x$ of C called the structure map of the algebra such that the diagrams

and

commute.

A morphism $f:(x,h)\to(x',h')$ of T-algebras is an arrow $f:x\to x'$ of C such that the diagram

commutes.

The category $C T$ of T-algebras and their morphisms is called the Eilenberg-Moore category or category of (Eilenberg-Moore) algebras of the monad T.

Given the monad T, there exists another "canonical" category $C T$ called the Kleisli category of the monad T. Its objects are the objects of C and its arrows from x to y are the arrows $f:x\to Ty$ in C. The identity on an object x is the unit $η x$ , and the composite $g\circ f:x\to Tz$ of two arrows $f:x\to Ty$ and $g:y\to Tz$ is given by $g\circ f=\mu_z\circ Tg\circ f$ . This category is equivalent to the category of free algebras for the monad T, i. e. the full subcategory of $C T$ whose objects are of the form $(T x,μ x)$ , for x an object of C.

[edit] Monads and adjunctions

An adjunction $(F,G,\eta,\varepsilon)$ between two categories C and D (where $F:C\to D$ is left adjoint to $G:D\to C$ and $η$ and $\varepsilon$ are respectively the unit and the counit) always defines a monad $(GF, \eta, G\varepsilon F)$ .

Conversely, it is interesting to consider the adjunctions which define a given monad $(T,η,μ)$ this way. Let $\mathbf{Adj}(C,T)$ be the category whose objects are the adjunctions $(F,G,e,\varepsilon)$ such that $(GF, e, G\varepsilon F)=(T,\eta,\mu)$ and whose arrows are the morphisms of adjunctions which are the identity on C. Then this category has

an initial object $(F_T, G_T, \eta, \mu_T):C\to C_T$ , where $C T$ is the Kleisli category,
a terminal object $(F^T, G^T, \eta, \mu^T):C\to C^T$ , where $C T$ is the Eilenberg-Moore category.

An adjunction $(F,G,\eta,\varepsilon)$ between two categories C and D is a monadic adjunction when the category D is equivalent to the Eilenberg-Moore category $C T$ for the monad $T = G F$ . By extension, a functor $G:D\to C$ is said to be monadic if it has a left adjoint F forming a monadic adjunction. Beck's monadicity theorem gives a characterization of monadic functors.

[edit] Uses

Monads are used in functional programming to express types of sequential computation (sometimes with side-effects). See monads in functional programming.

In categorical logic, an analogy has been drawn between the monad-comonad theory, and modal logic^{[citation needed]}.

[edit] See also

Distributive law between monads
Strong monad
Monad for other meanings of the term.

[edit] References

Daniele Turi: Category Theory Lecture Notes (1996-2001), based on MacLane's book "Categories for the Working Mathematician"
Michael Barr and Charles Wells: Category Theory Lecture Notes (1999), based on their book "Category Theory for Computing Science"

[edit] External links

Monads Four short lectures (with one appendix).
John Baez's This Week's Finds in Mathematical Physics (Week 89) covers monads in 2-categories.

Categories: Adjoint functors

Hidden categories: All articles with unsourced statements | Articles with unsourced statements since May 2008

Monad (category theory)

From Wikipedia, the free encyclopedia

Contents

[edit] Introduction

[edit] Formal definition

[edit] Comonads and their importance

[edit] Examples

[edit] Algebras for a monad

[edit] Monads and adjunctions

[edit] Uses

[edit] See also

[edit] References

[edit] External links

Views

Navigation

Interaction

Search

Languages