Tweaky

So I’m up at 03:00 because of an unexpected nap this evening. When I got back from dinner, there was a blackout that included my building. So I slept a bit, then woke up completely a few hours later. Having little else to do, I finally hunkered down on some tweaks to the site.

I moved the tagline a bit and dropped the “rant” phrase. I wanted to change “outraged” to “outspoken”, but even then it wouldn’t really look nice where it now goes. Actually, not only have I not been that outraged, I haven’t been as ranty as I expected I’d be.

Over the last seven months this place has gone in directions I didn’t really expect, and it’s really taken on a life of its own. As for myself — the nominal author — I find myself taken along for the ride. I’m reminded of the apocryphal story about the university that planted grass everywhere, waited to see where it got trampled from people walking across it, then put the sidewalks where people naturally walked. Making predictions is difficult, especially about the future. Unless you’re an anti-blogger, in which case I suppose it’s difficult to predict the past, but that’s a whole ‘nother story.

In the place of the old tagline, I’ve got a more robust (and appropriate) “about” panel. It should give a better explanation of what the hell is going on here, and how to read the page for newcomers.

I haven’t started tearing through and restructuring the “categories” panel in the sidebar, but I’ll hold off on that until I get the cable modem set up here rather than the slow and buggy “Mu-Fi“.

I’m also going to see what I can do about getting a search panel set up, but without paying for the capability to edit my CSS directly (in both money to WordPress and time invested in learning how), I’m not sure what I’ll be able to cobble together.

Finally, inspired by the adventures this evening, I’m starting a more “bloggy” weblog about my life as a Connecticut Yankee in the Lower Garden District. I’m using a phrase I picked up from Nick Maggio (a grad student here) for the title: Yankee Freak-Out. There’s not much there yet, but I’ll start posting tomorrow afternoon.

Assuming, of course, that I’ve got the power.

Enriched Categories

I’d like to move on now to another way of blending various structures. We’ve seen that in certain situations the set of morphisms between two objects in a category naturally has deeper structure itself. For example, the set of homomorphisms between two abelian groups is itself an abelian group, because abelian groups are modules over the commutative ring . More generally, the set of homomorphisms between two -modules naturally has the structure of a -module, and sometimes more.

We need a good way of talking about this sort of thing, where we replace hom sets by “hom objects” in some other category . When this happens we say that our category is “enriched” over . So to rephrase what I said above, the category of -modules is enriched over . Similarly, locally small categories are enriched over .

When we talk about categories — which usually for us means locally small categories — we are implicitly using a number of properties of . In particular, to set up compositions we need to be able to take pairs of morphisms, which the cartesian product handles for us nicely: . We also need to be able to pick out a special morphism in each set of endomorphisms to be the identity, which we can take to be the image of a function from a one-point set to the set of endomorphisms sort of like we did for monoid objects.

For setting up the relations a category must satisfy we need to be able to build triples from pairs in two ways:


We also need to pair a morphism with a (unique) identity morphism:

What are the important properties of the category of sets that make it useful for these purposes? It’s just the fact that equipped with finite products (including a singleton set as terminal object) is a monoidal category! So let’s take a monoidal category — a useful example to have always at hand is — and try to use it for enrichment. As we proceed, we’ll write for the underlying regular category (that is, forget that is monoidal).

So, given such a monoidal category we’ll define a -category to consist of a class of objects , and for each pair of objects a “hom-object” . For each triple of objects there is a composition . For each object there is an “identity”, described by an arrow .

I’ll be spending some time on this, so let’s leave it at the definition for now. Go through and unpack it for the case of an -category, and see what the definition says such a thing should look like.

Correction

Todd Trimble pointed out to me a mistake I made in saying that internalizations commute. I glossed over a number of important subtleties and he set me straight.

Now I’m just getting back from a visit to Bourbon Street, since the real intarwobs and television won’t be reaching my apartment until Wednesday morning. I’ve skimmed his points and they check out, but I invite him to post them here as a comment so I don’t mangle them. Basically, I think I’m “morally” right (and I’m sure I’ve read John Baez saying somthing along these lines), but I’ve messed something up in my presentation as I attempt to get back in the saddle. I’d be glad of any clarification that can be made to see where I’ve gone Pete Tong.

These last two posts are sort of the tail end of internalization anyhow, and I was planning on moving on to something new on Monday. If they’re a little messy, so be it.

Internal Categories

Just like we have monid objects, we can actually define something we could sensibly call a “category object”. In this case, however, it will be a little more accurate to use the term “internal category”.

This is because a (small) category isn’t just a set with extra structure. It’s two sets with extra structure. We have a set of objects, a set of morphisms, a function assigning the identity morphism to each object, functions and assigning the source and target objects to each morphism, and an arrow telling us how to compose certain pairs of morphisms. This involves a “fibered product”, which is just the pullback in . We take the arrows and from to and pull back the square to get the set of all pairs of morphisms so that the source object of one is the target of the other.

Then there are a bunch of relations which hold:

• The source of the identity arrow on an object is the object itself.
• The target of the identity arrow on an object is the object itself.
• The identity arrow on an object acts as a left and right identity for the composition.
• The source of a composition is the source of the second member of the pair.
• The target of a composition is the target of the first member of the pair.
• The composition is associative.

I’ll leave you to write these out purely in terms of the functions , , , and .

Now we can take this whole setup and drop it into any other category, as long as that category has pairwise pullbacks. If does have these pullbacks, then a category internal to (or a “category object”) consists of a pair of objects and four morphisms of , which must satisfy the above relations. Then a category internal to is a small category.

When we’re talking about categorifying something like a group, we want to replace the underlying set of a group with a small category. That is, we want to have a group object in . But we know that internalizations commute, so this is the same thing as a “category object” in groups! That is, instead of looking for a category with a multiplication functor and so on, we can instead look for a pair of groups with source, target, composition, and identity homomorphisms between them.

Internalizations commute

Okay, back in the saddle. We know about monoid objects and group objects, and also the slight variant of abelian group objects. These are functors (preserving some sort of product structure) from the toy categories , , and to our target category , respectively. We could also write out all the properties of (unital) rings in terms of a category — the “theory of rings” — and then use this to define “ring objects

We know, though, that a ring is a monoid object in the category of abelian groups. And the category of abelian groups is the category of abelian group objects in . That is, . And then we get monoid objects (rings) by considering .

But what is a functor from one category into the category of functors from a second category into a third? What is ? This is just a functor from the product category to ! Thus . This should look familiar — it says that (to whatever extent it’s well-defined) the category of categories is a closed category!

Now we also know that the product of two categories is “weakly symmetric” — is equivalent to . And thus the categories of functors from either one of these to a third category are equivalent — . Putting this together with the “currying” above we find that .

So let’s bring this back to internalizations. We find that and are equivalent. A monoid object in is equivalent to an abelian group object in .

And we saw evidence of this before. We’ve taken abelian groups and built free monoid objects on them, and we’ve taken monoids and built free abelian group objects on them. And the rings we get from each case are isomorphic to each other.

This whole setup generalizes. For any two algebraic structures we can describe by “theory of” categories, we can add both structures to an object of a category in either order. the processes of “internalizing” the two structures into the category commute with each other.

Now, for an exercise you can work out the naïve approach mentioned above. Write down the definition of from first principles, just like we did for monoids and groups and such. Then show that the resulting category is equivalent to .

Still busy

I’ve now determined that the distance from here to the department is not as walkable as the same distance would be in New Haven.

As I recover, here is a paper on solving the Travelling Salesman Problem. The authors do so with “white light interferometry”, which sort of makes it a quantum computation algorithm.

The thing they’re overstating is this: this is far from the first reduction of an NP-complete problem to a polynomial-time solution. What they miss out on is that their algorithm is exponential in space — the amount of computational space required goes up exponentially with the size of the problem. Specifically, it takes photons to solve the -city problem. Thus it’s not really that new as far as computational complexity goes. Still.

Travelling

I’ll put the main line of the blog on hiatus for a little bit while I travel, especially since it’s so hard to make links or to type $latex over and over again without a copy/paste function.

I do want to make one note/puzzle in connection with my trip from Washington, D.C. to New Orleans, LA. Earlier today I was driving north, south, and west all at the same time. Where was I?

Group objects

Just like we have monoid objects, we can construct a category called , which encodes the notion of a “group object”.

Groups are a lot like monoids, but we’ll need to be able to do a few more things to describe groups than we needed for monoids. So let’s start with all the same setup as for monoid objects, but let’s make the monoidal structure in our toy category be an actual cartesian structure. That is, we start with an object and we build up all the “powers”, but now we insist that they be built from categorical products rather than just some arbitrary monoidal structure. Then is the categorical product of copies of . Not only does this work like a monoidal structure, but it come equipped with a bunch of extra arrows. For example, there are arrows to “project out” a copy of from a product, and every object has a unique arrow from to the terminal object — the product of zero copies of .

More importantly it has an arrow called the “diagonal” that is defined as the unique arrow satisfying . That is, it makes an “identical copy” of . For instance, in the context of sets this is the function defined by .

Now we do everything like we did for monoid objects. There’s a morphism , and one , and these satisfy the identity and associativity relations. Now we also throw in an arrow satisfying . That is, we can start with an “element” of and split it into two copies. Then we can either copy with and leave the other alone. Then we can multiply together the copies. Either choice of which one to hit with will give us the exact same result as if we’d just “forgotten” the original element of by passing to the terminal object, and then created a copy of the identity element with .

Wow, that looks complicated. Well, let’s take a functor from this category to that preserves products. Then what does the equation say in terms of elements of sets? We read off . That is, the product of and on either side is just the single element in the image of the arrow described by — the identity element of the monoid. But this is the condition that be the inverse of . So we’re just saying that (when we read the condition in sets) every element of our monoid has an inverse, which makes it into a group! Now a group object in any other category is a product-preserving functor from to .

We can do even better. Since the monoidal structure in is cartesian, it comes with a symmetry. The twist is defined as the unique arrow satisfying and . In sets, this means . Now we can add the relation to our category. In sets this reads that , which says that the multiplication is commutative. The resulting category is — the “theory of abelian groups” — and an “abelian group object” in a category is a product-preserving functor in .

Free Algebras

Let’s work an explicit example from start to finish to illustrate these free monoid objects a little further. Consider the category of modules over the commutative ring , with tensor product over as its monoidal structure. We know that monoid objects here are -algebras with units.

Before we can invoke our theorem to cook up free -algebras, we need to verify the hypotheses. First of all, is symmetric. Well, remember that the tensor product is defined so that -bilinear functions from to are in bijection with -linear functions from to . So we’ll define the function . Now there is a unique function which sends to . Naturality and symmetry are straightforward from here.

Now we need to know that is closed. Again, this goes back to the definition of tensor products. The set consists of -linear functions from to , which correspond to -bilinear functions from to . Now we can use th same argument we did for sets to see such a function as a -linear function from to the -module . Remember here that every modyle over is both a left and a right module because is commutative. That is, we have a bijection . Naturality is easy to check, so we conclude that is indeed closed.

Finally, we need to see that has countable coproducts. But the direct sum of modules gives us our coproducts (but not products, since our index set is infinite). Then since is closed the tensor product preserves all of these coproducts.

At last, the machinery of our free monoid object theorem creaks to life and says that the free -algebra on a -module is . And we see that this is exactly how we constructed the free ring on an abelian group! In fact, that’s a special case of this construction because abelian groups are -modules and rings are -algebras.

Free Monoid Objects

When we have an algebraic concept described as a set with extra structure, the morphisms between such structured sets are usually structure-preserving functions between the underlying sets. This gives us a “forgetful” functor which returns the underlying sets and functions. Then as we saw, we often have a left adjoint to this forgetful functor giving the “free” structure generated by a set.

But now that we’re talking about monoid objects we’re trying not to think about sets. A monoid object in is a monoidal functor from to , and a “homomorphism” of such monoid objects is a monoidal natural transformation. But the object part of such a functor is specified by one object of — the image of — which we can reasonably call the “underlying object” of the monoid object. Similarly, a natural transformation will be specified by a morphism between the underlying objects (subject to naturality conditions, of course). That is, we have a “forgetful functor” from monoid objects in to itself. And a reasonable notion of a “free” monoid object will be a left adjoint to this functor.

Now, if the monoidal category has coproducts indexed by the natural numbers, and if the functors and preserve these coproducts for all objects , then the forgetful functor above will have a left adjoint. To say that the monoidal structure preserves these coproducts is to say that the following “distributive laws” hold:

For any object we can define the “free monoid object on ” to be , equipped with certain multiplication and unit morphisms. For the unit, we will use the inclusion morphism that comes for free with the coproduct. The multiplication will take a bit more work.

Given any natural numbers and , the object is canonically isomorphic to , which then includes into using the coproduct morphisms. But this object also includes into , which is isomorphic to . Thus by the universal property of coproducts there is a unique morphism . This is our multiplication.

Proving that these two morphisms satisfy the associativity and identity relations is straightforward, though somewhat tedious. Thus we have a monoid object in . The inclusion defines a universal arrow from to the forgetful functor, and so we have an adjunction.

So what does this look like in ? The free monoid object on a set will consist of the coproduct (disjoint union) of the sets of ordered -tuples of elements of . The unit will be the unique -tuple , and I’ll leave it to you to verify that the multiplication defined above becomes concatenation in this context. And thus we recover the usual notion of a free monoid.

One thing I slightly glossed over is showing that satisfies the hypotheses of our construction. It works here for the same reason it will work in many other contexts: is a closed category. Given any closed category with countable coproducts, the functor has a right adjoint by definition. And thus it preserves all colimits which might exist. In particular, it preserves the countable coproducts, which is what the construction requires. The other functor preserves these coproducts as well because the category is symmetric — tensoring by on the left and tensoring by on the right are naturally isomorphic. Thus we have free monoid objects in any closed category with countable coproducts.