Part II: Free Monoids

String Diagrams

The utility of diagrams in formulating and proving theorems in category theory cannot be overemphasized. While working my way through the construction of free monoids, I noticed that there was a particular set of manipulations that had to be done algebraically, with little help from diagrams. These were operations involving a mix of tensor products and composition of morphisms. Tensor product is a bifunctor, so it preserves composition; which means you can often slide products through junctions of arrows—but the rules are not immediately obvious. Diagrams in which objects are nodes and morphisms are arrows have no immediate graphical representation for tensor products. A thought occurred to me that maybe a dual representation, where morphisms are nodes and objects are edges would be more accommodating. And indeed, a quick search for “string diagrams in monoidal categories” produced a paper by Joyal and Street, “The geometry of tensor calculus.”

The idea is very simple: if you represent morphisms as points on a plane, you have two additional dimensions to play with composition and tensoring. Two morphism—represented as points—can be composed if they share an object, which can be represented as a line connecting them. By convention, we read composition from the bottom of the diagram up. We follow lines as they go through points—that’s composition. Two lines ascending in parallel represent a tensor product. The geometry of the diagram just works!

Let me explain it on a simple example—the left unit law for a monoid (m, \pi, \mu):

\mu \circ (\pi \otimes m) = id

The left hand side is a composition of two morphisms. The first morphism \pi \otimes m starts from the object I \otimes m (see Fig. 12).

Fig. 12. Left unit law

In principle, there should be two parallel lines at the bottom, one for I and one for m; but I \otimes m is isomorphic to m, so the I line is redundant and can be omitted. Scanning the diagram from the bottom up, we encounter the morphism \pi in parallel with the m line. That’s exactly the graphical representation of \pi \otimes m. The output of \pi is also m, so we now have two upward moving m lines, corresponding to m \otimes m. That’s the input of the next morphism \mu. Its output is the single upward moving m. The unit law may be visualized as pulling the two m strings in opposite direction until the whole diagram is straightened to one vertical m string corresponding to id_m.

Here’s the right unit law:

\mu \circ (m \otimes \pi) = id

It works like a mirror image of the left unit law:

Fig. 13. Right unit law

The associativity law can be illustrated by the following diagram:

Fig. 14. Associativity law

The important property of a string diagram is that, because of functoriality, its value—the compound morphism it represents—doesn’t change under continuous transformations.

Monoid

First we’d like to show that the carrier of the free h-algebra (m, \sigma) which, as we’ve seen before, is also the initial algebra for the list functor I + h \otimes -, is automatically a monoid. To show that, we need to define its unit and multiplication—two morphisms that satisfy monoid laws. The obvious candidate for unit is the universal mapping \pi \colon I \to m. It’s the morphism in the definition of the free algebra from the previous post (see Fig 15).

Fig. 15. Free h-algebra (m, \sigma) generated by I

Multiplication is a morphism:

\mu \colon m \otimes m \to m

which, if you think of a free monoid as a list, is the generalization of list concatenation.

The trick is to show that m \otimes m is also a free h-algebra whose generator is m itself. We could then use the universality of m \otimes m to generate the unique algebra morphism from it to m (which is also an h-algebra). That will be our \mu.

Proposition. {Monoid.}

The free h-algebra (m, \sigma) generated by the unit object I is a monoid whose unit is:

\pi \colon I \to m

and whose multiplication:

\mu \colon m \otimes m \to m

is the unique h-algebra morphism

(m \otimes m, \sigma \otimes m) \to (m, \sigma)

induced by the identity morphism id_m.

Proof.
In the previous post we’ve shown that, if (m, \sigma) is a free algebra generated by the unit object I with the universal map \pi, then (m \otimes k, \sigma \otimes k) is a free algebra generated by k with the universal map \pi \otimes k (see Fig. 16).

Fig. 16. Free h-algebra generated by k \cong I \otimes k

We get \mu by redrawing this diagram: using m as both the generator and the target algebra, and replacing f with id_m (see Fig. 17):

Fig. 17. Monoid multiplication as an h-algebra morphism

Since so defined \mu is an h-algebra morphism, it makes the following diagram, Fig. 18, commute.

Fig. 18. \mu is an h-algebra morphism

This commuting condition can be redrawn as the identity of two string diagrams (Fig. 19) corresponding to the two paths through the original diagram.

Fig. 19. String diagram showing that \mu is an algebra morphism

The universal condition in Fig. 17:

\mu \circ (\pi \otimes m) = id_m

gives us immediately the left unit law for the monoid.

The right unit law:

\mu \circ (m \otimes \pi) = id_m

requires a little more work.

There is a standard trick that we can use to show that two morphisms, whose source (in this case m) is a free algebra, are equal. It’s enough to prove that they are algebra morphisms, and that they are both induced by the same morphism (in this case \pi). Their equality then follows from the uniqueness of the universal construction.

We know that \mu is an algebra morphism so, if we can show that m \otimes \pi is also an algebra morphism, their composition will be an algebra morphism too. Trivially, id_m is an algebra morphism so, if we can show that the two are induced by the same regular morphism \pi, then they must be equal.

To show that m \otimes \pi is an h-algebra morphism, we have to show that the diagram in Fig. 20 commutes.

Fig. 20. m \otimes \pi as an h-algebra morphism

We can redraw the two paths through Fig. 20 as two string diagrams in Fig. 21. They are equal because they can be deformed into each other.

Fig. 21. String diagram showing that m \otimes \pi is an algebra morphism

Therefore the composition \mu \circ (m \otimes \pi) is also an h-algebra morphism. The string diagram that illustrates this fact is shown in Fig. 22.

Fig. 22. String diagram showing that \mu \circ (m \otimes \pi) is an algebra morphism

Since the identity h-algebra morphism is induced by \pi, we’d like to show that \mu \circ (m \otimes \pi) is also induced by \pi (Fig. 23).

Fig. 23. Universal property of the free h-algebra generated by I, with the algebra morphism induced by \pi

To do that, we have to prove the universal condition in Fig. 23:

\mu \circ (m \otimes \pi) \circ \pi = \pi

This is represented as a string diagram identity in Fig. 24. We can deform this diagram by sliding the left \pi node up, past the right \pi node, and then using the left identity.

Fig. 24. Universal condition in Fig. 23.

This concludes the proof of the right identity.

The proof of associativity is very similar, so I’ll just sketch it. We have to show that the two diagrams in Fig. 14 are equal. We’ll use the same trick as before. We’ll show that they are both algebra morphisms. Their source is a free algebra generated by m \otimes m (see Fig. 25—the other diagram has \mu \circ (\mu \otimes m) replaced by \mu \circ (m \otimes \mu)). The universal condition follows from the unit law for m. Associativity condition:

\mu \circ (\mu \otimes m) = \mu \circ (m \otimes \mu)

will then follow from the uniqueness of the universal construction.

Fig. 25. One part of associativity as an h-algebra morphism

You can easily convince yourself that showing that something is an h-algebra morphism can be done by first attaching the h leg to the left of the string diagram and then sliding it to the top of the diagram, as illustrated in Fig. 26. This can be accomplished by repeatedly using the fact that \mu is an h-algebra morphism.

Fig. 26. String diagram showing that one of the associativity diagrams is an h-algebra morphism

The same process can be applied to the second associativity diagram, thus completing the proof.

\square

For Haskell programmers, recall from the previous post our construction of the free h-algebra generated by k and the derivation of the algebra morphism g from it to the internal-hom algebra:

g :: Expr -> (k -> n)
g () = f
g a  = k -> nu (a, f k)
g (a, b) = k -> nu (a, nu (b, f k))
...

In the current proof we have replaced k with m, which generalizes the list of hs, f became id, and \nu is a function that prepends an element to a list. In other words, g concatenates its list-argument in front of the second list, and it does it in the correct order.

Free Monoid

The monoid whe have just constructed from the free algebra is a free monoid. As we did with free algebras, instead of using the free/forgetful adjunction to prove it, we’ll use the free-object universal construction.

Theorem. {Free Monoid.}

The monoid (m, \pi, \mu) is a free monoid generated by h, with a universal mapping given by u = \sigma \circ (h \otimes \pi):

That is, for any monoid (n, \eta, \nu) and any morphism s \colon h \to n, there is a unique monoid morphism t from (m, \pi, \mu) to (n, \eta, \nu) such that the universal condition holds:

t \circ u = s

(see Fig. 27).

Fig. 27. Free monoid diagram

Proof. Recall that (m, \sigma) is a free h-algebra generated by I. It turns out that any monoid (n, \eta, \nu), for which there is a morphism s \colon h \to n, is automatically a carrier of an h-algebra. We construct its structure map \lambda by combining s with monoid multiplication \nu:

We can use n‘s monoidal unit \eta to insert I into n. Because (m, \sigma) is a free h-algebra, there is a unique algebra morphism, let’s call it t, from it to (n, \lambda), which is induced by \eta, such that t \circ \pi = \eta (see Fig. 28). We want to show that this algebra morphism is also a monoid morphism. Furthermore, if we can show that this is the unique monoid morphism induced by s, we will have a proof that m is a free monoid.

Fig. 28. Algebra morphism between monoids

Since t is an algebra morphism, the rectangle in Fig. 29 commutes.

Fig. 29. t is an h-algebra morphism

Let’s redraw it as an identity of string diagrams, Fig. 30. We’ll make use of it in a moment.

Fig. 30. t is an h-algebra morphism

Going back to Fig. 27, we want to show that the universal condition holds, which means that we want the diagram in Fig. 31 to commute (I have expanded the definition of u).

Fig. 31. Free monoid universal condition

In other words we want show that the following two string diagrams are equal:

Fig. 32. Free monoid universal condition

Using the identity in Fig. 30, the left hand side can be rewritten as:

Fig. 33. Step 1 in transforming Fig 32

The right leg can be shrunk down to \eta using the universal condition in Fig. 28:

t \circ \pi = \eta

which, incidentally, also expresses the fact that t preserves the monoidal unit.

Finally, we can use the right unit law for the monoid n, Fig. 34,

Fig. 34. Right unit law for monoid n

to arrive at the right hand side of the identity in Fig. 32. This completes the proof of the universal condition in Fig. 27.

Now we have to show that t is a full-blown monoid morphism, that is, it preserves multiplication (Fig. 35).

Fig. 35. Preservation of multiplication

The corresponding string diagrams are shown in Fig. 36.

Fig. 36. Preservation of multiplication

Let’s start with the fact that m \otimes m is the free h-algebra generated by m. We will show that the two paths through the diagram in Fig. 35 are both h-algebra morphisms, and that they are induced by the same regular morphism t \colon m \to n. Therefore they must be equal.

The bottom path in Fig. 35, t \circ \mu, is an h-algebra morphism by virtue of being a composition of two h-algebra morphisms. This composite is induced by morphism t in the diagram Fig. 37.

Fig. 37. h-algebra morphism t \circ \mu

The universal condition in Fig. 37 follows from the diagram in Fig. 38, which follows from the left unit law for the monoid (m, \pi, \mu).

Fig. 38. Universal condition in Fig. 37

We want to show that the top path in Fig. 35 is also an h-algebra morphism, that is, the diagram in Fig. 39 commutes.

Fig. 39. h-algebra morphism diagram for \nu \circ (t \otimes t)

We can redraw this diagram as a string diagram identity in Fig. 40.

Fig. 40. h-algebra morphism diagram for \nu \circ (t \otimes t)

First, let’s use the associativity law for the monoid n to transform the left hand side. We get the diagram in Fig. 41.

Fig. 41. After applying associativity, we can apply Fig. 30

We can now apply the identity in Fig. 30 to reproduce the right hand side of Fig. 40.

We have thus shown that both paths in Fig. 35 are algebra morphisms. We know that the bottom path is induced by morphism t. What remains is to show that the top path, which is given by \nu \circ (t \otimes t) is induced by the same t. This will be true, if we can show the universal condition in Fig. 42.

Fig. 42. h-algebra morphism \nu \circ (t \otimes t)

This universal condition can be expanded to the diagram in Fig. 43.

Fig. 43. Universal condition in Fig. 42

Here’s the string diagram that traces the path around the square (Fig. 44).

Fig. 44. Path around Fig. 43 as a string diagram

First, let’s use the preservation of unit by t, Fig. 45, to shrink the left leg,

Fig. 45. Preservation of unit by t

and follow it with the left unit law for the monoid (n, \eta, \nu) (Fig. 46). The result is that Fig. 44 shrinks to the single morphism t, thus making Fig. 43 commute.

Fig. 46. Left unit law for the monoid n

This completes the proof that t is a monoid morphism.

The final step is to make sure that t is the unique monoid morphism from m to n. Suppose that there is another monoid morphism t' (replacing t in Fig. 28). If we can show that t' is also an h-algebra morphism induced by the same \eta, it will have to, by universality, be equal to t. In other words, we have to show that the diagram in Fig. 28 also works for t'. Our assumptions are that both t and t' are monoid morphisms, that is, they preserve unit and multiplication; and they both satisfy the universal condition in Fig 27. In particular, t' satisfies the condition in Fig. 47.

Fig. 47. Free monoid universal condition for t' as a string diagram

Notice that, in the first part of the proof, we started with an h-algebra morphism t and had to show that it’s a monoid morphism. Now we are going in the opposite direction: we know that t' is a monoid morphism, and have to show that it’s an h-algebra morphism, and that the universal condition in Fig. 28

t' \circ \pi = \eta

holds. The latter simply restates our assumption that t' preserves the unit.

To show that t' is an algebra morphism, we have to show that the diagram in Fig 48 commutes.

Fig. 48. t' as an h-algebra morphism

This diagram may be redrawn as a pair of string diagrams, Fig 49.

Fig. 49. t' as an algebra morphism

The proof of this identity relies on redrawing string diagrams using the identities in Figs. 12, 19, 36, and 47. Before we continue, you might want to try it yourself. It’s an exercise well worth the effort.

We start by expanding the s node using the diagram in Fig. 47 to get Fig. 50.

Fig. 50. After expanding the left leg of the diagram in Fig. 49, we can apply preservation of multiplication by t'.

We can now use the preservation of multiplication by t' to obtain Fig 51.

Fig. 51. Applying the fact that \mu is an h-algebra morphism

Next, we can use the fact that \mu is an h-algebra morphism, Fig. 19, to slide the \sigma node up, and obtain Fig. 52.

Fig. 52. Applying left unit law

We can now use the left unit law for the monoid m:

\mu \circ (\pi \otimes m) = id

as illustrated in Fig. 12, to arrive at the right hand side of Fig. 49.

This concludes the proof that t' must be equal to t.

\square

Conclusion

To summarize, we have shown that the free monoid can be constructed from a free algebra of the functor h \otimes -. This is a very general result that is valid in any monoidal closed category. Earlier we’ve seen that this free algebra is also the initial algebra of the list functor I + h \otimes -. The immediate consequence of this theorem is that it lets us construct free monoids in functor categories with interesting monoidal structures. In particular, we get a free monad as a free monoid in the category of endofunctors with functor composition as tensor product. We can also get a free applicative, or free lax monoidal functor, if we define the tensor product as Day convolution—the latter can be also constructed in the profunctor category.

Advertisements