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 us to skip some of the standard symbol-pushing that is common to all algebras. This general theory is monads. The idea is that the notion of finite nonempty words is one monad, while the notion of -words is another monad.
Definition. A monad, consists of the following ingredients:
• for each set , a new set , called the structures over .
• for each function , a new function , called the lifting of .
• for each set , a flattening operation .
• for each set , a unit operation .
These ingredients are subject to axioms called “functor”, “natural” and “monoid” that will be discussed below.
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.
Example. The monad of nonempty finite words is defined as follows. The structures over are , i.e. the nonempty finite words over . The lifting is obtained by applying to each letter of . The flattening operation is the natural one which takes a word of words into a single word, e.g. the flattening of is . The unit operation maps a letter to a single letter word consisting of this letter.
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.
Functor axioms. The first group of 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 , the result is the identity function on . Preserving composition means that for every functions and , the following diagram commutes
Natural axioms. The second group of axioms is that for every function , the following diagrams commute. This means that flattening and unit are what category theorists call natural transformations.
Monoid axioms. The first monoid axiom says, essentially, that applying the unit to a structure (i.e. an element of ) 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 :
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.
This completes the axioms of a monad, and therefore also the definition of a monad.
Eilenberg-Moore algebras. In this lecture, the point of monads is that each monad comes with a natural notion of algebra, called its Eilenberg-Moore algebra. 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.
Definition. An Eilenberg-Moore algebra for a monad is defined to be a pair of:
• a set , called the universe of the algebra, and
• a multiplication operation
such that is the identity on , and which is associative in the sense that the following diagram commutes
Instead of Eilenberg-Moore algebra for a monad , we will write -algebra. We denote -algebras by blackboard letters , and use the convention that the universe of (respectively ) is written by a non-boldface letter (respectively ), while its multiplication operation is denoted by (respectively ). In the special case of the monad of possibly finite words, an Eilenberg-Moore algebra is the same thing as a monoid, in the sense of Definition 2 here. Likewise, semigroups are Eilenberg-Moore algebras for the monad of nonempty finite words.
Homomorphisms. A homomorphism of -algebras and is a function between their universes which is consistent with the multiplication operation in the sense that the following diagram commutes
Free algebra. For a set , define its free -algebra as follows: the universe is , while the multiplication operation is flattening. The two monoid axioms of a monad imply that this is indeed a -algebra. By abuse of notation, we denote the free -algebra by . For example, in the special case of the monad of nonempty finite words, the free algebra is . The reason for the name free is given in the following lemma.
Free Algebra Lemma. If is a -algebra and is a set, then for every function from to the universe of there is a unique homomorphism of -algebras which extends it in the sense that the following diagram commutes
Proof. Let us first show that if the homomorphism exists, then it is unique. Suppose that is a homomorphism which extends in the sense of the diagram above. Consider the following diagram:
The left triangular face commutes by applying the functor to the diagram in the statement of the lemma which says that extends . (Applying a functor preserves commuting diagrams.) The right triangular face commutes by the first monoid axiom of a monad. The lower face commutes by the assumption that is a homomorphism. Therefore, the perimeter of the diagram says that must be equal to followed by multiplication in . We now show that defined this way really is a homomorphism.
Being a homomorphism is that the perimeter of the following diagram commutes.
The lower triangular face is simply the definition of , while the upper triangular face is the definition of with the functor 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 .