Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 1, 2010

Homological Algebra Puzzle

Posted by John Baez

Whenever I have time to talk with James Dolan, he likes to pose puzzles — partially to test out ideas he just had, partially to teach me stuff, and partially just to watch me squirm. I’m always happiest when I find a mistake in his solution of the puzzle, but the next best thing is to solve it.

Here’s the puzzle he threw at me tonight while we were eating pizza. It’s part of a much bigger story, but I’ll rip it out of context and throw it at you:

Puzzle: What is the free finitely cocomplete linear category on an epi?

First, remember what Tom said:

Someone taught me how to spot a fake knot theorist. (You can never be too careful.) Simply ask them to draw a trefoil. If they hesitate in the slightest, they’re faking it. Actually, this will only catch really bad fakes, but in some weak sense it’s a shibboleth, a mark of identity, or at the very least, something that any professional can do.

The point I want to make is that for category theory, the ability to throw around phrases of the form

the free such-and-such category containing a such-and-such

is something like the ability to draw a trefoil without hesitation. Of course, this comparison isn’t entirely serious: one of these skills is much more meaningful than the other. But there is something serious here. While there are plenty of people who are fluent in quite sophisticated category- and topos-speak, it seems to me that outside the smallish group for whom category theory is a central research interest, not many people are comfortable with phrases of this form. And that’s a shame.

So, while the essence of this puzzle turns out to be homological algebra, being able to think about it without instantly fainting is a test of whether you’re a category theorist.

Of course, it also helps to know what the words mean here:

“What is the free finitely cocomplete linear category on an epi?”

Here ‘epi’ is a cute nickname for epimorphism — and soon to come we’ll see ‘mono’, which is a cute nickname for monomorphism. Also: we are secretly fixing a field kk, so a linear category is a category enriched over VectVect, the category of vector spaces over kk. Finally, by ‘finitely cocomplete’ we mean our category has finite colimits. For linear categories, this means it has cokernels and finite coproducts. If you don’t know much about finitely cocomplete categories, you can read an article about finitely complete categories and then turn around all the arrows! Or just stand on your head while reading it.

Okay: try the puzzle. Our attempted solution — not guaranteed to be correct — is below the fold. Even if it’s correct, we could certainly use some help filling in the details.

I first figured out an answer using intuition in a pretty lowbrow way, but let me give the slick approach that Jim then prodded me into.

The idea is to use an enriched version of Gabriel–Ulmer duality:

  • Peter Gabriel and Friedrich Ulmer, Lokal Praesentierbare Kategorien, Springer Lecture Notes in Mathematics 221, Berlin, 1971.

Gabriel–Ulmer duality is about finitely complete categories. I don’t understand it terribly well, but I think the idea is this:

We can think of a finitely complete category TT as a kind of ‘theory’ — sometimes called a ‘finite limits theory’ or essentially algebraic theory. A ‘model’ of this theory in the category of sets is a functor f:TSetf : T \to Set that preserves finite limits. We can talk about a model being ‘finitely presented’. Gabriel–Ulmer duality says that the category of finitely presentable models of TT in SetSet is the same as T opT^{op}.

I don’t know if this works for enriched categories, so I’ll pretend it does and hope someone smart can fill in the details.

In other words, I’ll hope something like this: if TT is a finitely complete linear category, the category of finitely presentable models of TT in VectVect is equivalent to T opT^{op}. Again, there may be fine print being overlooked here, but life is short, so I’m willing to risk it.

So: let T opT^{op} be ‘the free finitely cocomplete linear category on an epi’ — the thing the puzzle is asking us to compute.Then TT is ‘the free finitely complete linear category on a mono’ — the sort of thing where we can try to use Gabriel–Ulmer duality.

By definition, for any finitely complete linear category XX, a ‘model’ of TT in XX is a finite-limit-preserving linear functor f:TX f : T \to X By saying TT is ‘free on a mono’, we mean such models are the same as monos in XX. So a model of TT in VectVect is just a mono VWV \hookrightarrow W where VV and WW are vector spaces. In a finitely presentable model, VV and WW will be finite-dimensional vector spaces.

So: T opT^{op} is equivalent to the category of monos in the category of finite-dimensional vector spaces. Let’s call that category FinVectFinVect.

In short, we seem to be getting this:

Answer: The free finitely cocomplete linear category on an epi is the category of monos in FinVectFinVect.

Now this raises a big question: if the category of monos in FinVectFinVect is free on an epi, what is that epi?

And this raises a smaller but still mildly mind-boggling question: what is an epi in the category of monos in FinVectFinVect?

And this raises an even tinier question: what is a morphism in the category of monos in FinVectFinVect?

That, at least, should be obvious. It’s a commuting square V W V W \array{ V & \hookrightarrow & W \\ \downarrow & & \downarrow \\ V' & \hookrightarrow & W' } where the horizontal arrows are monos.

Then, after I gave a probably wrong answer, James told me what seems to be the right answer to the big question, “if the category of monos in FinVectFinVect is free on an epi, what is that epi?” Here it is: 0 k 1 k 1 k \array{ 0 & \rightarrow & k \\ \downarrow & & \downarrow 1 \\ k & \stackrel{1}{\rightarrow} & k }

Interestingly, the left-hand vertical arrow is not an epi! You might naively guess that to get an epi in the category of monos, both vertical arrows would need to be epis. But that’s not true — as you can see by pondering this example.

More interestingly, this epi is not a cokernel. In the definition of abelian category, there’s a clause saying every epi must be a cokernel. So, the category of monos in FinVectFinVect is not abelian.

Even more interestingly, every mono in FinVectFinVect determines a short exact sequence, which determines an epi — and conversely. Given the mono 0UiV 0 \to U \stackrel{i}{\to} V we get the short exact sequence 0UiVpW0 0 \to U \stackrel{i}{\to} V \stackrel{p}{\to} W \to 0 where WW is the cokernel of ii, and this gives the epi VpW0 V \stackrel{p}{\to} W \to 0 Conversely, we can turn this process around: since FinVectFinVect is abelian, every mono is a kernel and every epi is cokernel.

So, the category of monos in FinVectFinVect is equivalent to the category of short exact sequences in FinVectFinVect, which is equivalent to the category of epis in FinVectFinVect. Any one of these categories should be an equally good answer to our puzzle!

And, we see that none of these categories is abelian. This is especially interesting because, if we haven’t screwed up, the category of monos in FinVectFinVect should have finite colimits. Why? Because it’s the answer to the puzzle “What’s the free finitely cocomplete linear category on an epi?” (Of course I’m sure we can also easily see this directly, at least if it’s true, but I’m too tired to check that now!)

It follows that dually, the category of epis in FinVectFinVect should have finite limits. But since these categories are equivalent, either one is a linear category that’s finitely complete and finitely cocomplete, but still not abelian!

Saying it yet another way:

The category of short exact sequences of finite-dimensional vector spaces is a linear category with finite limits and finite colimits that’s not abelian.

And that’s nice, because most of the finitely complete and cocomplete linear categories that leap to mind are abelian, but this is a pretty natural counterexample.

Further mucking about shows that this epi in the category of monos: 0 k 1 k 1 k \array{ 0 & \rightarrow & k \\ \downarrow && \downarrow 1 \\ k & \stackrel{1}{\rightarrow} & k } is also a mono in the category of monos. So, we’re getting a nice example of a morphism that’s an epimorphism and a monomorphism but not an isomorphism. It looks a bit cuter if we draw it as a morphism in the category of short exact sequences: 0 0 k 1 k 0 1 0 k 1 k 0 0 \array{0 &\to & 0 & \rightarrow & k & \stackrel{1}{\to} &k &\to& 0 \\ && \downarrow && \downarrow 1 && \downarrow \\ 0& \to & k & \stackrel{1}{\rightarrow} & k & \to &0 &\to& 0 }

So, it was a pretty fun puzzle. Do you see any mistakes in our work? Can you fill in some of the details of enriched Gabriel–Ulmer duality? Any other comments or questions?

Posted at July 1, 2010 6:30 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2237

6 Comments & 0 Trackbacks

Re: Homological Algebra Puzzle

Presumably just as 22 can support a whole raft of structures allowing it to play the role of dualizing object for many dualities, as described in Stone Spaces, SetSet likewise supports many structures. Back here it was mentioned how SetSet is both a category with finite products, and an object in the category of such categories with finite product preserving functors. But it is also a category with all limits and colimits, and an object in the category of such categories with functors which preserve limits, filtered colimits, and regular epimorphisms.

What other structures on SetSet could allow it to ‘keep winter and summer homes’? And how does VectVect work as a dualizing object?

Posted by: David Corfield on July 2, 2010 1:56 PM | Permalink | Reply to this

Re: Homological Algebra Puzzle

David wrote:

Presumably just as 2 can support a whole raft of structures allowing it to play the role of dualizing object for many dualities, as described in Stone Spaces, Set likewise supports many structures.

Right, that’s the idea behind Gabriel–Ulmer duality for essentially algebraic theories (= categories with finite limits) and also the simpler Lawvere duality for algebraic theories (= categories with finite products). There are also many other dualities of this sort, good for categories that have other kinds of limits.

So, one could start by trying to generalizes these dualities to a general theory of dualities that work for ‘categories with a specified class of limits’.

This paper does the job:

Why are limits so important here? It’s because for any object cCc \in C, the functor from CC to SetSet sending xCx \in C to hom(c,x)hom(c,x) preserves all limits. So, any object of CC gives a limit-preserving functor

hom(c,):CSet hom(c,-) : C \to Set

Note that hom(c,)hom(c,-) is contravariant as a function of cc. And so, one could dream that C opC^{op} is just the same as the category of functors from CC to SetSet that preserve all limits. At least, say, if CC has all limits.

(Or at least all small limits. Of course SetSet has all small limits.)

Sadly, this beautiful dream is false, for ‘technical’ reasons. I’m sure many people here could explain this failure much better than I could. But this false dream gives birth to a thousand theorems that are actually true: one for each ‘limit doctrine’ of the sort studied by Centazzo and Vitale!

I’m hoping that there’s nothing incredibly special about SetSet here, and that any sufficiently nice category VV will give rise to a ‘VV-enriched’ version of Gabriel–Ulmer duality and its many relatives. All I really need for the stuff I wrote is the case V=VectV = Vect.

In this paper:

the authors say (a bit curiously, given the title), “For ease of exposition, we shall ignore enrichment beyond saying that everything we write enriches without fuss…”

Posted by: John Baez on July 2, 2010 6:10 PM | Permalink | Reply to this

Re: Homological Algebra Puzzle

This kind of thing has come up in conversation before.

Posted by: Todd Trimble on July 2, 2010 7:04 PM | Permalink | Reply to this

Re: Homological Algebra Puzzle

Thanks! I was wondering how Cauchy completeness fit into the picture, since you’ve sensitized me to its importance…

Posted by: John Baez on July 2, 2010 8:18 PM | Permalink | Reply to this

Re: Homological Algebra Puzzle

Sadly, this beautiful dream is false, for ‘technical’ reasons.

But it becomes true if we assume just a little bit more about CC than merely that it has small limits, or a just little but more about our functors CSetC\to Set than that they preserve limits. For every (small-)limit-preserving functor is not-so-secretly yearning to be a right adjoint, and if G:CSetG:C \to Set has a left adjoint FF, then FF preserves all colimits and thus is uniquely determined by the object c=F(1)c = F(1) (since SetSet is the free cocompletion of a point), and we have G()=Set(1,G())=C(F(1),)=C(c,)G(-) = Set(1,G(-)) = C(F(1),-) = C(c,-).

Thus, while C opC^{op} is not the same as the category of limit-preserving functors CSetC\to Set, it is the same as the category of right adjoints CSetC\to Set, which is almost as good. By the general adjoint functor theorem, we could equally well say C opC^{op} is the same as the category of functors CSetC\to Set which satisfy the solution-set condition. And if CC is nice enough to satisfy the hypotheses of the special adjoint functor theorem (e.g. complete, locally small, well-powered, and with a small generating set), then every limit-preserving functor CSetC\to Set is a right adjoint, and so the theorem is true for such CC.

I know you know all this, but I think it deserves to be mentioned that the ‘technical problems’ go away if you assume just a little bit more.

Posted by: Mike Shulman on July 3, 2010 4:40 AM | Permalink | Reply to this

Re: Homological Algebra Puzzle

Mike wrote:

I know you know all this…

I’ve certainly heard all this, but that’s not the same as knowing it.

For me, the hypotheses of the special and general adjoint functor theorems keep going in one ear and out the other. I’ve never actually used these theorems — and I wasted my youth, when I eagerly memorized theorems just for the fun of it, doing analysis. So, I wanted to state the ‘false dream’, which is easy to remember, but somehow not mentioned often enough… and let someone who really understands this stuff give the true story. Thanks!

Posted by: John Baez on July 3, 2010 5:00 PM | Permalink | Reply to this

Post a New Comment