{"id":315,"date":"2015-06-09T13:37:13","date_gmt":"2015-06-09T11:37:13","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=315"},"modified":"2015-06-09T16:49:41","modified_gmt":"2015-06-09T14:49:41","slug":"8-monads","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/8-monads","title":{"rendered":"8. Monads"},"content":{"rendered":"

So far, we had monoids (and semigroups), as well as an algebraic structure for \"\omega\"-words. In the future, we will also study algebraic structures for other kinds of words, e.g. words indexed by countable total orders, or maybe even arbitrary total orders. Before presenting those structures, we will introduce some general theory, which will allow us to skip some of the standard symbol-pushing that is common to all algebras. This general theory is\u00a0monads.\u00a0<\/em>The idea is that the notion of finite nonempty words is one monad, while the notion of \"\infty\"-words is another monad.<\/p>\n

\n

 <\/p>\n

Definition.\u00a0<\/strong>A\u00a0monad,\u00a0<\/em>consists of the following ingredients:<\/p>\n

\u2022 for each set \"X\", a new set \"\monad X\", called the structures<\/em> over \"X\".
\n\u2022 for each function\u00a0\"f : X \to Y\", a new function \"\monad f : \monad X \to \monad Y\", called the lifting<\/em> of \"f\".
\n\u2022 for each set \"X\", a flattening\u00a0<\/i>operation \"\flatt X : \monad \monad X \to \monad X\".
\n\u2022 for each set \"X\", a\u00a0unit\u00a0<\/em>operation \"\unit X : X \to \monad X\".<\/p>\n

These ingredients are subject to axioms called “functor”, “natural” and “monoid” that will be discussed below. \"\Box\"<\/p>\n

\n

 <\/p>\n

The above definition is actually a special case of the general definition of monads. Monads can be applied to any category, while the above definition is only given for the category of sets. However, since in this lecture we only use monads in the category of sets, we only give the special case of the definition.<\/p>\n

Example.\u00a0<\/strong>The monad of<\/em>\u00a0nonempty finite words<\/em>\u00a0is defined as follows. The\u00a0<\/em>structures over \"X\" are \"X^+\", i.e. the nonempty finite words over \"X\". The lifting \"f^+(w)\" is obtained by applying \"f\" to each letter of \"w\". The flattening operation is the natural one which takes a word of words into a single word, e.g. the flattening of \"(aba)(aa)(b)\" is \"abaaab\". The unit operation maps a letter to a single letter word consisting of this letter. \"\Box\"<\/p>\n

We now begin discussing the axioms of a monad. When reading the axioms below, it is a good idea to check that they are satisfied by the monad of nonempty words in the example above.<\/p>\n

Functor axioms.\u00a0<\/b>The first group\u00a0of axioms is that the first two ingredients of a monad are a functor in the sense of category theory. This means lifting is preserves the identity and composition of functions. Preserving identity means that if we lift the identity function on \"X\", the result is the identity function on \"\monad X\". Preserving composition means that for every functions \"f : X \to Y\" and \"g : Y \to Z\", the following diagram commutes <\/p>\n

  <\/span>   <\/span>\"\[ \xymatrix @R=2pc { \monad X \ar[r]^{\monad f} \ar[dr]_{\monad (g \circ f)} & \monad Y \ar[d]^{\monad g} \\& \monad Z<\/p>\n

Natural axioms. <\/strong>\u00a0The second group of axioms is that for every function \"f X \to Y\", the following diagrams commute. This means that flattening and unit are what category theorists call natural transformations<\/em>.<\/p>\n

  <\/span>   <\/span>\"\[ \vcenter{\xymatrix @R=2pc { X \ar[r]^{f} \ar[d]_{\unit X} & Y \ar[d]^{\unit Y} \\<\/p>\n

Monoid axioms.\u00a0<\/strong>The first monoid axiom says, essentially, that applying the unit to a structure (i.e. an element of \"\monad X\") and flattening has no effect. The expression “applying the unit to a structure” is ambiguous in the sense that it has two different interpretations, and both interpretations are dealt with in the axiom, which says that the following diagram commutes for every set \"X\":<\/p>\n

  <\/span>   <\/span>\"\[\vcenter{\xymatrix @R=2pc { \monad X \ar[dr]^{\mathrm{id}_X} \ar[r]^{\unit {\monad X}} \ar[d]_{\monad \unit X} & \monad \monad X \ar[d]^{\flatt X} \\<\/p>\n

The second monoid axiom is the most important one. It says that if we start with a structure of structures of structures, and we flatten it twice, then we get the same result regardless of which order of flattening we employ. The appropriate commuting diagram is given below.<\/p>\n

  <\/span>   <\/span>\"\[ \vcenter{\xymatrix @R=2pc @C=3pc {\monad \monad \monad X \ar[r]^{\flatt{ \monad X}} \ar[d]_{\monad{ \flatt X}} & \monad \monad X \ar[d]^{\flatt X} \\<\/p>\n

This completes the axioms\u00a0of a monad, and therefore also the definition of a monad.<\/p>\n

\n

 <\/p>\n

Eilenberg-Moore algebras.\u00a0<\/strong>In this lecture, the point of monads is that each monad comes with a natural notion of algebra, called its Eilenberg-Moore algebra<\/em>. For example, in the monad of nonempty finite words, Eilenberg-Moore algebras will be semigroups, in the monad of possibly empty finite words (with the obvious definition), the Eilenberg-Moore algebras will be monoids.<\/p>\n

Definition.\u00a0<\/strong>An Eilenberg-Moore algebra for a monad<\/em> \"\monad\" is defined to be a pair\u00a0of:
\n\u2022 a set \"A\", called the\u00a0universe\u00a0<\/em>of the algebra, and
\n\u2022 a\u00a0multiplication operation\u00a0<\/em>\"\mult : \monad A \to A\"
\nsuch that \"\multnoarg \circ \unit A\" is the identity on \"A\", and which is associative in the sense that the following diagram commutes<\/p>\n

  <\/span>   <\/span>\"\[\vcenter{\xymatrix @R=2pc @C=3pc { \monad \monad A \ar[r]^{\flatt A} \ar[d]_{\monad \multnoarg} & \monad A \ar[d]^{\multnoarg} \\<\/p>\n

\"\Box\"<\/p>\n

Instead of Eilenberg-Moore algebra for a monad \"\monad\", we will write \"\monad\"-algebra. We denote \"\monad\"-algebras by\u00a0blackboard\u00a0letters \"\alg\", and use the convention that the\u00a0universe of \"\alg\" (respectively \"\balg\") is written by a non-boldface letter \"A\" (respectively \"B\"), while its multiplication operation is denoted by \"\mult \alg\" (respectively \"\mult \balg\"). In the special case of the monad of possibly\u00a0finite words, an Eilenberg-Moore algebra is the same thing as a monoid, in the sense of Definition 2 here<\/a>. Likewise, semigroups are Eilenberg-Moore algebras for the monad of nonempty finite words.<\/p>\n

 <\/p>\n

 <\/p>\n

Homomorphisms.\u00a0<\/b>A homomorphism\u00a0of \"\monad\"-algebras \"\alg\" and \"\balg\"\u00a0<\/em>is a function \"h : A \to B\" between their universes which is consistent with the multiplication operation in the sense that the following diagram commutes <\/p>\n

  <\/span>   <\/span>\"\begin{align*}<\/p>\n

Free algebra.\u00a0<\/strong>For a set \"X\", define its free \"\monad\"-algebra\u00a0<\/em>as follows: the universe is\u00a0\"\monad X\",\u00a0while the\u00a0multiplication operation is flattening. The two monoid axioms of a monad imply that this is indeed a \"\monad\"-algebra. By abuse of notation, we denote the free \"\monad\"-algebra by \"\monad X\". \u00a0For example, in the special case of the monad of nonempty finite words, the free algebra is\u00a0\"X^+\". The reason for the name\u00a0free\u00a0<\/em>is given in the following lemma.<\/p>\n

Free Algebra Lemma. \u00a0<\/strong>If \"\alg\" is a \"\monad\"-algebra and \"\Sigma\" is a set, then for every\u00a0function \"f\" from \"\Sigma\" to the universe of \"\alg\" there is a unique homomorphism of \"\monad\"-algebras \"h : \monad \Sigma \to \alg\" which extends it in the sense that the following diagram commutes<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{ \Sigma \ar[dr]_{f} \ar[r]^{\unit \Sigma} & \monad \Sigma \ar[d]^h \\ & \alg}\]\"<\/p>\n

\"\Box\"<\/p>\n

Proof.<\/b>\u00a0Let us first show that if the homomorphism \"h\" exists, then it is unique. Suppose that \"h\" is a homomorphism which extends \"f\" in the sense of the diagram above. Consider the following diagram:<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix@C=4pc{<\/p>\n

The left triangular face commutes by applying the functor \"\monad\" to the diagram in the statement of the lemma which says that \"h\" extends \"f\".\u00a0(Applying a functor preserves commuting diagrams.) \u00a0The right triangular face commutes by the first monoid axiom of a monad. The lower face commutes by the assumption that \"h\" is a homomorphism. Therefore, the perimeter of the diagram says that \"h\" must be equal to \"\monad f\" followed by multiplication in \"\alg\". We now show that \"h\" defined this way really is a homomorphism.<\/p>\n

Being a homomorphism is that the perimeter of the following diagram commutes.<\/p>\n

  <\/span>   <\/span>\"\begin{align*}<\/p>\n

The lower triangular face is simply the definition of \"h\", while the upper triangular face is the definition of \"h\" with the functor \"\monad\" applied to it. The left trapezoid face is the second of the “natural axioms”, while the right trapezoid face is the associativity of multiplication in \"\alg\". \u00a0\"\Box\"<\/p>\n","protected":false},"excerpt":{"rendered":"

So far, we had monoids (and semigroups), as well as an algebraic structure for -words. In the future, we will also study algebraic structures for other kinds of words, e.g. words indexed by countable total orders, or maybe even arbitrary total orders. Before presenting those structures, we will introduce some general theory, which will allow […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":42,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-315","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/315"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=315"}],"version-history":[{"count":4,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/315\/revisions"}],"predecessor-version":[{"id":320,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/315\/revisions\/320"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/42"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}