## 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 $k$, so a linear category is a category enriched over $Vect$, the category of vector spaces over $k$. 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 $T$ 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 : 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 $T$ in $Set$ is the same as $T^{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 $T$ is a finitely complete linear category, the category of finitely presentable models of $T$ in $Vect$ is equivalent to $T^{op}$. Again, there may be fine print being overlooked here, but life is short, so I’m willing to risk it.

So: let $T^{op}$ be ‘the free finitely cocomplete linear category on an epi’ — the thing the puzzle is asking us to compute.Then $T$ 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 $X$, a ‘model’ of $T$ in $X$ is a finite-limit-preserving linear functor $f : T \to X$ By saying $T$ is ‘free on a mono’, we mean such models are the same as monos in $X$. So a model of $T$ in $Vect$ is just a mono $V \hookrightarrow W$ where $V$ and $W$ are vector spaces. In a finitely presentable model, $V$ and $W$ will be finite-dimensional vector spaces.

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

In short, we seem to be getting this:

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

Now this raises a big question: if the category of monos in $FinVect$ 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 $FinVect$?

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

That, at least, should be obvious. It’s a commuting square $\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 $FinVect$ is free on an epi, what is that epi?” Here it is: $\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 $FinVect$ is not abelian.

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

So, the category of monos in $FinVect$ is equivalent to the category of short exact sequences in $FinVect$, which is equivalent to the category of epis in $FinVect$. 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 $FinVect$ 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 $FinVect$ 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: $\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: $\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

### Re: Homological Algebra Puzzle

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. Back here it was mentioned how $Set$ 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 $Set$ could allow it to ‘keep winter and summer homes’? And how does $Vect$ 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 $c \in C$, the functor from $C$ to $Set$ sending $x \in C$ to $hom(c,x)$ preserves all limits. So, any object of $C$ gives a limit-preserving functor

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

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

(Or at least all small limits. Of course $Set$ 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 $Set$ here, and that any sufficiently nice category $V$ will give rise to a ‘$V$-enriched’ version of Gabriel–Ulmer duality and its many relatives. All I really need for the stuff I wrote is the case $V = 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 $C$ than merely that it has small limits, or a just little but more about our functors $C\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:C \to Set$ has a left adjoint $F$, then $F$ preserves all colimits and thus is uniquely determined by the object $c = F(1)$ (since $Set$ is the free cocompletion of a point), and we have $G(-) = Set(1,G(-)) = C(F(1),-) = C(c,-)$.

Thus, while $C^{op}$ is not the same as the category of limit-preserving functors $C\to Set$, it is the same as the category of right adjoints $C\to Set$, which is almost as good. By the general adjoint functor theorem, we could equally well say $C^{op}$ is the same as the category of functors $C\to Set$ which satisfy the solution-set condition. And if $C$ 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 $C\to Set$ is a right adjoint, and so the theorem is true for such $C$.

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