Subject: categories: *-Autonomous Abelian Functor Categories

From: Peter Freyd <[email-masked]>
Date: Mon, 21 Nov 2005 11:51:14 -0500 (EST)

Let  R  be a commutative ring. {Footnote: If, instead, R  is a ring
with anti-involution (such as a group-ring) all that is below appears
to still hold.} Let  R-fpmod  be the category of finitely presented
R-modules and let  *F*  be the full category of finitely presented
covariant abelian-group-valued functors on  R-fpmod. A functor is in
*F*  iff it appears in an exact sequence  H^A --> H^B --> T --> O
where the first two objects are representable functors.

It is an easy exercise to see that  *F*  is an exact subcategory of
the ambient functor category, hence an abelian category. For any
f.p.module  A  we will use  A@  to denote the functor that carries
B  to  A@B  (using, here,  @  for $\otimes$). If we choose a
finite-rank free resolution  F --> G --> A --> O  we obtain exact
F@ --> G@ --> A@ --> O.  Since  F@ = H^F, G@ = H^G  and  *F*  is
closed under cokernel formation, we know that  A@  is in  *F*. (I'll
continue to denote isomorphisms here with equality signs.)

Let  I  denote the forgetful functor from  R-fpmod  to the category
of abelian groups. It has two other notations, to wit, H^R  and  R@.

I pointed out in my last note that  *F*  is the free abelian category
generated by  R. (That is, given any abelian category with an object
and an action of  R  thereon there is an exact functor from  *F*  that
carries  I  to the given object, unique up to natural equivalence.)
But I'm not going to use that fact here. (I did use it to learn all
this stuff, though.).

NOTATION: Every group-valued functor from a category of  R-modules,
commutative  R, can be canonically lifted to a module-valued functor.
Given two such functors, S  and  T, we follow the CS tradition of
denoting their composition, "first apply  S  then  T"  as  S;T  (hence
(S;T)(A) = T(S(A)).

For fixed  S  the functor  S;T  is exact in the second variable. (That
property, together with  S:I = S, characterizes this bifunctor; we
don't actually need to define it in terms of composition.)

We will need:

         (H^A);(H^B) = H^{A@B}
and
           (A@);(B@) = (A@B)@

DEFINE:

     [S,T]  is the functor such that sends  A  to the group of natural
     transformations  Hom((H^A;S),T)

Note:  [S,T]  carries right exact sequences in the first variable to
left exact sequences, and preserves left-exactness in the second
variable. We will need the formula

       [H^A,T] = (A@);T

verifiable by evaluating on an arbitrary  B:

   [H^A,T](B)  =  Hom((H^B;H^A),T)  =  Hom(H^{A@B},T)  =
      T(A@B)  =  ((A@);T)(B)

A  couple of things implicit in the definition of  [S,T]  should be
explicated. First:

LEMMA: If  S  and  T  are in  *F*  then so is  S;T.

BECAUSE: If  T  is in  *F*  let  H^A --> H^B --> T --> 0  be
exact. We obtain an exact sequence

              S;H^A --> S;H^B --> S;T --> O

Since  *F*  is closed under cokernel formation it suffices to show
that  S;H^A  is in  *F*  for any f.p. R-module  A. Let  F  and  G  be
finite-rank free modules and  F --> G --> A --> O  exact. Then so is

            O --> S;H^A --> S;H^G --> S;H^F

Since  *F*  is closed under kernel formation it suffices to show that
S;H^F  is in  *F*  for any finite-rank free module  F. But  S;H^F  is
just a finite direct sum of copies of  S  and  *F*  is, of course,
closed under direct sums. []

Second explication:

LEMMA: If  S  and  T  are in  *F*  then so is  [S,T].

BECAUSE: If  S  is in  *F*  let  H^A --> H^B --> S --> 0  be exact. We
obtain an exact sequence

            O --> [S,T] --> [H^B,T] --> [H^A,T]

which we know can be rewritten as

            O --> [S,T] --> (B@);T --> (A@);T

Since  *F*  is closed under kernel formation and composition we're
done. []

DEFINE a  *-FUNCTOR,  S*  as  [S,I].

LEMMA:  The duality functor is exact

BECAUSE: If  S --> T  --> U  is exact then  H^A;S --> H^A;T  --> H^A;U
is exact for every  A. We will obtain, therefore, the exactness of
U*(A) --> S*(A) --> T*(A)  if we know:

LEMMA: The object  I  is injective in  *F*.

BECAUSE: Being a representable functor, I  is, of course, projective
in the ambient functor category, hence in  *F*.

Let
                               O

                               |

                               I

                               |

               H^A --> H^B --> T --> O

be exact (all vertical arrows point down). We seek a retraction for
I --> T. Since  I  is projective we can choose a map  I --> H^B  to
yield a commutative triangle. The fact that  I --> T  is monic says
that
                              O ----> I

                              |       |

                             H^A --> H^B

is a pullback. It is, therefore, the Yoneda-image of a pushout square:

                               B --> A

                               |     |

                               R --> O

Let  O --> K --> B --> A. It is an exercise in abelian categories
that  K --> B --> R  is epi. (The dual exercise is easy in the category
of abelian groups -- which, of course,  suffices.)  We may choose a
retraction  R --> K. The map it induces,  H^B --> H^K --> I, is such
that  H^A --> H^B --> H^K --> I  is a zero-map and we obtain a
factorization  H^B --> I  =  H^B --> T --> I. The map  T --> I  is what
we seek. []

{Footnote: The object I  need not be injective in the ambient functor
category. In the case  R = Z  let  T  be the functor that assigns to a
group its torsion subgroup. If  I  were injective then any endo-
transformation on  T  would extend to an endo-transformation on  I.
But there are uncountably many endo-transformations on  T  and only
countably many on  I  (the ring of endo-transformations on  T  is the
"n-adic" completion of the integers -- it may be constructed as the
product of all the p-adic completions.)}

THEOREM: The  *-functor on is a duality on  *F*.

WE NEED TO SHOW that  S** = S. First note that  I* = I, hence, of
course, I** = I. Second, for any finite-rank free module, F,
(H^F)** = H^F, just because the *-functor is additive. Third, for any
f.p. module  A  let  F  and  G  be finite rank free modules and
F --> G --> A --> O  exact. Then  O --> H^A --> H^G --> H^F  is exact
and is carried to exact  O --> (H^A)** --> H^G --> H^F, hence
(H^A)** = H^A. Finally, for any  T  in  *F*, choose
H^A --> H^B --> T --> O  exact. The **-functor carries it to exact
H^A --> H^B --> T** --> O  Hence  T** = T. []

Note that  (H^A)* =  [H^A,I]  =  (A@);I  =  A@.  Hence  (A@)* = H^A.

SLOGAN:   H^A  and  A@  are dual.

It follows that  A@  is injective in  *F*. (It's a good exercise to
find a direct proof.) And, of course, every object has an injective
resolution (if  H^A --> H^B --> T*--> O is exact then so is
O --> T --> B@ --> A@). Note that an f.p, functor is projective iff
it is representable and, dually, it is injective iff it is of the
form  A@.

{Footnote: The category of f.p. abelian-group-valued sheaves on
R-fpmod, that is, the category of f.p. abelian-group-valued
_contravariant_ functors on  R-fpmod need not have injective
resolutions. In the case that  R = Z  any f.p. functor will carry  Z
to an f.p. abelian group. If  E  is injective in the category of f.p
functors then for any  n > 0  the map  n:Z --> Z  induces monic
H_Z --> H_Z  hence epic  (H_Z,E) --> (H_Z,E). The latter is just
multiplication by  n  on  E(Z), hence  E(Z)  is a divisible group.
But the only divisible finitely generated abelian group is  O, thus
H_Z  can not have an injective extension.}

DEFINE  S@T  =  [S,T*]*.

It follows immediately that this bi-functor on  *F*  is right-exact in
both variables and that it is a commutative with  I  as unit. Note:

        H^A @ H^B   =   H^{A@B}

(which together with the right-exactness characterizes  @).

THEOREM	 *F*  is  *-autonomous.

BECAUSE: The only thing left to prove is

           Hom(S@T,U) = Hom(S,[T,U])

Both sides of this equation carry right-exact sequences in the first
two positions to left-exact sequences in the category of abelian
groups. It therefore suffices to verify the isomorphism when  S = H^A
and  T = H^B:

     Hom(H^A @ H^B, U) = Hom(H^{A@B},U) = U(A@B)

     Hom(H^A,[H^B,U]) = Hom(H^A,[H^B,U]) = ]H^B,U](A) = U(A@B)  []

COR:   [S,T] = [T*,S*]

LEMMA: For S  and  T  in  *F*,  (S;T)* = S*;T*.

BECAUSE: Both  (S;T)*  and  S*;T* are exact in  T. Because every
object in  *F*  is obtainable using finite limits and co-limits
starting with the object  I, it therefore suffices to establish that
(S;I)* = S*;I* and that's immediate. []

COR:  (H^A)@S = [H^A,S*]* = ((A@);S*)* = H^A;S

An interesting adjointness arises:

PROPOSITION: For  S  and  T  in  *F*

       Hom( H^A;S , T )  =  Hom( S , A@;T )

BECAUSE: H^A;S =  S@H^A  and  A@;T  =  [H^A,T].  []

{Footnote: When the compositions are reversed we obtain the routine
adjointness:  Hom( S;A@ , T )  =  Hom( S , T;H^A ).}

COR:  [S,T](A) = Hom(S, A@;T)
         S*(A) = Hom(S,A@).

{Footnote: The last equation is the one I used at Ottawa to compute
S*. If all one knows is that there is a duality on  *F*  such that
(H^A)* = A@  then we may infer
S*(A)  =  Hom(H^A,S*) = Hom(S**,(H^A)*) = Hom(S,A@).}

Recall that a coherent ring is one such that all finitely generated
ideals are finitely presented. It follows that f.p. modules are
closed under finite limits (hence form an exact subcategory).

{Footnote: Clearly Noetherian implies coherent. For a quick separating
example take the group ring of the rationals (usually called
"polynomials with rational exponents"). All finitely generated ideals
are principal. The important non-Noetherian examples arise in
algebraic geometry.}

LEMMA: For f.p. modules over a coherent ring

		 Ext^n(A,-)   and  Tor_n(A,-)  are dual.

BECAUSE: Choose a free resolution

     ...--> F_{n+1} --> F_n -->....--> F_2 --> F_1 --> A --> 0

The  Ext^n(A,--)  functors are obtainable as the homology of the
sequence:

    0 --> H^A --> H^{F_1} --> H^{F_2} --> ...

The  Tor_n(A,--)  functors are obtainable as the homology of the
sequence:

     ... --> (F_2)@ --> (F_1)@ --> A@ --> O.

These complexes are dual. []

It has not escaped my notice that this *-autonomous structure suggests
a possible alternate approach to classical homological algebra. Just
one example: a "connecting homomorphism" between half-exact f.p.
functors  S  and  T  may be identified as an exact sequence of the
form  O --> S --> E --> P --> T --> O  where  E  is injective and  P
is projective and this says that the duality works well with the
notion of satellites and derived functors.

---

From: Vaughan Pratt <[email-masked]>
Date: Sun, 27 Nov 2005 19:38:54 -0800

Peter Freyd wrote on 11/21/2005:
> ...

Actually it is an RA (Relation Algebra) tradition dating back to the
19th century.  In my LICS'92 evening history talk, "Origins of the
Calculus of Binary Relations", http://boole.stanford.edu/pub/ocbr.pdf, I
attributed it as follows.

> But this view of composition/concatenation as a form of conjunction
> predates even Peirce and would appear to be due to De Morgan in 1860
> [DeM].  The following footnote appears exactly one-third of the
> way through De Morgan's ``On the Syllogism IV'' (p.221 in Heath's
> anthology ``On the Syllogism'' [DeM66]).  Here De Morgan argues
> that, allowing for the obvious differences, composition L;M of
> relations L and M resembles conjunction XY of ``terms''
> (predicates) X and Y.  Indeed he notates composition LM the
> better to suggest conjunction---the L;M notation which is now in
> almost universal use, and is in (fortuitous?) agreement with Algol 60
> and dynamic logic [Pr76], was introduced later by Peirce.

I still don't know whether RA played any role in the adoption of ; by
Algol 60.  However Algol 60 used ; not as a statement terminator (as in
C or Java) but as an associative infix operator between statements,
suggestive of RA influence.  (Perhaps so as not to overly inconvenience
those who tended to think of semicolon as a terminator anyway, the empty
string was permitted as a statement, inadvertently complicating the task
of generating the language Algol 60 with an unambiguous context-free
grammar.)

Vaughan Pratt