The Unapologetic Mathematician

Mathematics for the interested outsider

Adjoints with parameters

Now that we know how to transform adjoints, we can talk about whole families of adjoints parametrized by some other category. That is, for each object P of the parametrizing category \mathcal{P} we’ll have an adjunction F_P\dashv G_P:\mathcal{C}\rightarrow\mathcal{D}, and for each morphism of \mathcal{P} we’ll have a transformation of the adjunctions.

Let’s actually approach this from a slightly different angle. Say we have a functor F:\mathcal{C}\times\mathcal{P}\rightarrow\mathcal{D}, and that for each P\in\mathcal{P} the functor F(\underline{\hphantom{X}},P):\mathcal{C}\rightarrow\mathcal{D} has a right adjoint G(P,\underline{\hphantom{X}}). Then I claim that there is a unique way to make G into a functor from \mathcal{P}^\mathrm{op}\times\mathcal{D} to \mathcal{C} so that the bijection \phi_{C,P,D}:\hom_\mathcal{D}(F(C,P),D)\rightarrow\hom_\mathcal{C}(C,G(P,D)) is natural in all three variables. Note that G must be contravariant in P here to make the composite functors have the same variance in P.

If we hold P fixed, the bijection is already natural in C and D. Let’s hold C and D fixed and see how to make it natural in P. The components \phi_P:\hom_\mathcal{D}(F(C,P),D)\rightarrow\hom_\mathcal{C}(C,G(P,D)) are already given in the setup, so we can’t change them. What we need are functions \hom_\mathcal{D}(F(1_C,p),1_D):\hom_\mathcal{D}(F(C,P'),D)\rightarrow\hom_\mathcal{D}(F(C,P),D) and \hom_\mathcal{C}(1_C,G(p,1_D)):\hom_\mathcal{C}(C,G(P',D))\rightarrow\hom_\mathcal{C}(C,G(P,D)) for each arrow p:P\rightarrow P'.

For naturality to hold, we need \hom_\mathcal{C}(1_C,G(p,1_D))\circ\phi_{P'}=\phi_P\circ\hom_\mathcal{D}(F(1_C,p),1_D). But from what we saw last time this just means that the pair of natural transformations (F(1_C,p),G(p,1_D)) forms a conjugate pair from F(\underline{\hphantom{X}},P)\dashv G(P,\underline{\hphantom{X}}) to F(\underline{\hphantom{X}},P')\dashv G(P',\underline{\hphantom{X}}). And this lets us define G(p,1_D) uniquely in terms of F(1_C,p), the counit \epsilon' of F(\underline{\hphantom{X}},P')\dashv G(P',\underline{\hphantom{X}}), and the unit \eta of F(\underline{\hphantom{X}},P)\dashv G(P,\underline{\hphantom{X}}) by using the first of the four listed equalities.

From here, it’s straightforward to show that this definition of how G acts on morphisms of \mathcal{P} makes it functorial in both variables, proving the claim. We can also flip back to the original viewpoint to define an adjunction between categories \mathcal{C} and \mathcal{D} parametrized by the category \mathcal{P} as a functor from \mathcal{P} to the category \mathbf{Adj}(\mathcal{C},\mathcal{D}) of adjunctions between those two categories.

July 31, 2007 Posted by John Armstrong | Category theory | | 4 Comments

Transformations of Adjoints

And now we go back to adjoints. Like every other structure out there, we want to come up with some analogue of a homomorphism between two adjunctions. Let’s consider the adjunctions F\dashv G:\mathcal{C}\rightarrow\mathcal{D} and F'\dashv G':\mathcal{C}'\rightarrow\mathcal{D}', and try to find a good notion of a transformation from the first to the second.

We’ll proceed by considering an adjunction to consist of the pair of categories (\mathcal{C},\mathcal{D}) with the functors giving extra structure. Down in the land of groups and rings and such, we’d consider sets with extra structure and functions that preserved that structure. So here, naturally, we want to consider functors which preserve this extra structure. That is, a map of adjunctions consists of a pair of functors K:\mathcal{C}\rightarrow\mathcal{C}' and L:\mathcal{D}\rightarrow\mathcal{D}'. These must preserve the structure in that K\circ G=G'\circ L and L\circ F=F'\circ K.

But hold up a second, we’ve forgotten something else that goes into an adjunction: the isomorphism \phi:\hom_\mathcal{D}(F(C),D)\rightarrow\hom_\mathcal{C}(C,G(D)). Here’s a diagram showing how the map of adjunctions should play nicely with them:
Coherence for Adjunction Map

Equivalently we can specify an adjunction by its unit and counit. In this case the compatibility in question is a pair of equations of natural transformations: 1_K\circ\eta=\eta'\circ1_K and 1_L\circ\epsilon=\epsilon'\circ1_L.

What if we’re looking at two different adjunctions between the same pair of categories? Well then we may as well try to use the appropriate identity functors for K and L. But then it’s sort of silly to insist that G=1_\mathcal{C}\circ G=G'\circ\mathcal{D}=G' on the nose, and similarly for F'. Instead, as we do so often, let’s weaken this equality to just a natural transformation.

We’ll say that a pair of natural transformations \sigma:F\rightarrow F' and \tau:G'\rightarrow G are “conjugate” if \hom_\mathcal{C}(1_C,\tau_D)\circ\phi'_{C,D}=\phi_{C,D}\circ\hom_\mathcal{D}(\sigma_C,1_D). This is equivalent, in terms of the unit and counit, to any one of the following four equalities:

  • \tau=(1_G\circ\epsilon')\cdot(1_G\circ\sigma\circ1_{G'})\cdot(\eta\circ1_{G'})
  • \sigma=(\epsilon\circ1_{F'})\cdot(1_F\circ\tau\circ1_{F'})\cdot(1_F\circ\eta')
  • \epsilon\cdot(1_F\circ\tau)=\epsilon'\cdot(\sigma\circ1_{G'})
  • (1_G\circ\sigma)\cdot\eta=(\tau\circ1_{F'})\cdot\eta'

Now it’s easily verified that given a pair of categories (\mathcal{C},\mathcal{D}) we can build a category whose objects are adjunctions F\dashv G:\mathcal{C}\rightarrow\mathcal{D} and whose morphisms are conjugate pairs of natural transformations, which we write out in full as (\sigma,\tau):(F,G,\phi)\rightarrow(F',G',\phi'):\mathcal{C}\rightarrow\mathcal{D}. We compose conjugate pairs in this category in the obvious way, which we write (\sigma',\tau')\cdot(\sigma,\tau).

On the other hand, if we have a pair (\sigma,\tau):(F,G,\phi)\rightarrow(F',G',\phi'):\mathcal{C}\rightarrow\mathcal{D} and another (\bar{\sigma},\bar{\tau}):(\bar{F},\bar{G},\bar{\phi})\rightarrow(\bar{F}',\bar{G}',\bar{\phi}'):\mathcal{D}\rightarrow\mathcal{E}, then we can form the composite (\bar{\sigma}\circ\sigma,\tau\circ\bar{\tau}):(\bar{F}\circ F,G\circ\bar{G},\bar{\phi}\cdot\phi)\rightarrow(\bar{F}'\circ F',G'\circ\bar{G}',\bar{\phi}'\cdot\phi'):\mathcal{C}\rightarrow\mathcal{E}, which we’ll write as (\bar{\sigma},\bar{\tau})\circ(\sigma,\tau). Notice the similarity of this situation with the two different compositions of natural transformations between functors.

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

Sunday Samples 27

Before New Order was New Order, they were Joy Division. In this incarnation they pioneered the post-punk sound, taking all of the malaise of punk with very little, if any, of the energy. To be honest, I don’t find it to be the most listenable band in the world. But there was surely something there. In the right hands the seeds could come to full flower.

And then along comes Nouvelle Vague, who finally recast Joy Division’s culminating hit as the bossa nova it was always intended to be. The lead off track from their self-titled 2004 debut: “Love Will Tear Us Apart“.
Read more »

July 29, 2007 Posted by John Armstrong | Sunday Samples | | 1 Comment

The Simplicial Category

There’s another approach to the theory of monoids which finds more direct application in topology and homology theory (which, yes, I’ll get to eventually) — the “simplicial category” \mathbf{\Delta}. Really it’s an isomorphic category to \mathrm{Th}(\mathbf{Mon}), but some people think better in these other terms. I personally like the direct focus on the algebra, coupled with the diagrammatics so reminiscent of knot theory, but for thoroughness’ sake I’ll describe the other approach.

Note that the objects of \mathrm{Th}(\mathbf{Mon}) correspond exactly with the natural numbers. Each object is the monoidal product of some number of copies of the generating object M. We’re going to focus here on the model of \mathbb{N} given by the ordinal numbers. That is, the object M^{\otimes n} corresponds to the ordinal number \mathbf{n}, which is a set of n elements with its unique (up to isomorphism) total order. In fact, we’ve been implicitly thinking about an order all along. When we draw our diagrams, the objects consist of a set of marked points along the upper or lower edge of the diagram, which we can read in order from left to right.

Let’s pick a specific representation of each ordinal to be concrete about this. The ordinal \mathbf{n} will be represented by the set of natural numbers from {0} to n-1 with the usual order relation. The monoidal structure will just be addition — \mathbf{m}\otimes\mathbf{n}=\mathbf{m+n}.

The morphisms between ordinals are functions which preserve the order. A function f:X\rightarrow Y between ordinals satisfies this property if whenever i\leq j in X then f(i)\leq f(j) in Y. Note that we can send two different elements of X to the same element of Y, just as long as we don’t pull them past each other.

So what sorts of functions do we have to play with? Well, we have a bunch of functions from \mathbf{n} to \mathbf{n+1} that skip some element of the image. For instance, we could send \mathbf{3} to \mathbf{4} by sending {0} to {0}, skipping 1, sending 1 to 2, and sending 2 to 3. We’ll say \delta^n_i:\mathbf{n}\rightarrow\mathbf{n+1} for the function that skips i in its image. The above function is then \delta^3_1. For a fixed n, the index i can run from {0} to n.

We also have a bunch of functions from \mathbf{n+1} to \mathbf{n} that repeat one element of the image. For example, we could send \mathbf{4} to \mathbf{3} by sending {0} to {0}, 1 and 2 both to 1, and 3 to 2. We’ll say \sigma^n_i:\mathbf{n+1}\rightarrow\mathbf{n} for the function that repeats i in its image. The above function is then \sigma^3_1. Again, for a fixed n, the index i can run from {0} to n-1.

Notice in particular that “skipping” and “repeating” are purely local properties of the function. For instance, \delta^0_0 is the unique function from \mathbf{0} (the empty set) to \mathbf{1}, which clearly skips 0\in\mathbf{1}. Then \delta^n_i can be written as 1_i\otimes\delta^0_0\otimes1_{n-i}, since it leaves the numbers from {0} to i-1 alone, sticks in a new i, and then just nudges over everything from (the old) i to n. Similarly, \sigma^1_0 is the unique function from \mathbf{2} to \mathbf{1} that sends both elements in its domain to 0\in\mathbf{1}. Then all the other \sigma^n_i can be written as 1_i\otimes\sigma^0_0\otimes1_{n-i-1}.

Now every order-preserving function is determined by the set of elements of the range that are actually in the image of the function along with the set of elements of its domain where it does not increase. That is, if we know where it skips and where it repeats, we know the whole function. This tells us that we can write any function as a composition of \delta and \sigma functions. These basic functions satisfy a few identities:

  • If i\leq j then \delta^{n+1}_i\circ\delta^n_j=\delta^{n+1}_{j+1}\circ\delta^n_i.
  • If i\leq j then \sigma^{n-1}_j\circ\sigma^n_i=\sigma^{n-1}_i\circ\sigma^n_{j+1}.
  • If i<j then \sigma^n_j\circ\delta^n_i=\delta^{n-1}_i\circ\sigma^{n-1}_{j-1}.
  • If i=j or i=j+1 then \sigma^n_j\circ\delta^n_i=1.
  • If i>j+1 then \sigma^n_j\circ\delta^n_i=\delta^{n-1}_{i-1}\circ\sigma^{n-1}_j.

We could check all these by hand, and if you like that sort of thing you’re welcome to it. Instead, I’ll just assume we’ve checked the second one for n=2 and the fourth one for n=1.

What’s so special about those conditions? Well, notice that \sigma^1_0:\mathbf{1}\otimes\mathbf{1}\rightarrow\mathbf{1} takes two copies of \mathbf{1} to one copy, and that the second relation becomes the associativity condition for this morphism. Then also \delta^0_0:\mathbf{0}\rightarrow\mathbf{1} takes zero copies to one copy, and the fourth relation becomes the left and right identity conditions. That is, \mathbf{1} with these two morphisms is a monoid object in this category! Now we can verify all the other relations by using our diagrams rather than a lot of messy calculations!

We can also go back the other way, breaking any of our diagrams into basic pieces and translating each piece into one of the \delta or \sigma functions. The category of ordinal numbers not only contains a monoid object, it is actually isomorphic to the “theory of monoids” functor — it contains the “universal” monoid object.

So why bother with this new formulation at all? Well, for one thing it’s always nice to see the same structure instantiated in many different ways. Now we have it built from the ground up as \mathrm{Th}(\mathbf{Mon}), we have it implemented as a subcategory of \mathcal{OTL}, we have it as the category of ordinal numbers, and thus we also have it as a full subcategory of \mathbf{Cat} — the category of all small categories (why?).

There’s another reason, though, which won’t really concern us for a while yet. The morphisms \delta^n_i and \sigma^n_i turn out to be very well-known to topologists as “face” and “degeneracy” maps when working with shapes they call “simplicial complexes”. Not only is this a wonderful oxymoron, it’s the source of the term “simplicial category”. If you know something about topology or homology, you can probably see how these different views start to tie together. If not, don’t worry — I’ll get back to this stuff.

July 28, 2007 Posted by John Armstrong | Category theory | | 5 Comments

Happy Sysadmin Day

Today is the last Friday in July, and thus is System Administrator Appreciation Day.

Thanks to the sysadmins here at WordPress for steering between the Scylla and Charybdis of spammers and Akismet.

Thanks to John Stotler, the math department sysadmin back at Yale, who (unfortunately) will be leaving academic staff work for the real world.

Thanks in advance to the sysadmin at Tulane, who already has my name up on the directory page (but still hasn’t given me my new email address).

If you’re a sysadmin yourself, thanks for doing your job efficiently enough to be able to spend your time reading this.

And to Simon Travaglia… even today I have to fall back on, “Go Cheney Yourself.” You wouldn’t expect anything less.

July 27, 2007 Posted by John Armstrong | Uncategorized | | No Comments Yet

The General Associative Law

For any monoid object we have an associative law for the multiplication: \mu\circ(\mu\otimes1_X)=\mu\circ(1_X\otimes\mu). This basically says that the two different ways of multiplying together three inputs to give one output are the same. Let’s call the result \mu_3:X^{\otimes3}\rightarrow X. In fact, we might go so far as to say \mu_2=\mu:X^{\otimes2}\rightarrow X, \mu_1=1_X:X^{\otimes1}\rightarrow X, and even \mu_0=1:X^{\otimes0}\rightarrow X.

This generalizes a lot. We want to say that there’s a unique way (called \mu_n) to multiply together n inputs. The usual way is to pick some canonical form and show that everything can be reduced to that form. This ends up being a lot like the Coherence Theorem. In fact, if we take a monoid object in the category \mathbf{Cat} of small categories, this is the Coherence Theorem for a strict monoidal category.

But there’s an easier way than walking through that big proof again, and it uses our diagrammatic approach! The first thing we need to realize is that if we can show this rule holds in \mathrm{Th}(\mathbf{Mon}), then it will hold for all monoid objects. That’s why the “theory of monoids” category is so nice — it exactly encodes the structure of a monoid. Anything that is true for all monoids can be proved by just looking at this category and proving it there!

So how do we show that the general associative law holds in \mathrm{Th}(\mathbf{Mon})? Now we need to notice that the functor that makes \downarrow\otimes\uparrow into a monoid object is faithful. That is, if two Temperley-Lieb diagrams in the image are the same, then they must come from the same morphism in \mathrm{Th}(\mathbf{Mon}). But if two diagrams are equivalent they differ by either sliding loops arcs around in the plane — which uses the monoidal structure to pull cups or caps past each other — or by using the zig-zag identities — which encode the left and right identity laws. Thus any equalities that hold in the image of the functor must come from equalities already present in \mathrm{Th}(\mathbf{Mon})!

Now any way of multiplying together n inputs to give one output is a morphism f:M^{\otimes n}\rightarrow M in \mathrm{Th}(\mathbf{Mon}), which will be sent to a diagram F(f):(\downarrow\otimes\uparrow)^{\otimes n}\rightarrow\downarrow\otimes\uparrow in \mathcal{OTL}. It’s not too hard to see that there’s really only one of these diagrams that could be in the image of the functor (up to equivalence of diagrams). So all such multiplications are sent to the same diagram. By the faithfulness above, this means that they were all the same morphism in \mathrm{Th}(\mathbf{Mon}) to begin with, and we’re done.

By the way, you should try playing around with the oriented Temperley-Lieb diagrams to verify the claim I made of uniqueness. Try to work out exactly what diagrams are in \hom_\mathcal{OTL}((\downarrow\otimes\uparrow)^{\otimes n},\downarrow\otimes\uparrow), and then which ones can possibly be in the image of the functor. Playing with the diagrams like this should give you a much better intuition for how they work. If nothing else, drawing a bunch of pictures is a lot more fun than algebra homework from back in school.

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

The Simpsons Movie

Today is the national opening of The Simpsons Movie. Why do I mention this? Well, I always used to like the Simpsons. However, I’ve been of two minds about them ever since they stabbed me in the back by supporting Krusty against me for Springfield’s 24th congressional district seat. It only adds insult to injury that they were joined by Fox News in a vicious smear campaign. So go see it if you want to support that sort of thing.

July 27, 2007 Posted by John Armstrong | Uncategorized | | 2 Comments

More monoid diagrams

Let’s pick up with the diagrams for monoid objects from yesterday. In fact, let’s draw the multiplication and unit diagrams again, but this time let’s make the lines really thick.

Thick Multiplication and Unit Diagram

Now we’re looking at something more like a region of the plane than a curve. We really don’t need all that inside part, so let’s rub it out and just leave the outline. Of course, whenever we go from a blob to its outline we like to remember where the blob was. We do this by marking a direction on the outline so if we walk in that direction the blob would be on our left. Those of you who have taken multivariable calculus probably have a vague recollection of this sort of thing. Don’t worry, though — we’re not doing calculus here.

Okay, now the outline diagrams look like this:

Multiplication and Unit Diagram Outlines

That’s odd. These diagrams look an awful lot like Temperley-Lieb diagrams. And in fact they are! In fact, we get a functor from \mathrm{Th}(\mathbf{Mon}) to \mathcal{OTL} that sends M to \downarrow\otimes\uparrow. That is, a downward-oriented strand next to an upward-oriented strand makes a monoid object on \mathcal{OTL}!

But to be sure of this, we need to check that the associativity and identity relations hold. Here’s associativity:

Associativity T-L Diagram

Well that’s pretty straightforward. It’s just sliding the arcs around in the plane. How about the identity relations?

Identity T-L Diagram

The right identity relation holds because of one of the “zig-zag” relations for duals, and the left identity relation holds because of the other!

Now you should be able to find a comonoid object in \mathcal{OTL} in a very similar way.

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

Self-Referential Aptitude

From God Plays Dice comes the reference to Jim Propp’s Self-Referential Aptitude Test.

I’m linking to the text version of the test available from Propp’s own webspace because the online version checks itself in real-time, so you can get information by seeing what answers get marked wrong as you try them. Also, I’ll warn you that the GPD link contains a solution, but I think it’s less than maximally elegant since it makes an unfounded assumption right off the bat and justifies this assumption by the asserted uniqueness of the solution. As the text version I link to states, it is possible to derive the solution without this assumption — and thus also prove its uniqueness at the same time. Still, a spoiler is a spoiler, so consider yourself fairly warned if you follow that link.

July 25, 2007 Posted by John Armstrong | Uncategorized | | 3 Comments

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 John Armstrong | Category theory | | 2 Comments

« Previous Entries