NationMaster - Encyclopedia: Monad (category theory)

In category theory, a monad or triple is a type of functor, together with two associated natural transformations. Monads are important in the theory of pairs of adjoint functors. They can be viewed as monoid objects in a category of endofunctors (hence the name) and they generalize closure operators on posets to arbitrary categories. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ... In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ... In mathematics, a magma in a category, or magma object, can be defined in a category with a cartesian product. ... In category theory, a functor is a special type of mapping between categories. ... In mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties: if x ≤ y, then C(x) ≤ C(y), i. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...

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

Introduction

If F and G are an adjoint pair of functors, with F left adjoint to G, then the composition G o F will be a monad. Note that therefore a monad is a functor from a category to itself; and that if F and G were actually inverses as functors the corresponding monad would be 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 o G, is discussed under the dual theory of comonads. In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ...

The monad axioms can be seen at work in a simple example: let G be the forgetful functor from the category Group of groups to the category Set of sets. Then as F we can take the free group functor. In mathematics, the category Grp has the class of all groups for objects and group homomorphisms for morphisms. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ... The Cayley graph of the free group on two generators a and b In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many...

This means that the monad

T = G o 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 → T(X)

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

T(T(X)) → T(X)

can be made out of a natural concatenation of 'strings of strings'. This amounts to two natural transformations In formal language theory (and therefore in programming languages), concatenation is the operation of joining two character strings end to end. ... In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ...

I → T,

and

T o T → T.

They will satisfy some axioms about identity and associativity that result from the adjunction properties. In mathematics, associativity is a property that a binary operation can have. ...

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. In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation... In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ... In mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties: if x ≤ y, then C(x) ≤ C(y), i. ...

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 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. Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ... In category theory, a branch of mathematics, Becks monadicity theorem asserts that a functor is monadic if and only if U has a left adjoint; U reflects isomorphisms; and C has co-equalizers of U-split co-equalizer pairs, and U preserves those co-equalizers. ...

While monads are quite common, making them explicit is less so (the language belongs to the school of Mac Lane, and has rarely been used in the school of Grothendieck, which prefers to write out monads and comonads longhand). In categorical logic, an analogy has been drawn between the monad-comonad theory, and modal logic. Saunders Mac Lane (born 4 August 1909) is a US mathematician. ... Alexander Grothendieck (born March 28, 1928, Berlin) is one of the greatest mathematicians of the 20th century, with major contributions to algebraic geometry, homological algebra, and functional analysis. ... A modal logic is any logic for handling modalities: concepts like possibility, impossibility, and necessity. ...

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 axioms: Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ...

μ o Tμ = μ o μT (as natural transformations T³ → T; see the article on natural transformations for the explanation of the notations Tμ and μT)

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

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. In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ... Image File history File links Monad_mult. ... Image File history File links Monad_unit. ... In mathematics, associativity is a property that a binary operation can have. ... In category theory, a monoid (or monoid object) in a monoidal category C is an object M together with two morphisms called multiplication, and called unit, such that the diagrams and commute. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ... In category theory, a monoid (or monoid object) in a monoidal category C is an object M together with two morphisms called multiplication, and called unit, such that the diagrams and commute. ... In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ... In mathematics, a monoidal category (or tensor category) is a 2-category with one object (a 2-monoid). ...

Comonads and their importance

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 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. In category theory, an abstract branch of mathematics, the dual of a category C is the category formed by reversing all the morphisms of C. That is, we take Cop to be the category with objects that are those of C, but with the morphisms from X to Y in...

Since a comonoid is not a basic structure in abstract algebra, this is less familiar at an immediate level. A comonad in older terminology is a cotriple. Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ...

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. Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ... In mathematics, the idea of descent has come to stand for a very general idea, extending the intuitive idea of gluing in topology. ... For discussion of topoi in literary theory, see literary topos. ... In category theory, a branch of mathematics, Becks monadicity theorem asserts that a functor is monadic if and only if U has a left adjoint; U reflects isomorphisms; and C has co-equalizers of U-split co-equalizer pairs, and U preserves those co-equalizers. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... Fiber or fibre[1] is a class of materials that are continuous filaments or are in discrete elongated pieces, similar to lengths of thread. ...

Examples

The most important examples to think about when hearing the term "monad" are the free group example mentioned above, and closure operators. Here's 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 In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, a singleton is a set with exactly one element. ...

μ_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. In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...

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:Txto x$ of C such that the diagrams

and

commute. Image File history File links Monad_alg_mult. ... Image File history File links Monad_alg_unit. ...

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

commutes. Image File history File links Monad_alg_morph. ...

The category $C T$ of T-algebras is called the Eilenberg-Moore category of the monad T.

Given the monad T, another "canonical" category can be built: 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:xto Ty$ in C. The identity on an object x is the unit $η x$ , and the composite $gcirc f:xto Tz$ of two arrows $f:xto Ty$ and $g:yto Tz$ is given by $gcirc f=mu_zcirc Tgcirc f$ . This category is said to be the category of free algebras for the monad T in the sense that it is equivalent to the category whose objects are the algebras $(T x,μ x)$ (called the free algebras of $C$ ), where x is an object of C, and whose morphisms are the algebra morphisms between them.

Monads and adjunctions

An adjunction $(F,G,eta,varepsilon)$ between two categories C and D (where $F:Cto D$ is left adjoint to $G:Dto C$ and $η$ and $varepsilon$ are respectively the unit and the counit) always defines a monad $(GF, eta, Gvarepsilon F)$ . In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another. ...

Conversely, it is interesting to consider the adjunction 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, Gvarepsilon 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):Cto C_T$ , where $C T$ is the Kleisli category,
a terminal object $(F^T, G^T, eta, mu^T):Cto 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:Dto 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. In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ... In category theory, a branch of mathematics, Becks monadicity theorem asserts that a functor is monadic if and only if U has a left adjoint; U reflects isomorphisms; and C has co-equalizers of U-split co-equalizer pairs, and U preserves those co-equalizers. ...

Uses

Monads are used in functional programming to express types of sequential computation (sometimes with side-effects). See monads in functional programming. Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... Some functional programming languages, particularly Haskell, make use of the monad concept from category theory, a branch of mathematics that describes patterns applicable to many mathematical fields. ...

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"

Categories: Adjoint functors

Results from FactBites:

Monad (category theory) - Wikipedia, the free encyclopedia (1354 words)
	In category theory, a monad or triple is a type of functor, together with two associated natural transformations.
	Monads are important in the theory of pairs of adjoint functors.
	While monads are quite common, making them explicit is less so (the language belongs to the school of Mac Lane, and has rarely been used in the school of Grothendieck, which prefers to write out monads and comonads longhand).

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Introduction GA_googleFillSlot("encyclopedia_square");