The Unapologetic Mathematician

Mathematics for the interested outsider

Adjoints and universality

Now we have the notion of an adjunction, along with its unit and counit. It’s time to start tying them back into universality.

The unit of an adjunction picks out, for each object C, an arrow \eta_C:C\rightarrow G(F(C)). This arrow is an object in the comma category (C\downarrow G). And, amazingly enough, it’s an initial object in that category. Given any other object D\in\mathcal{D} and arrow d:C\rightarrow G(D) we need to find an arrow f:F(C)\rightarrow D in \mathcal{D} so that d=G(f)\circ\eta_C. Since d\in\hom_\mathcal{C}(C,G(D)) the obvious guess is f=\Phi_{C,D}^{-1}(d)=\epsilon_D\circ F(d). Then we can calculate:
G(\epsilon_D\circ F(d))\circ\eta_C=G(\epsilon_D)\circ G(F(d))\circ\eta_C=G(\epsilon_D)\circ\eta_{G(D)}\circ d=d
where the second equality uses the naturality of \eta and the third uses the “quasi-inverse” condition we discussed yesterday.

So, an adjunction means that for each and every object C\in\mathcal{C} the component of the unit \eta_C gives a universal arrow from C to G. Dually, for every object D\in\mathcal{D} the component of the counit \epsilon_D gives a couniversal arrow from F to D.

On the other hand, let’s say we start out with a functor G:\mathcal{D}\rightarrow\mathcal{C} and for each C\in\mathcal{C} an object F_O(C) and an arrow \eta_C:C\rightarrow G(F_O(C)) that is universal from C to G. Then given an arrow c:C\rightarrow C' we can build an arrow \eta_{C'}\circ c:C\rightarrow G(F_O(C')). By the universality of \eta_C there is then a unique arrow F_M(c):F_O(C)\rightarrow F_O(C') so that \eta_{C'}\circ c=G(F_M(c))\circ\eta_C. It’s straightforward now to show that F_O and F_M are the object and morphism functions of a functor F:\mathcal{C}\rightarrow\mathcal{D}, and that \eta:1_\mathcal{C}\rightarrow G\circ F is a natural transformation.

Now, say we have functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural transformation \eta:1_\mathcal{C}\rightarrow G\circ F so that each \eta_C:C\rightarrow G(F(C)) is universal from C to G. Given an arrow f:C\rightarrow G(D), there is (by universality of \eta_C) a unique arrow g:F(C)\rightarrow D so that f=G(g)\circ\eta_C. This sets up a bijection \Phi_{C,D}:\hom_\mathcal{D}(F(C),D)\rightarrow\hom_\mathcal{C}(C,G(D)) defined by \Phi_{C,D}(g)=G(g)\circ\eta_C. This construction is natural in C because \eta_C is, and it’s natural in D because G is a functor. And so this data is enough to define an adjunction F\dashv G:\mathcal{C}\rightarrow\mathcal{D}.

Dually, we can start with a functor F:\mathcal{C}\rightarrow\mathcal{D} and for each D\in\mathcal{D} an object G_O(D)\in\mathcal{C} and an arrow \epsilon_D:F(G_O(D))\rightarrow D universal from F to D. Then we can build G_O up into a functor G:\mathcal{D}\rightarrow\mathcal{C} and \epsilon up into a natural transformation with each component a couniversal arrow. And this is enough to define an adjunction F\dashv G:\mathcal{C}\rightarrow\mathcal{D}.

And, of course, we know that giving a universal arrow \eta_C from C to G is equivalent to giving a representation of the functor \hom_\mathcal{C}(C,G(\underline{\hphantom{X}})):\mathcal{D}\rightarrow\mathbf{Set}, and dually.

So we have quite a long list of ways to specify an adjunction

  • Functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural isomorphism \Phi_{C,D}:\hom_\mathcal{D}(F(C),D)\rightarrow\hom_\mathcal{C}(C,G(D))
  • Functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and natural transformations \eta_C:C\rightarrow G(F(C)) and \epsilon_D:F(G(D))\rightarrow D satisfying (1_G\circ\epsilon)\cdot(\eta\circ1_G)=1_G and (\epsilon\circ1_F)\cdot(1_F\circ\eta)=1_F
  • A functor G:\mathcal{D}\rightarrow\mathcal{C} and for each C\in\mathcal{C} an object F_O(C)\in\mathcal{D} and a universal arrow \eta_C:C\rightarrow G(F_O(C))
  • A functor F:\mathcal{C}\rightarrow\mathcal{D} and for each D\in\mathcal{D} an object G_O(D)\in\mathcal{C} and a couniversal arrow \epsilon_D:F(G_O(D))\rightarrow D
  • A functor G:\mathcal{D}\rightarrow\mathcal{C} and for each C\in\mathcal{C} a representation \phi_C of the functor \hom_\mathcal{C}(C,G(\underline{\hphantom{X}})):\mathcal{D}\rightarrow\mathbf{Set}
  • A functor F:\mathcal{C}\rightarrow\mathcal{D} and for each D\in\mathcal{D} a representation \phi_D of the functor \hom_\mathcal{D}(F(\underline{\hphantom{X}}),D):\mathcal{C}\rightarrow\mathbf{Set}
  • Functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural transformation \eta:1_\mathcal{C}\rightarrow G\circ F so that each component \eta_C is universal from C to G
  • Functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural transformation \epsilon:F\circ G\rightarrow1_\mathcal{D} so that each component \epsilon_D is universal from F to D

July 19, 2007 Posted by John Armstrong | Category theory | | No Comments Yet

More on units and counits

Last time we took an adjunction and came up with two natural transformations, weakened versions of the natural isomorphisms defining an equivalence. Today we’ll see how to go back the other way.

So let’s say we have an adjunction F\dashv G:\mathcal{C}\rightarrow\mathcal{D} given by natural isomorphism \Phi_{C,D}:\hom_\mathcal{D}(F(C),D)\rightarrow\hom_\mathcal{C}(C,G(D)). Remember that we defined the unit and counit by \eta_C:\Phi_{C,F(C)}(1_{F(C)}) and \epsilon_D=\Phi_{G(D),D}^{-1}(1_{G(D)}). We can take either one of these and reverse-engineer it. For instance, given an arrow f:F(C)\rightarrow D in \mathcal{D} we can calculate
\Phi_{C,D}(f)=\Phi_{C,D}(f\circ1_{F(C)})=G(f)\circ\Phi_{C,F(C)}(1_{F(C)})=G(f)\circ\eta_C
so once we know the unit of the adjunction we can calculate \Phi from it. Notice how we use the naturality of \Phi in the second equality.

Dually, we can determine \Phi^{-1} in terms of the counit. Given g:C\rightarrow G(D) in \mathcal{C}, we calculate:
\Phi_{C,D}^{-1}(g)=\Phi_{C,D}^{-1}(1_{G(D)}\circ g)=\Phi_{G(D),D}^{-1}(1_{G(D)})\circ F(g)=\epsilon_D\circ F(g)
so we can also determine the natural isomorphism of hom-sets in terms of the counit.

Of course, since we can determine the same isomorphism (technically the isomorphism and its inverse) from either the unit or the counit, they must be related. So what do these equations really tell us?

For this we have to go back to the way we compose natural transformations. The obvious way is where we have natural transformations \phi:F\rightarrow G and \theta:G\rightarrow H between three functors from \mathcal{C} to \mathcal{D}. We put them together to get (\theta\cdot\phi)_C=\theta_C\circ\phi_C:F\rightarrow H.

Less obviously, we can consider functors F_1 and F_2 from \mathcal{C} to \mathcal{D}, functors G_1 and G_2 from \mathcal{D} to \mathcal{E}, and natural transformations \phi:F_1\rightarrow F_2 and \theta:G_1\rightarrow G_2. We can put these together to get \theta\circ\phi:F_1\circ G_1\rightarrow F_2\circ G_2, defined by \theta_{F_2(C)}\circ G_1(\phi_C) or G_2(\phi_C)\circ\theta_{F_1(C)} (exercise: show that these two composites are equal).

Now what we need here is this “horizontal” composite. Let’s go back to the adjunction and take the natural transformations \eta:1_\mathcal{C}\rightarrow G\circ F and 1_G:G\rightarrow G. The components of their horizontal composite \eta\circ1_G:G\rightarrow G\circ F\circ G is then given by \eta_{G(D)}. Similarly, if we take the natural transformations 1_G and \epsilon:F\circ G\rightarrow1_\mathcal{D}, their horizontal composite has components given by G(\epsilon_D). Now the “vertical” composite of these two (1_G\circ\epsilon)\cdot(\eta\circ1_G) has components G(\epsilon_D)\circ\eta_{G(D)}. And the above formula for the adjunction isomorphism in terms of the unit tells us that this is \Phi_{G(D),D}(\epsilon_D)=\Phi_{G(D),D}(\Phi_{G(D),D}^{-1}(1_{G(D)}))=1_{G(D)}.

To put it at a bit of a higher level, if we start with the functor G, use the unit to turn it into the functor G\circ F\circ G, then use the counit to move back to G, the composite natural transformation is just the identity transformation on G. Similarly, we can show that the composite (\epsilon\circ1_F)\cdot(1_F\circ\eta) taking F to F\circ G\circ F and back to F is the identity transformation on F.

Inherent in this is also the converse statement. If we have natural transformations \eta:1_\mathcal{C}\rightarrow G\circ F and \epsilon:F\circ G\rightarrow1_\mathcal{D} satisfying these two identities, then we can use the above formulae to define a natural isomorphism \phi in terms of \eta and its inverse in terms of \epsilon. Thus an adjunction is determined by a unit and a counit satisfying these “quasi-inverse” relations.

If you’re up to it, try to see where we’ve seen these quasi-inverse relations before in a completely different context. I’ll be coming back to this later.

July 18, 2007 Posted by John Armstrong | Category theory | | 1 Comment

The Unit and Counit of an Adjunction

Let’s say we have an adjunction F\dashv G:\mathcal{C}\rightarrow\mathcal{D}. That is, functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural isomorphism \Phi_{C,D}:\hom_\mathcal{D}(F(C),D)\rightarrow\hom_\mathcal{C}(C,G(D)).

Last time I drew an analogy between equivalences and adjunctions. In the case of an equivalence, we have natural isomorphisms \eta:1_\mathcal{C}\rightarrow G\circ F and \epsilon:F\circ G\rightarrow1_\mathcal{D}. This presentation seems oddly asymmetric, and now we’ll see why by moving these structures to the case of an adjunction.

So let’s set D=F(C') like we did to show that an equivalence is an adjunction. The natural isomorphism is now \Phi_{C,F(C')}:\hom_\mathcal{D}(F(C),F(C'))\rightarrow\hom_\mathcal{C}(C,G(F(C')). Now usually this doesn’t give us much, but there’s one of these hom-sets that we know has a morphism in it: if C'=C then 1_{F(C)}\in\hom_\mathcal{D}(F(C),F(C)). Then \Phi_{C,F(C)}(1_{F(C)}) is an arrow in \mathcal{C} from C to \left[G\circ F\right](C).

We’ll call this arrow \eta_C. Doing this for every object C\in\mathcal{C} gives us all the components of a natural transformation \eta:1_\mathcal{C}\rightarrow G\circ F. For this, we need to show the naturality condition G(F(f))\circ\eta_C=\eta_{C'}\circ f for each arrow f:C\rightarrow C'. This is a straightforward calculation:
G(F(f))\circ\eta_C=G(F(f))\circ\Phi_{C,F(C)}(1_{F(C)})=\Phi_{C,F(C')}(F(f)\circ1_{F(C)})=
\Phi_{C,F(C')}(1_{F(C')}\circ F(f))=\Phi_{C',F(C')}(1_{F(C')})\circ f=\eta_{C'}\circ f
using the definition of \eta_C and the naturality of \Phi.

This natural isomorphism \eta is called the “unit” of the adjunction F\dashv G. Dually we can set C=G(D) and extract an arrow \eta_D=\Phi_{G(D),D}^{-1}(1_{G(D)}) for each object D\in\mathcal{D} and assemble them into a natural transformation \eta:F\circ G\rightarrow1_\mathcal{D} called the “counit”. If both of these natural transformations are natural isomorphisms, then we have an equivalence.

For a particular example, let’s look at this in the case of the free-monoid functor M as the left adjoint to the underlying-set monoid U. The unit will give an arrow \eta_S:S\rightarrow U(M(S)), which here is just the inclusion of the generators (elements of S) as elements of the underlying set of the free monoid. The counit, on the other hand, will give an arrow \epsilon_N:M(U(N))\rightarrow N. That is, we take all elements of the monoid N and use them as generators of a new free monoid — write out “words” where each “letter” is a whole element of N. Then to take such a word and send it to an element of N, we just take all the letters and multiply them together as elements of N. Since we gave a description of \Phi last time for this case, it’s instructive to sit down and work through the definitions of \eta_S=\Phi_{S,M(S)} and \epsilon=\Phi_{U(N),N}^{-1} to show that they do indeed give these arrows.

July 17, 2007 Posted by John Armstrong | Category theory | | 9 Comments

Adjoint functors

Today I return to the discussion of universals, limits, representability, and related topics. The last piece of this puzzle is the notion of an adjunction. I’ll give a definition and examples today and work out properties later.

An adjunction between categories \mathcal{C} and \mathcal{D} consists of a pair of functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} and a natural isomorphism \Phi_{X,Y}:\hom_\mathcal{D}(F(X),Y)\rightarrow\hom_\mathcal{C}(X,G(Y)). Notice that the functors on either side of \Phi go from \mathcal{C}^\mathrm{op}\times\mathcal{D} to \mathbf{Set}, so each component \Phi_{X,Y} is a bijection of sets. We say that F is “left adjoint” to G, and conversely that G is “right adjoint” to F, and we write F\dashv G.

Now, we have been seeing these things all along our trip so far, but without mentioning them as such. For instance, we have all the “free” constructions:

and maybe more that I’ve mentioned, but don’t recall.

These all have a very similar form in their definitions. For instance, the free monoid M(S) on a set S is characterized by the following universal property: every function f from S into the underlying set of a monoid N extends uniquely to a monoid homomorphism \bar{f}:M(S)\rightarrow N. If we write the underlying set of N as U(N), we easily see that U:\mathbf{Mon}\rightarrow\mathbf{Set} is a functor. The condition then is that every element of the hom-set \hom_\mathbf{Set}(S,U(N)) corresponds to exactly one element of the hom-set \hom_\mathbf{Mon}(M(S),N), and every monoid homomorphism restricts to a function on S. That is, for every set S and monoid N we have an isomorphism of sets \hom_\mathbf{Mon}(M(S),N)\cong\hom_\mathbf{Set}(S,U(N)).

Now, given a function from a set S_1 to a set S_2 we can consider S_2 to be a subset of the free monoid on itself, giving a function f:S_1\rightarrow U(M(S_2)). This extends to a unique monoid homomorphism M(f):M(S_1)\rightarrow M(S_2). This construction preserves identities and compositions, making M into a functor from \mathbf{Set} to \mathbf{Mon}.

If we have a function f:S_1\rightarrow S_2 and a monoid homomorphism m:N_1\rightarrow N_2 then we can build functions \hom_\mathbf{Mon}(M(f),m):\hom_\mathbf{Mon}(M(S_2),N_1)\rightarrow\hom_\mathbf{Mon}(M(S_1),N_2) and \hom_\mathbf{Set}(f,U(m)):\hom_\mathbf{Set}(S_2,U(N_1))\rightarrow\hom_\mathbf{Set}(S_1,U(N_2)). The isomorphisms \hom_\mathbf{Mon}(M(S_2),N_1)\cong\hom_\mathbf{Set}(S_2,U(N_1)) and \hom_\mathbf{Mon}(M(S_1),N_2)\cong\hom_\mathbf{Set}(S_1,U(N_2)) commute with these arrows, so they form the components of a natural isomorphism between the two functors. This proves that the free monoid functor M:\mathbf{Set}\rightarrow\mathbf{Mon} is a left adjoint to the forgetful functor U:\mathbf{Mon}\rightarrow\mathbf{Set}.

All the other examples listed above go exactly the same way, giving left adjoints to all the forgetful functors.

As a slightly different example, we have a forgetful functor U:\mathbf{Ab}\rightarrow\mathbf{Grp} that takes an abelian group and “forgets” that it’s abelian, leaving just a group. Conversely, we can take any group G and take the quotient by its commutator subgroup \left[G,G\right] to get an abelian group. This satisfies the property that for any group homomorphism f:G\rightarrow U(A) from G to an abelian group A (considered as just a group) there is a unique homomorphism of abelian groups \bar{f}:G/[G,G]\rightarrow A. Thus it turns out that “abelianization” of a group is left adjoint to the forgetful functor from abelian groups to groups.

There are more explicit examples we’ve seen, but I’ll leave them to illustrate some particular properties of adjoints. Take note, though, that not all adjunctions involve forgetful functors like these examples have.

An adjunction between two categories can be seen as a weaker version of an equivalence. An equivalence given by functors F:\mathcal{C}\rightarrow\mathcal{D} and G:\mathcal{D}\rightarrow\mathcal{C} tells us that both F and G are fully faithful, so \hom_\mathcal{C}(C',C)\cong\hom_\mathcal{D}(F(C'),F(C)). Now let’s put C'=G(D) to find that \hom_\mathcal{C}(G(D),C)\cong\hom_\mathcal{D}(F(G(D)),F(C))\cong\hom_\mathcal{D}(D,F(C)), where the last isomorphism uses the natural isomorphism F\circ G\rightarrow1_\mathcal{D}. So every equivalence is an adjunction.

July 16, 2007 Posted by John Armstrong | Category theory | | 12 Comments

Diagrammatics for braided monoidal categories with duals

I’m exhausted from spending all morning and much of the afternoon purchasing a new (to me) car. As a result, I’ll just forward you to the excellent notes that Miguel Carrión Alvarez took in John Baez’ seminar on quantum gravity back in fall and winter of 2000-1.

Specifically, pay attention to the diagrammatics. He’s talking mostly about finite-dimensional vector spaces over the field of complex numbers, but most everything applies to a general (braided) monoidal category (with duals). Also, he draws his diagrams from top to bottom, while (as I keep reminding you) I write mine from bottom to top to make it easier to read off the algebraic notation.

We’ve already seen some of the basic pieces as braid, Temperley-Lieb, and tangle diagrams, but here each arc in the diagram carries a label from the objects of a category, and usually an arrow. We can move to a dual object by reversing the arrow or changing the label.

Morphisms can be put in boxes, with the incoming object in the bottom and the outgoing one at the top. The naturality for the dual morphisms basically says we can slide a morphism up over a cup or down under a cap to get its dual. Also, often a morphism will have a number of incoming or outgoing strands, which means that the incoming object is the tensor product of the objects on the incoming strands.

A braiding is written as a crossing (lower-left over upper-right), and the inverse of the braiding is written as the other kind of crossing. Naturality means that we can pull a morphism along a strand through a crossing.

There’s a lot more to the notes than just the diagrammatics, though. If you’re up to it, I highly recommend giving it all a look. If not, just look for the pictures and read the sections around them for the explanations. I’ll be back on Monday with more exposition.

July 14, 2007 Posted by John Armstrong | Category theory | | No Comments Yet

Braided Monoidal Categories with Duals

As one last example along these lines, let’s throw all these structures in together. We start with a monoidal category, and we want it to have both a braiding and duals. Naturally, they’ll have to play well together.

Now I’ll want to go back and tweak one of the things I said about duals. I insisted that the duality functor satisfy (M^*)^*\cong M, but we can actually weaken it slightly. What I defined before we can call a “right dual”, since it provides a pairing M\otimes M^*\rightarrow\mathbf{1}. Instead of insisting that (M^*)^*\cong M, we can put in “left duals” by hand. This will be another contravariant functor M\rightarrow {}^*M, and arrows \overline{\epsilon_M}:{}^*M\otimes M\rightarrow\mathbf{1} and \overline{\eta_M}:\mathbf{1}\rightarrow M\otimes{}^*M satisfying the “mirror images” of the identities for \eta and \epsilon.

What does this all have to do with a braiding? Well we can use a braiding to turn a left dual into a right dual and vice versa. Let’s say we’ve got (right) dual maps \eta_M:\mathbf{1}\rightarrow M^*\otimes M and \epsilon_M:M\otimes M^*\rightarrow\mathbf{1}, along with braiding maps \beta_{M,N}:M\otimes N\rightarrow N\otimes M. Now we can define left dual maps by \overline{\eta_M}[\beta_{M,M^*}^{-1}\circ\eta_M]:\mathbf{1}\rightarrow M\otimes M^* and \overline{\epsilon_M}[\epsilon_M\circ\beta_{M^*,M}]:M^*\otimes M\rightarrow\mathbf{1}. This will automatically satisfy the left dual axioms. You can either try to show this now using the algebra or hold off a bit until we have a better tool to attack such identities.

Okay, so a braided monoidal category with duals has a braiding and has right duals. Since we define left duals in terms of these structures they’ll automatically play well together. From these we can further build a morphism for each object called the “balancing”. It’s defined by \theta_M=(1_M\otimes\epsilon_M)\circ(\beta_{M,M}\otimes1_M)\circ(1_M\otimes\overline{\eta_M}). We call an object M “unframed” if \theta_M=1_M.

I know that there’s a lot of stuff here and it’s hard to remember it all. We need a better way to think about these things. Just like we had for braided categories and categories with duals, we have a diagrammatic rendering of the free braided monoidal category with duals on one object.

First I’ll deal with the free braided monoidal category with duals on one self-dual, unframed object. That is, we start with one object and say it’s its own (left and right) dual and for whom the balancing is the identity. Then we build all the other objects as tensor powers of this one. Then we throw in the braiding morphisms and the duality morphisms and insist they satisfy all the relevant relations. And what we get is the category \mathcal{T}ang of tangles. Here’s an example:
Sample Tangle

As usual we read this from bottom to top. Notice that this means we can read off the algebraic notation just by going top to bottom, left to right, to get (\beta_{1,1}\otimes\epsilon_1)\circ(1_1\otimes\beta_1\otimes1_1)\circ(\beta_1\otimes\eta_1):2\rightarrow2. The unframed condition tells us that we can untwist that loop to the right and still have the same tangle.

What if we didn’t ask that our generator be unframed? Then we get the category \mathcal{F}r\mathcal{T}ang of framed tangles, which differs only in that we can’t untwist loops like the one above. It’s like working with knot diagrams where all we can use are Reidemeister moves 2 and 3.

What if our generator is unframed, but isn’t self-dual? Then we get the category \mathcal{OT}ang of oriented tangles. All we do now is label each strand of our tangle diagram with an orientation, like we did in the case of oriented Temperley-Lieb diagrams.

What if our generator is neither unframed nor self-dual? Then we get the category \mathcal{F}r\mathcal{OT}ang of framed, oriented tangles.

Each of these leads to a diagrammatic way of looking at the respective sorts of categories. For example, go back and take the definition of left duals in terms of right duals and write it out as a diagram of framed, oriented tangles. Then write down the condition it must satisfy as an equation between framed oriented tangles. Finally, verify that it satisfies the equation by finding a sequence of Reidemeister moves 2 and 3 from one side to the other (and invoke the definition of right duals at some point).

The category of tangles is very simply described in combinatorial and algebraic terms, but you might not yet have noticed how general it is. To illustrate this, I give with no further comment an example of a tangle from {}0 to {}0:
Tangle from 0 to 0

July 13, 2007 Posted by John Armstrong | Category theory, Knot theory | | 2 Comments

The Temperley-Lieb Category

Okay, after last week’s shake-ups I’m ready to get back into the swing of things. I mentioned yesterday something called the “Temperley-Lieb Category”, and it just so happens we’re right on schedule to explain it properly.

We’ve seen the category of braids and how the braided coherence theorem makes it the “free braided monoidal category on one object”. That is, it has exactly the structure needed for a braided monoidal category — no more, no less — and if we pick any object in another such category \mathcal{C} we get a unique functor from \mathcal{B}raid to \mathcal{C}.

So of course we want the same sort of thing for monoidal categories with duals. We’ll even draw the same sorts of pictures. A point on a horizontal line will be our generating object, but we also need a dual object. So specifically we’ll think of the object as being “going up through the point” and the dual as “going down through the point”. Then we can draw cups and caps to connect an upward line and a downward line and interpret it as a duality map. Notice, though, that we can’t make any curves cross each other because we have no braiding! Here’s an example of such a Temperley-Lieb diagram:
Oriented Temperley-Lieb diagram

Again, we read this from bottom to top, and from left to right. On the bottom line we have a downward line followed by an upward line, which means we start at the object X^*\otimes X. Then we pass through a cap, which corresponds to the transformation \epsilon_{X^*}. Then we go through a cup (\eta_X^*) to get to X\otimes X^*, and another cup to get to X\otimes X^*\otimes X\otimes X^*. A cap in the middle (\epsilon_{X^*}) is followed by a cup (\eta_X), and then another pair of caps (\epsilon_X\otimes\epsilon_X). Then we have a cup \eta_{X^*} and another \eta_X to end up at X\otimes X^*\otimes X\otimes X^*.

We could simplify this a bit by cancelling two cup/cap pairs using the equations we imposed on the natural transformations \eta and \epsilon. In fact, this is probably a much easier way to remember what those equations mean. The equations tell us in algebraic terms that we can cancel off a neighboring cup and cap, while the topology of diagram says that we can straighten out a zig-zag.

Incidentally, one feature that’s missing from this diagram is that it’s entirely possible to have an arc (pointing either way) start at the bottom of the diagram and leave at the top.

Now if we have any category \mathcal{C} with duals and an object C we can build a unique functor from the category \mathcal{OTL} of oriented Temperley-Lieb diagrams to \mathcal{C} sending the upwards-oriented line to the object C. It sends the above diagram (for example) to the morphism

\left[(1_C\otimes\eta_C\otimes1_{C^*})\circ\eta_{C^*}\circ(\epsilon_C\otimes\epsilon_C)\circ(1_C\otimes\eta_C\otimes1_{C^*})\circ(1_C\otimes\epsilon_{C^*}\otimes1_{C^*})\circ(1_C\otimes1_C^*\otimes\eta_{C^*})\circ\eta_{C^*}\circ\epsilon_{C^*}\right]:
C^*\otimes C\rightarrow C\otimes C^*\otimes C\otimes C^*.

Another useful category is the free monoidal category with duals on a single self-dual object. This is the Temperley-Lieb category \mathcal{TL} which looks just the same as \mathcal{OTL} with one crucial difference: since the object X is its own dual, we can’t tell the difference between the two different directions a line could go. Up and down are the same thing. In the algebra this might seem a little odd, but in the diagram all it means is we get to drop the little arrows that tell us which way to go.

And now if we have any category \mathcal{C} with duals and any self-dual object C=C^* we have a unique functor from \mathcal{TL} to \mathcal{C} sending the strand to \mathcal{C}. This is how Temperley-Lieb diagrams are turned into (categorified) \mathfrak{sl}_2 representations in Khovanov homology.

July 12, 2007 Posted by John Armstrong | Category theory, Knot theory | | 7 Comments

Categories with Duals

Now we’ve got monoidal categories to categorify the notion of a monoid, we should consider what the proper analogue of an inverse is. What we’ll do is define a “dual object”, which is sort of halfway a left inverse and halfway a right inverse.

So, we say a monoidal category \mathcal{M} “has duals” if for every object M there is a “dual object” M^* and natural transformations \eta_M:\mathbf{1}\rightarrow M^*\otimes M and \epsilon_M:M\otimes M^*\rightarrow\mathbf{1}. We do not ask that these be isomorphisms, since for the best examples they’re actually not.

Instead we ask that the transformations be compatible in the sense that the following equations hold:
\lambda_M\circ(\epsilon_M\otimes1_M)\circ\alpha_{M,M^*,M}^{-1}\circ(1_M\otimes\eta_M)\circ\rho_M^{-1}=1_M
\rho_{M^*}\circ(1_{M^*}\otimes\epsilon_M)\circ\alpha_{M^*,M,M^*}\circ(\eta_M\otimes1_{M^*})\circ\lambda_M^{-1}=1_{M^*}
The first one means (reading right to left) that if we create a copy of the identity on the right with \rho^{-1}, then hit it with \eta to create M^*\otimes M, then associate, then hit the M\otimes M^* on the left with \epsilon to get the identity, then remove it with \lambda, it’s just the same as doing nothing at all! And there’s a similar interpretation of the other equation. I can hear your furiously scratching your heads and saying “huh?” right now, but I’ll come back to this with another viewpoint later.

Anyhow, we also want this duality to be a functor — a contravariant functor even — which you should have guessed when I called \eta and \epsilon natural transformations. So we need for every f:M\rightarrow N and arrow f^*:N^*\rightarrow M^* so that (f\circ g)^*=g^*\circ f^* and 1_M^*=1_{M^*}. There are also a naturality conditions for \eta and \epsilon that you should be able to write down if you think of this as a covariant functor (\underline{\hphantom{X}})^*:\mathcal{M}^\mathrm{op}\rightarrow\mathcal{M}. The functor should also be monoidal, in the sense that (M\otimes N)^*\cong N^*\otimes M^* (why this form? write out the condition explicitly).

The motivating example here is the category \mathbf{FinVect}_k of finite-dimensional vector spaces over a field k. Here we know that tensor product over k gives a monoidal structure, and we’ll use the dual module of linear functionals as our functor. Indeed, if we set M^*=\hom_{\mathbf{Vect}_k}(M,k) we clearly have a contravariant functor. We can verify that it’s monoidal in the proper sense, and that the pairing gives a natural transformation M\otimes M^*\rightarrow\mathbf{1}=k. The other natural transformation required is also there, but we don’t yet have the tools needed (unless you’ve taken some linear algebra on your own). Still, you can keep this example in mind.

Now one thing that should be bugging you is that we have arrows M\otimes M^*\rightarrow\mathbf{1} and \mathbf{1}\rightarrow M^*\otimes M\rightarrow, but there are two more it seems we should have. To handle this, we’ll insist that (M^*)^*\cong M — that duality “is its own inverse”, so that we can just use \eta_{M^*} and \epsilon_{M^*} as the other natural transformations we need. This does indeed hold in our motivating example, but we again won’t prove it completely until later.

Note that there’s no reason to assume that \epsilon_{M^*}\circ\eta_M=1_\mathbf{1} or \epsilon_{M}\circ\eta_{M_*}=1_\mathbf{1}, so these still aren’t isomorphisms. If they are, though, then we really do have natural isomorphisms to replace left and right inverse rules in the definition of a group. If you’re feeling up to it, try to state (prove?) a coherence theorem that says what diagrams must commute to ensure they all do.

July 7, 2007 Posted by John Armstrong | Category theory | | 10 Comments

The Braided Coherence Theorem

I find myself up earlier than expected this morning, so I thought I’d bang out the proof I’d promised of the “coherence theorem” for braided monoidal categories.

Recall that we’re considering a braided monoidal category \mathcal{M} with underlying “ordinary category” \mathcal{M}_0 — the same category, just forgetting that it’s braided and monoidal. Then the statement is that the category of braided monoidal functors from \mathcal{B}raid to \mathcal{M} is equivalent to \mathcal{M}_0.

To make our lives a bit easier, we’ll use the strictification theorem to pass from the (weak) monoidal category \mathcal{M} to a monoidally equivalent strict monoidal category \mathcal{S}, with underlying category \mathcal{S}_0. Now the braiding on \mathcal{M} induces (via the equivalence) one on \mathcal{S}. The new statement is that the category of strictly monoidal functors from \mathcal{B}raid to \mathcal{S} is isomorphic to \mathcal{S}_0. Then the result we really want (about \mathcal{M}) will follow.

One direction is easy: we take a functor F and evaluate it at the object 1 to get an object F(1)\in\mathcal{S}_0. A monoidal natural transformation \eta:F\rightarrow G has, in particular, the component \eta_1:F(1)\rightarrow G(1), which makes “evaluate at 1” a functor.

For the other direction, we’ll pick an object S of \mathcal{S}_0 and use it to construct a strictly braided monoidal functor from \mathcal{B}raid to \mathcal{S} that sends 1 to S, and then show that an arrow f:S\rightarrow S' in \mathcal{S}_0 induces a natural transformation between the functors built on S and S'. We’ll see that everything in sight is unique, so this construction actually provides an “on the nose” inverse functor to “evaluate at 1“.

So, we’ve got an object S and we set F_S(1)=S. Then for F to be monoidal we must set F(n)=S^{\otimes n}, since n is 1^{\otimes n} (remember that the “tensor power” is defined just like regular exponentiation: take the tensor product of n copies of the object in question). This completely defines the functor F_S on objects.

Now any morphism in \mathcal{B}raid is an element of some braid group B_n. Let’s look at simply crossing the left strand over the right in B_2: this is \beta_{1,1}, so to have a strictly braided functor we must set F_S(\beta_{1,1})=\beta_{S,S}. In B_n, the crossings of one strand over the one to its right generate the whole group. If we cross strand i over strand i+1 we’ll call the generator \sigma_i. In terms of the category \mathcal{B}raid, we can write \sigma_i as 1_{i-1}\otimes\beta_{1,1}\otimes1_{n-i-1}, so monoidality forces us to set F_S(\sigma_i)=1_{S^{\otimes i-1}}\otimes\beta_{S,S}\otimes1_{S^{\otimes n-i-1}}.

We do have to check that the relations of the braid group are satisfied. But if |i-j|>1 then we have F_S(\sigma_i\sigma_j)=F_S(\sigma_j\sigma_i) because the monoidal product in \mathcal{S} is a functor. And we see that F_S(\sigma_i\sigma_{i+1}\sigma_i)=F_S(\sigma_{i+1}\sigma_i\sigma_{i+1}) because this is exactly an instance of the triangle relation for the braiding on \mathcal{S}!

So once we pick the single object S=F_S(1) everything else about F_S is uniquely determined. If we have an arrow f:S\rightarrow S' then we must set the component \eta_1 of the induced natural transformation to be f:F_S(1)\rightarrow F_{S'}(1). Then monoidality forces \eta_n:F_S(n)\rightarrow F_{S'}(n) to be f^{\otimes n}. The construction is indeed a functor sending \mathcal{S}_0 to the category of strictly monoidal functors from \mathcal{B}raid to \mathcal{S}, and it is clearly inverse to evaluation at 1.

July 6, 2007 Posted by John Armstrong | Category theory, Knot theory | | No Comments Yet

The Category of Braids

Before I jet off for a week of knot homology — where I’m looking forward to seeing Scott Morrison, Jacob Rasmussen, and Ben Webster of the Secret Blogging Seminar — I thought I’d finally start tying in (sorry) this category theory stuff with knot theory.

As I said yesterday, the analogue of commutativity for a monoidal category is called a braiding. The name comes from a deep connection between braided monoidal categories and braid groups. Specifically, there is a (strict) braided monoidal category of braids: \mathcal{B}raid. The objects of this category are the natural numbers, and \hom_{\mathcal{B}raid}(m,n) is the group B_n if m=n and empty otherwise. We think of a braid with n strands as taking a collection of n points and shuffling them around, and we draw a diagram like this:
Sample Braid
As a side note, I always intend diagrams like these to be read from bottom to top, though other authors go the other way.

First, the monoidal structure. We don’t need any of the structural isomorphisms because we’re making a strict monoidal structure, but we do need a bifunctor \underline{\hphantom{X}}\otimes\underline{\hphantom{X}}. On the objects it’s just addition. For morphisms we need a way of taking a braid with m strands and one with n strands and making a braid with m+n strands. We’ll just stand both of our braids next to each other like this:
The Monoidal Product of Braids

Now we need a braiding. That is, for each pair of objects (m,n) we need a morphism (a braid) from m+n to n+m that “commutes” with all the other morphisms. We’ll just pass the m strands from the left over the n strands from the right. Here’s what I mean for m=3 and n=2:
A Sample Braiding

This is natural because if we stick on a braid below the leftmost three strands on the bottom, the Reidemeister moves will let us pull it up and over the other two strands until it’s sitting on top of the three strands at the right on the top. Similarly, a braid can be pulled along the undercrossing strands. Since our monoidal structure is strict, the hexagon identities degenerate into triangles, and the proof is just the following diagram:
The Hexagon Identity for Braids

So we indeed have a strict braided monoidal category. It turns out to be extremely important because of the following theorem of Joyal and Street:

If \mathcal{M} is a braided monoidal category with underlying category \mathcal{M}_0 (forget the monoidal structure and the braiding to just have a regular old category), then the category of braided monoidal functors from \mathcal{B}raid to \mathcal{M} is equivalent to \mathcal{M}_0.

This is sort of like a coherence theorem for braided monoidal categories: for each natural isomorphism built from \alpha, \lambda, \rho, and \beta there is an “underlying braid”, and two such isomorphisms are equal if and only if they have the same underlying braid. I’ll defer the proof of this for now, but you should think about it a bit. The details aren’t that bad, but the basic idea just leaps out at you after a bit.

July 3, 2007 Posted by John Armstrong | Category theory, Knot theory | | 2 Comments

« Previous Entries     Next Entries »