The Unapologetic Mathematician

Mathematics for the interested outsider

Diagrammatics for Monoid Objects

I don’t know about you, but all this algebraic notation starts to blur together. Wouldn’t it be nice if we could just draw pictures?

Well luckily for use we can! Just like we had diagrams for braided categories, categories with duals, and braided categories with duals, we have certain diagrammatics to help us talk about monoid objects.

First off, we think of our generating object as a point on a line. As we tensor copies of this object together, we just add more points. Then our morphisms will be diagrams in the plane. At the bottom of the diagram is the incoming object — a bunch of marked points — and at the top is the outgoing object — another bunch of marked points. In between, we have morphisms we can build from the two basic pieces we added: multiplication and unit.

Multiplication and Unit Diagrams

See? For multiplication, two points come in. They move together and multiply, leaving one point to go out. For the unit, a point comes “out of nowhere” to leave the diagram.

As before, we set two diagrams side-by-side for the monoidal product and stack them top-to-bottom for composition. Now, what do those associativity and identity relations look like?

Associativity and Identity Diagrams

Neat! Associativity just means we can pull the branch in the middle to either side of the threefold multiplication, while identity means we can absorb a dangling free end.

I haven’t bothered to render a diagram for symmetry, but we can draw it by just having lines cross through each other. The naturality of the symmetry means that we can pull any morphism from one side of a crossing line to the other.

And now what about comonoid objects? We’ve got diagrams to talk about them too!

Comultiplication and Counit Diagrams

Here’s a comultiplication and a counit. We just flip the multiplication and unit upside-down to dualize them. And we do the same thing for the coassociativity and coidentity relations.

Coassociativity and Coidentity Diagrams

The one thing we have to take careful note of here is that everything in sight is strict. These diagrams don’t make any distinction between (M\otimes M)\otimes M and M\otimes(M\otimes M); or between M, \mathbf{1}\otimes M, and M\otimes\mathbf{1}.

July 25, 2007 Posted by | Category theory | 2 Comments

Examples of Monoid Objects

It’s all well and good to define monoid objects, but it’s better to see that they subsume a lot of useful concepts. The basic case is, of course, that a monoid object in \mathbf{Set} is a monoid.

Another example we’ve seen already is that a ring with unit is a monoid object in \mathbf{Ab} — the category of abelian groups with the tensor product of abelian groups as the monoidal structure. Similarly, given a commutative ring K, a monoid object in the category K\mathbf{-mod} with tensor product of K-modules as its monoidal structure is a K-algebra with unit. For extra credit, how would we get rings and K-algebras without units?

Here’s one we haven’t seen (and which I’ll talk more about later): given any category \mathcal{C}, the category of “endofunctors” \mathcal{C}^\mathcal{C} has a monoidal structure given by composition of functors from \mathcal{C} to itself. This is the one I was thinking of that doesn’t have a symmetry, by the way. A monoid object in this category consists of a functor T:\mathcal{C}\rightarrow\mathcal{C} along with natural transformations \mu:T\circ T\rightarrow T and \eta:1_\mathcal{C}\rightarrow T. These turn out to be all sorts of useful in homology theory, and also in theoretical computer science. In fact, the programming language Haskell makes extensive and explicit use of them.

And now for a really interesting class of examples. Let’s say we start with a monoidal category \mathcal{C} with monoidal structure \otimes. We immediately get a monoidal structure \otimes^\mathrm{op} on the opposite category \mathcal{C}^\mathrm{op}. Just define A\otimes^\mathrm{op}B=A\otimes B for objects. For morphisms we take f:A\rightarrow C and g:B\rightarrow D (which are in \hom_{\mathcal{C}^\mathrm{op}}(C,A) and \hom_{\mathcal{C}^\mathrm{op}}(D,B), respectively), and define f\otimes^\mathrm{op}g=f\otimes g, which is in \hom_{\mathcal{C}^\mathrm{op}}(C\otimes^\mathrm{op}D,A\otimes^\mathrm{op}B).

So what’s a monoid object in \mathcal{C}^\mathrm{op}? It’s a contravariant functor from \mathrm{Th}(\mathbf{Mon}) to \mathcal{C}. Equivalently, we can write it as a covariant functor from \mathrm{Th}(\mathbf{Mon})^\mathrm{op} to \mathcal{C}. It will be easier to just write down explicitly what this opposite category is.

So we need to take \mathrm{Th}(\mathbf{Mon}) and reverse all the arrows. It’s enough to just reverse the arrows we threw in to generate the category, and their composites will be reversed as well. We’ll also have to dualize the relations we imposed to make everything work out right. So we’ll have an arrow \Delta:M\rightarrow M\otimes M called comultiplication and another arrow \epsilon:M\otimes\mathbf{1} called the counit. These we require to satisfy the coassociative condition (\Delta\otimes1_M)\circ\Delta=(1_M\otimes\Delta)\circ\Delta and the left and right coidentity conditions (\epsilon\otimes1_M)\circ\Delta=1_M=(1_M\otimes\epsilon)\circ\Delta.

Now a functor from this category to another monoidal category picks out an object C\in\mathcal{C} and arrows (reusing the names) \epsilon:C\rightarrow\mathbf{1} and \Delta:C\rightarrow C\otimes C satisfying coassociativity and coidentity conditions. We call such an object with extra structure a “comonoid object” in \mathcal{C}. In \mathbf{Set} we call them “comonoids”. In \mathbf{Ab} we call them “corings” (with counit), in K\mathbf{-mod} we call them “coalgebras” (with counit), and in \mathcal{C}^\mathcal{C} we call them “comonads”. In general, we call this new model category \mathrm{Th}(\mathbf{CoMon}) — the “theory of comonoids”.

July 24, 2007 Posted by | Category theory | 4 Comments

Monoid Objects

Now it’s time to start getting into the fun things we can do with monoidal categories. For my first trick, I’m going to build a neat monoidal category \mathcal{M} and show you what we can do with it.

Any monoidal category has an “identity” object \mathbf{1}, so to make it a bit more interesting let’s throw in a single non-identity object M. Then we get for free all the monoidal products built with M and \mathbf{1}. Let’s make our lives easier by saying our category is strict. Then all our objects look like M^{\otimes n} — the monoidal product of n copies of M. We can see that \mathbf{1}=M^{\otimes0}, and that M^{\otimes n_1}\otimes M^{\otimes n_2}=M^{\otimes(n_1+n_2)}.

This is all well and good, but we still don’t really have much going on here. All the morphisms in sight are identities. We don’t even have associators or unit isomorphisms because our category is strict. So let’s throw in a couple morphisms, and of course all the other ones we can build from them.

First let’s make our category symmetric. That is, we’ll add a “twist” \tau:M\otimes M\rightarrow M\otimes M that swaps the copies of M. We’ll insist that it satisfy \tau^2=1_{M\otimes M}. We can then build a braiding \beta_{M^{\otimes n_1},M^{\otimes n_2}}:M^{\otimes n_1}\otimes M^{\otimes n_2} by swapping the copies of M one at a time. This seems a little silly at first glance. If M had any additional structure — if it was a set, for instance — this would be clearly useful. As it stands, though, the use isn’t apparent. Don’t worry, we’ll get to it.

Next, let’s add a morphism e:\mathbf{1}\rightarrow M. From this we can get a bunch of other morphisms. For example, 1_M\otimes e:M\otimes\mathbf{1}\rightarrow M\otimes M or e\otimes1_M:\mathbf{1}\otimes M\rightarrow M\otimes M. We can use this one to increase the number of copies of M in a product in many different ways, depending on where we stick the new copy of M.

But we could also add a new copy of M in one place and use the symmetric structure to move it to a different place. For example, instead of adding a copy on the right with 1_M\otimes e, we could instead use \tau\circ(e\otimes1_M) to add a copy on the left and then swap the two. Notice also that 1_M=\beta_{\mathbf{1},M} and \tau=\beta_{M,M}, which means that these two morphisms are (1_M\otimes e)\circ\beta_{\mathbf{1},M} and \beta_{M,M}\circ(e\otimes1_M). The naturality of \beta says that these two are really the same. So, adding a new copy of M and then moving it around immediately to another position is the same as just adding it in the new position right away.

Now let’s add a way to reduce the number of copies. We’ll use a morphism m:M\otimes M\rightarrow M. Of course, we get for free such compositions as (m\otimes1_M)\circ(1_M\otimes\tau):M^{\otimes3}\rightarrow M^{\otimes2} and m\circ(e\otimes1_M):M\rightarrow M. There will be some equalities arising from the naturality of \beta, but nothing too important yet.

So let’s throw in a few more equalities. Let’s say that m\circ(m\otimes1_M)=m\circ(1_M\otimes m) and that m\circ(e\otimes1_M)=1_M=m\circ(1_M\otimes e). And of course there are other equalities we can build from these. The whole thing should start looking a bit familiar by this point.

Okay, so we’ve got ourselves a strict monoidal category \mathcal{M} with a bunch of objects and a few morphisms satisfying some equations. So what? Well, let’s start looking at symmetric monoidal functors from \mathcal{M} into other symmetric monoidal categories.

The first monoidal category we’ll look at is \mathbf{Set}, which uses the cartesian product as its monoidal structure. What does a monoidal functor F:\mathcal{M}\rightarrow\mathbf{Set} look like? Well, F(M) is some set X, and by monoidality we see that F(M^{\otimes n})=X^{\times n} — the cartesian product of n copies of X. In particular, F(\mathbf{1})=\{*\}: a set with a single element.

The symmetry for \mathbf{Set} is the natural isomorphism \beta_{A,B}:A\times B\rightarrow B\times A defined by \beta_{A,B}: (a,b)\mapsto(b,a). In particular, we get F(\tau)=\beta_{X,X}: (x_1,x_2)\mapsto(x_2,x_1).

The morphism e:\mathbf{1}\rightarrow M now becomes F(e)=1:\{*\}\rightarrow X, which picks out a particular point of X. Let’s call this point 1, just like the function that picks it out.

The morphism m:M\otimes M\rightarrow M is now a function F(m)=\mu:X\otimes X\rightarrow X. The equations that we imposed in \mathcal{M} must still apply here: \mu\circ(\mu\times1_X)=\mu\circ(1_X\times\mu) and \mu\circ(1\otimes1_X)=1_X=\mu\circ(1_X\otimes1). Since we’re in the category of sets, let’s just write these all out as functions and see what they do to particular elements.

The first equation is between two functions with source X\times X\times X, so let’s pick an arbitary element (x_1,x_2,x_3) to follow. The left side of the equation sends this to \mu(\mu(x_1,x_2),x_3), while the right sends it to \mu(x_1,\mu(x_2,x_3)). The equation now reads \mu(\mu(x_1,x_2),x_3)=\mu(x_1,\mu(x_2,x_3)). But that’s just the associative law for a composition! The second equation is between three functions that all have source X. Starting with an arbitrary element x we read off the equation \mu(1,x)=x=\mu(x,1). And that’s the left and right unit law for a composition!

So what we see here is that X=F(M) gets the structure of a monoid. And given any monoid X we can construct such a symmetric monoidal functor with F(M)=X and sending m and e to the multiplication and identity functions.

Can we do better? Sure we can. Let’s say we’ve got a homomorphism between two monoids f:X_1\rightarrow X_2. We can consider this to be a function between their underlying sets. Immediately we get f^{\times n}:X_1^{\times n}\rightarrow X_2^{\times n} as well, applying f to each entry of the product. This is clearly symmetric. Saying that f preserves the multiplication of these monoids is just the same as saying that f\circ F_1(m)=F_2(m)\circ(f\times f), which is the naturality square for m. Similarly, preserving the identities is the same as making the naturality square for e commute. So a monoid homomorphism is the same as a natural transformation between these functors!

Let’s back up a bit and give our toy category a better name. Let’s call it \mathrm{Th}(\mathbf{Mon}) — the “theory of monoids”. What we’ve just seen is that our familiar category \mathbf{Mon} of monoids is “really” the category \mathbf{Set}^{\mathrm{Th}(\mathbf{Mon})} of symmetric monoidal functors from the “theory of monoids” to sets. We now slightly shift our terminology and instead of calling such a set-with-extra-structure a “monoid”, we call it a “monoid object in \mathbf{Set}“.

And now the road is clear to generalize. Given any symmetric monoidal category \mathcal{C} we can take the category \mathcal{C}^{\mathrm{Th}(\mathbf{Mon})} of “monoid objects in \mathcal{C}“.

[UPDATE]: On reflection, the symmetric property isn’t really essential. That is, we can just consider the category of monoidal functors from \mathrm{Th}(\mathbf{Mon}) to \mathcal{C}. In fact, there’s one example I’ll be getting to that doesn’t have a symmetry. In general, though, when the target category has a symmetry we’ll usually ask that our functors preserve that structure as well.

[UPDATE]: You know what? Scrap that whole symmetry bit altogether. Sometimes the target category will have symmetry and sometimes that will be helpful, but it’s just not worth it in the general theory. I’m almost sorry I brought it up in the first place.

July 23, 2007 Posted by | Category theory | 13 Comments

Adjoints Preserve Limits

We can easily see that limits commute with each other, as do colimits. If we have a functor F:\mathcal{J}_1\times\mathcal{J}_2\rightarrow\mathcal{C}, then we can take the limit \varprojlim_{\mathcal{J}_1\times\mathcal{J}_2}F either all at once, or one variable at a time: \varprojlim_{\mathcal{J}_1}\varprojlim_{\mathcal{J}_2}F=\varprojlim_{\mathcal{J}_2}\varprojlim_{\mathcal{J}_1}F. That is, if the category \mathcal{C} has \mathcal{J}-limits, then the functor \varprojlim_{J} preserves all other limits.

But now we know that limit functors are right adjoints. And it turns out that any functor which has a left adjoint (and thus is a right adjoint) preserves all limits. Dually, any functor which has a right adjoint (and thus is a left adjoint) preserves all colimits.

First we need to note that we can compose adjunctions. That is, if we have adjunctions F_1\dashv F_2:\mathcal{C}\rightarrow\mathcal{D} and G_1\dashv G_2:\mathcal{D}\rightarrow\mathcal{E} then we can put them together to get an adjunction G_1\circ F_1\dashv F_2\circ G_2:\mathcal{C}\rightarrow\mathcal{E}. Indeed, we have
\hom_\mathcal{E}(G_1(F_1(C)),E)\cong\hom_\mathcal{D}(F_1(C),G_2(E))\cong\hom_\mathcal{C}(C,F_2(G_2(E)))

We also need to note that adjoints are unique up to natural isomorphism. That is, if F\dashv G_1:\mathcal{C}\rightarrow\mathcal{D} and F\dashv G_2:\mathcal{C}\rightarrow\mathcal{D} then there is a natural isomorphism G_1\cong G_2. This is essentially because adjunctions are determined by universal arrows, and universal arrows are unique up to isomorphism.

Okay, now we can get to work. We start with an adjunction F\dashv G:\mathcal{C}\rightarrow\mathcal{D}. Given another (small) category \mathcal{J} we can build the functor categories \mathcal{C}^\mathcal{J} and \mathcal{D}^\mathcal{J}. It turns out we get an adjunction here too. Define F^\mathcal{J}(S)=F\circ S for each functor S:\mathcal{J}\rightarrow\mathcal{C}. The unit \eta:1_\mathcal{C}\rightarrow G\circ F induces a unit \eta^\mathcal{J}_S=\eta\circ1_S:S\rightarrow G\circ F\circ S. We can similarly define G^\mathcal{J} and \epsilon^\mathcal{J}, and show that they determine an adjunction F^\mathcal{J}\dashv G^\mathcal{J}:\mathcal{C}^\mathcal{J}\rightarrow\mathcal{D}^\mathcal{J}

Now let’s say that \mathcal{C} and \mathcal{D} both have \mathcal{J}-limits. Then we have an adjunction \Delta\dashv\varprojlim_\mathcal{J}:\mathcal{C}\rightarrow\mathcal{C}^\mathcal{J} and a similar one for \mathcal{D}. We can thus form the composite adjunctions
F^\mathcal{J}\circ\Delta\dashv\varprojlim_\mathcal{J}\circ G^\mathcal{J}:\mathcal{C}\rightarrow\mathcal{D}^\mathcal{J}
\Delta\circ F\dashv G\circ\varprojlim_\mathcal{J}:\mathcal{C}\rightarrow\mathcal{D}^\mathcal{J}

So what is F^\mathcal{J}(\Delta(C))? Well, \Delta(C) is the functor that sends every object of \mathcal{J} to C and every morphism to 1_C. Then composing this with F gives the functor that sends every object of \mathcal{J} to F(C) and every morphism to 1_{F(C)}. That is, we get \Delta(F(C)). So F^\mathcal{J}\circ\Delta=\Delta\circ F. But these are the two left adjoints listed above. Thus the two right adjoints listed above are both right adjoint to the same functor, and therefore must be naturally isomorphic! We have \varprojlim_\mathcal{J}G\circ T\cong G(\varprojlim_\mathcal{J}T) for every functor T:\mathcal{J}\rightarrow\mathcal{D}. And thus G preserves \mathcal{J}-limits.

July 21, 2007 Posted by | Category theory | 2 Comments

Limits are Adjoints

When considering limits, we started by talking about the diagonal functor \Delta:\mathcal{C}\rightarrow\mathcal{C}^\mathcal{J}. This assigns to an object C\in\mathcal{C} the “constant” functor \Delta(C):\mathcal{J}\rightarrow\mathcal{C} that sends each object of \mathcal{J} to C and each morphism of \mathcal{J} to 1_C.

Then towards the end of our treatment of limits we showed that taking limits is a functor. That is, if each functor F from \mathcal{J} to \mathcal{C} has a limit \varprojlim_\mathcal{J}F, then \varprojlim_\mathcal{J} is a functor from \mathcal{C}^\mathcal{J} to \mathcal{C}. Dually, if every such functor has a colimit \varinjlim_\mathcal{J}F, then \varinjlim_\mathcal{J}:\mathcal{C}^\mathcal{J}\rightarrow\mathcal{C} is also a functor.

And now we can fit these into the language of adjoints: when it exists, the limit functor is right adjoint to the diagonal functor. Dually, the colimit functor is left adjoint to the diagonal functor when it exists. I’ll handle directly the case of colimits, but the limit statements and proofs are straightforward dualizations.

So we definitely have a well-defined functor \Delta:\mathcal{C}\rightarrow\mathcal{C}^\mathcal{J}. By assumption we have for each functor F\in\mathcal{C}^\mathcal{J} an object \varinjlim_\mathcal{J}F\in\mathcal{C}. If we look at the third entry in our list of ways to specify an adjunction, all we need now is a universal arrow \eta_F:F\rightarrow\Delta(\varprojlim_\mathcal{J}F). But this is exactly how we defined limits! Now the machinery we set up yesterday takes over and promotes this collection of universal arrows into the unit of an adjunction \varinjlim_\mathcal{J}\dashv\Delta:\mathcal{C}^\mathcal{J}\rightarrow\mathcal{C}.

For thoroughness’ sake: the unit of this adjunction \eta_F:F\rightarrow\Delta(\varinjlim_\mathcal{J}F) is the colimiting cocone, considered as a natural transformation from F to the constant functor on the colimiting object. The counit of this adjunction \epsilon_C:\varinjlim_\mathcal{J}\Delta(C)\rightarrow C is just the identity arrow on C because the colimit of the constant functor is just the constant value. The “quasi-inverse” conditions state that \Delta(1_C)\circ\eta_{\Delta(C)} is the identity natural isomorphism on \Delta, and that 1_{\varinjlim_\mathcal{J}F}\circ\varinjlim_\mathcal{J}\eta_F is the identity natural isomorphism on \varinjlim_\mathcal{J}, both of which are readily checked.

And our original definition of an adjoint here reads that \hom_\mathcal{C}(\varinjlim_\mathcal{J}F,C)\cong\hom_{\mathcal{C}^\mathcal{J}}(F,\Delta(C)). That is, for each cocone to C on F (one of the natural transformations on the right) there is a unique arrow from the colimiting object of F to C.

July 20, 2007 Posted by | Category theory | 1 Comment

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 | Category theory | 1 Comment

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 | 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 | 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 | Category theory | 16 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 | Category theory | Leave a Comment

« Previous Entries     Next Entries »

Follow

Get every new post delivered to your Inbox.

Join 216 other followers