Monad (category theory)

From Academic Kids

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 are formally similar to monoids (hence the name) and generalize closure operators on posets to arbitrary categories.

Contents

Introduction

If F and G are an adjoint pair of functors, with F left adjoint to G, then the composition GoF 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 FoG, 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 Group of groups to the category Set of sets. Then as F we can take the free group functor.

This means that the monad

T = GoF

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

XT(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

IT,

and

ToTT.

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 the category arising from a partially ordered set (P, ≤) (with a single morphism from x to y iff xy), 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, 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 algebra.

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.

Formal definition

If C is a category, a monad on C consists of a functor T : CC together with two natural transformations: ε : 1CT (where 1C denotes the identity functor on C) and μ : T2T (where T2 is the functor T o T from C to C). These are required to fulfill the following axioms:

  • μ o Tμ = μ o μT (as natural transformations T3T; see the article on natural transformations for the explanation of the notations Tμ and μT)
  • μ o Tε = μ o εT = 1T (as natural transformations TT; 1T 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.

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 Cop. 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. A comonad in older terminology is a cotriple.

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.

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 : AB 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 : AT(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.

Uses

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

See also

  • Monad for other meanings of the term

References

  • Daniele Turi: Category Theory Lecture Notes (http://www.dcs.ed.ac.uk/home/dt/CT/categories.pdf) (1996-2001), based on MacLane's book "Categories for the Working Mathematician"
  • Michael Barr and Charles Wells: Category Theory Lecture Notes (http://folli.loria.fr/cds/1999/library/pdf/barrwells.pdf) (1999), based on their book "Category Theory for Computing Science"
Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools