The Unapologetic Mathematician

Mathematics for the interested outsider

Mac Lane’s Coherence Theorem

Okay, as I promised yesterday, I’m going to prove the Coherence Theorem for monoidal categories today. That is, any two natural transformations built from \alpha, \lambda, and \rho between any two functors built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} are equal once we know the pentagon and triangle identities are satisfied.

Here’s an example. Brace yourself for the diagram.
A Diagram for the Coherence Theorem

Okay, the outer pentagon is the pentagon identity for the quadruple (A,B,\mathbf{1},\mathbf{1}). The triangles in the upper-right and on the left are the triangle identity. The quadrilaterals are all naturality squares for \alpha and \rho. And the last triangle near the center is the identity we’re proving. It says that \rho_{A\otimes B}=(1_A\otimes\rho_B)\circ\alpha_{A,B,\mathbf{1}}. There’s a similar diagram to show that \lambda_A\otimes1_B=\lambda_{A\otimes B}\circ\alpha_{\mathbf{1},A,B}, which you should find.

Now we’re ready to really get down to work. We can get any functor built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} by writing down a parenthesized sequence of multiplications like \underline{\hphantom{X}}\otimes((\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}))\otimes\underline{\hphantom{X}}) and filling some of the open slots with \mathbf{1}.

First, let’s get rid of those identity objects. Each of them shows up either to the right or to the left of some product symbol, so we can use either a \rho or a \lambda to remove it, but there’s some choice involved here. For example, near the \mathbf{1} we’re trying to get rid of the functor might look like (\underline{\hphantom{X}}\otimes\mathbf{1})\otimes\underline{\hphantom{X}}. We can either use a \rho right away, or we can hit it with an associator and then use a \lambda. The triangle identity says that these two ways of removing the \mathbf{1} are the same. Similarly, if nearby the functor looks like (\mathbf{1}\otimes\underline{\hphantom{X}})\otimes\underline{\hphantom{X}} or (\underline{\hphantom{X}}\otimes\underline{\hphantom{X}})\otimes\mathbf{1} we have some leeway, but the two new triangles we proved above say we’ll get the same natural transformation to remove the \mathbf{1} either way. The upshot is that any two natural transformations we use to reach a functor without any slots filled with identity objects are the same.

So now we just have to deal with functors built from monoidal products. Each of them is just a different way to parenthesize a multiplication of some number of variables, and the associator (or its inverse) lets us move between different ways of parenthesizing the same number of variables. One convenient way of parenthesizing is to have all pairs of parentheses at the end, like \underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes(\underline{\hphantom{X}}\otimes\underline{\hphantom{X}}))), and what we’re going to do is try to make every functor look like this.

Now imagine a big diagram with all the different ways of parenthesizing a product of n terms as its vertices, and draw an arrow from one vertex to another if you can go from the first to the second by applying one associator. When n=4, this is just the pentagon diagram. Try actually drawing the one for n=5 (there should be 14 vertices). We’re allowed to walk forwards or backwards along the arrows, since the associator is an isomorphism. Every path is a natural isomorphism between the two functors at its ends, since it’s a composition of natural isomorphisms. What the Coherence Theorem says is that any two paths between the same two points give the same natural isomorphism.

Let’s say that we have a path from a vertex V in this diagram to a vertex W, which might consist of some forward arrows and some reverse arrows. Each time we change directions from forward to reverse we can pick a path using only forward arrows from the turning point to the vertex R, which has all its parentheses to the right. Here’s a sketch of what I’m talking about
Another Diagram for the Coherence Theorem
Each arrow here is a path consisting of only forward arrows. We start with the path along the top. At the two points where we change from walking forwards along the arrows to walking backwards, we pick a path made up of only forward arrows to the point R. Now the path we started with is the same as walking forwards a step from V, down to R, back the way we just came (undoing the isomorphism), forwards to the next juncture, down to R and back, and on to W.

It seems we’ve made our lives more complicated by adding in these side-trips to R, just to undo them immediately, but something really nice happens. There are two paths here from the middle point of our original path down to R, and each of them consists only of forward arrows. If these two paths are the same, I can cut out that whole middle loop. Then our path walks straight down from V to R along forward arrows, then back up to W along backward arrows. If there are more changing points in the original path, then there are just more loops to cut out. So if any two paths from a vertex to R consisting of only forward arrows give the same isomorphism, then every path from V to W is the same as one passing through R. And even better, the paths from V and W to R themselves consist entirely of forward arrows, so there’s only one of each of them. That is, if we can show that any two paths made of forward arrows from an arbitrary vertex V to the fixed vertex R give the same natural isomorphism, then we’re done.

Now here’s where it gets a bit messy. We’ll need to use inductions on both the number of terms in our functors and on how close they are to R. We know the Coherence Theorem works up to n=4 terms, because that’s the pentagon identity. We’ll prove it for n terms assuming it’s known for fewer than n terms and work our way up. Similarly, for a fixed n we’ll start by establishing the result for the vertices closest to R and work our way out.

Let’s start with a functor V, which is the product of functors V_1 and V_2. Let \beta and \gamma be two arrows out of V to functors X and Y, respectively, which them continue on to paths to R. We need to find a Z and paths from X and Y to Z to make the square commute. Since X and Y are both closer than V to R, we can assume that both paths from X to R in the diagram give the same isomorphism, as do both paths from Y to R. Then since Z is even closer to R we can assume there’s only one transformation from Z to R, so the result follows for V. Here’s another sketch:
Yet Another Diagram for the Coherence Theorem

If \beta and \gamma are already the same there’s nothing to be done. Pick Z=X=Y and go home. Otherwise there are three possibilities for \beta

  • \beta applies an associator inside V_1
  • \beta applies an associator inside V_2
  • V_1=V_{11}\otimes V_{12}, and \beta:(V_{11}\otimes V_{12})\otimes V_2\rightarrow V_{11}\otimes(V_{12}\otimes V_2) is an associator

and the same three for \gamma.

If \beta and \gamma both act within V_1 or within V_2 then we’re done because of the induction on the number of terms. If \beta acts in one factor and \gamma in the other then they commute because \otimes is a functor of two variables. All that’s left to see is if \beta is an associator and \gamma acts in either V_1 or V_2.

If \gamma acts inside V_2, sending it to V_2', then we get (1_{V_{11}}\otimes(1_{V_{12}}\otimes\gamma))\circ\alpha_{V_{11},V_{12},V_2}=\alpha_{V_{11},V_{12},V_2'}\circ((V_{11}\otimes V_{12})\otimes\gamma) by the naturality of \alpha. A similar statement holds if \gamma acts inside V_{11} or V_{12}. Finally, if \gamma is itself the associator \alpha_{V_{111},V_{112},V_{12}}, then \beta and \gamma are actually the first steps around the pentagon identity, so we can use the far vertex of the pentagon as our Z.

And after all these cases, we’re done. If two paths start out differently from V we can guide them back together so that the square where they differed commutes, and we can keep doing this until we get to R. Thus there’s only one natural isomorphism built from associators taking a functor the the fully right-parenthesized functor on the same number of terms.

Thus there’s only one natural isomorphism built from associators between any two functors built from monoidal products on the same number of terms.

Thus any two natural transformations built from \alpha, \lambda, and \rho between any two functors built from \underline{\hphantom{X}}\otimes\underline{\hphantom{X}} and \mathbf{1} are equal, given that the pentagon and the triangle identities are satisfied.

Now breathe.

About these ads

June 29, 2007 - Posted by | Category theory

9 Comments »

  1. [...] I head off to Portugal on Tuesday. This theorem is another heavy one to prove, so if the proof of the Coherence Theorem was overwhelming you might just want to skim this one and remember the result: Any monoidal [...]

    Pingback by The “Strictification” Theorem « The Unapologetic Mathematician | July 1, 2007 | Reply

  2. [...] as described in Higher Dimensional Algebra I. Just like for monoidal categories, there’s a “coherence theorem” that tells us that once we specify a number of relations, all the others we want will follow. [...]

    Pingback by Monoidal Structures on Span 2-Categories II « The Unapologetic Mathematician | October 11, 2007 | Reply

  3. A bit of an issue I’m having with this is arrows from 1\otimes 1 to 1; Mac Lane has a principle that \rho_1=\lambda_1, but people often seem to omit this.

    I can’t see how to get this case of coherence without it, nor can I believe that CWM would have it if it wasn’t needed.

    Comment by Avery Andrews | December 17, 2008 | Reply

  4. Avery, perhaps Mac Lane threw that one in because it’s a slightly fiddly pain in the neck to prove from scratch. But, it’s not needed; it follows from the other axioms. This was first proven by G.M. Kelly in 1964. In fact, the original 1963 list had even more axioms, which Kelly whittled down to just the two (the pentagon and the unit triangle).

    Comment by Todd Trimble | December 17, 2008 | Reply

  5. Fiddly indeed! I’m surprised that more textbooks (any, afaik) don’t use Kelly’s proofs as the basis of an exercise series, they seem to be a nice demo of uses for naturality.

    Comment by Avery Andrews | December 18, 2008 | Reply

  6. Yes. They (and their higher-dimensional analogues) are also interesting from a geometric/combinatorial standpoint, just as the associahedra are interesting.

    Comment by Todd Trimble | December 18, 2008 | Reply

  7. So now I’m trying to get this out of John’s proof above, and not succeeding, due to the fact that par 3 after the first diagram takes us to the case of no units, but with \lambda_1=\rho_1, that’s not what we’ve got.

    Comment by Avery Andrews | December 18, 2008 | Reply

  8. Mac Lane does give a fairly detailed proof in CWM (as you surely know already). There are other slick ways of proving this theorem; one is given by Joyal and Street, either in their paper Braided Tensor Categories or in The Geometry of Tensor Calculus, I [sorry, can't remember which, but I think the first]. There’s a similar theorem for bicategories (in one formulation, every bicategory is biequivalent to a 2-category) which can be proven by appeal to a bicategorical Yoneda lemma (see Gordon-Power-Street, Coherence for Tricategories, page 3).

    What John proves above can be interpreted as the statement that the 2-skeleton of the associahedron in any dimension has trivial fundamental group.

    Comment by Todd Trimble | December 19, 2008 | Reply

  9. The CWM proof assumes $lambda \lambda_1=\rho_1$, so prepending Kelly to that & presumably to John’s would fix everything up. I find it rather intruiging that such a simple-looking factoid has such a convoluted proof.

    Comment by Avery Andrews | December 19, 2008 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 386 other followers

%d bloggers like this: