On defining *-autonomous categories

On defining *-autonomous categories

[Michael Barr]

I got a note from a student named Benjamin Jackson saying that someone had
told him that to define a *-autonomous category, you need only a symmetric
monoidal category and a contravariant involution * such that Hom(A @ B,C*)
= Hom(A,(B @ C)*).  Here "=" means natural equivalence and @ is the tensor
product.  Not only is this apparently true but that equivalence is needed
only for A = I, the tensor unit.  Of course, what is going on is that all
the coherence is built-in to the structure of a symmetric monoidal
category.

First define A --o B = (A @ B*)*.  Then the isomorphism above implies that
    Hom(A,B) = Hom(I @ A,B) = Hom(I,(A @ B*)*) = Hom(I,A --o B)
Next we see that
    (A @ B) --o C = (A @ B @ C*)* = A --o (B @ C*)* = A --o (B --o C)
and, applying Hom(I,-), that
       Hom(A @ B,C) = Hom(A,B --o C)
Also we have that
  A --o I* = (A @ I)* = A* and A --o B = (A @ B*)* = (B* @ A)* = B* --o A*
which gives the structure of a *-autonomous category with dualizing
object I*.

The trouble with this is that generally speaking it is the --o which is
obvious and the tensor is derived from it.  The coherences involving
internal hom alone are much less well-known, although they are included
in the original Eilenberg-Kelly paper in the La Jolla Proceedings.
Still I am surprised that I never noticed this before.

Re: On defining *-autonomous categories

[Prof. Peter Johnstone]

This result is a special case of a general fact about adjunctions,
which appears (yes, really!) as Lemma A1.1.1 in the Elephant.
I don't claim any originality for it, but I did comment in the
text that it "seems not to be widely known".

Lemma: Let F: C --> D be a functor having a right adjoint G.
If there is any natural isomorphism between the composite FG and
the identity functor on D, then the counit of the adjunction is
an isomorphism.

Proof: One can transport the comonad structure on FG across the
isomorphism, to obtain a comonad structure on 1_D. But the monoid
of natural endomorphisms of the identity functor on any category
is commutative, so the counit and comultiplication of this comonad
must be inverse isomorphisms. Transporting back again, the counit
of (F -| G) is an isomorphism.

Peter Johnstone

On Tue, 18 Dec 2007, Robin Houston wrote:

> On Mon, Dec 17, 2007 at 02:29:17PM -0400, Peter Selinger wrote:
>> On the other hand, none of the above matters in some sense, due to a
>> theorem proved last year by Robin Houston (it was previously unknown
>> at least to me):
>>
>>  Theorem. Let C be a symmetric monoidal category, and let D be an object.
>>  If there *exists* a natural isomorphism f : A -> (A -o D) -o D,
>>  then the *canonical* natural transformation g : A -> (A -o D) -o D
>>  (coming from the symmetric monoidal structure) is an isomorphism
>>  (although it may in general be different from f).
>
> I suspect I may not have been the first to notice this, since it's
> fairly easy, though I'm not aware that it's ever been mentioned
> in print. (If anyone knows otherwise, I'd be interested to hear.)
>
>
> Claim: Let C be a symmetric monoidal closed category, and
> let D be an object of C. Then the following are equivalent:
>
> 1. There exists a natural isomorphism A = (A -o D) -o D,
> 2. The functor (- -o D) is full and faithful,
> 3. The canonical natural transformation A -> (A -o D) -o D is
>   invertible.
>
>
> Lemma 1. Let G: X -> Y and H: Y -> Z be functors. If HG is faithful
> then G is faithful; if HG is full and G is essentially surjective,
> then H is full.
>
> Proof: easy.
>
> Lemma 2. Let C be a category, and F: C -> C an endofunctor. If FF
> is naturally isomorphic to 1_C, then F is an equivalence.
>
> Proof: Certainly F is essentially surjective, since every object
> X in C is naturally isomorphic to FFX. It then follows by Lemma 1
> that F is full and faithful.
>
>
> For the implication 1 => 2, take F = (- -o D) in Lemma 2.
>
>
> For the implication 2 => 3, consider the following sequence of
> isomorphisms natural in A \in C:
>
>    C(A, A)
> -> C(A -o D,  A -o D)       ;apply the functor (- -o D)
> =  C((A -o D) @ A, D)       ;closure
> =  C(A @ (A -o D), D)       ;symmetry of tensor
> =  C(A,  (A -o D) -o D)     ;closure again
>
> By definition, this natural transformation corresponds under Yoneda
> to the canonical A -> (A -o D) -o D. Since (- -o D) is full and faithful,
> the first step is invertible; the others are necessarily so. Therefore,
> by the Yoneda correspondence, the canonical natural transformation with
> components A -> (A -o D) -o D is invertible.
>
> [ Robin Cockett pointed out to me that this can be decomposed into
>  two steps, one easy and one well-known:
>   a) The functor (- -o D) is self-adjoint on the right.
>   b) For any adjunction, the left adjoint is full and faithful
>      if and only if the unit of the adjunction is invertible. ]
>
>
> Finally, the implication 3 => 1 is immediate.
>
> Robin
>
>
>

Re: On defining *-autonomous categories

[Robin Houston]

On Tue, Dec 18, 2007 at 01:08:07PM +0000, Robin Houston wrote:
> Lemma 2. Let C be a category, and F: C -> C an endofunctor. If FF
> is naturally isomorphic to 1_C, then F is an equivalence.
>
> Proof: Certainly F is essentially surjective, since every object
> X in C is naturally isomorphic to FFX. It then follows by Lemma 1
> that F is full and faithful.
>
>
> For the implication 1 => 2, take F = (- -o D) in Lemma 2.

There is a silly mistake here, caused by the fact that the functor
(- -o D) is contravariant. The error is really in the statement of
Lemma 2; of course the proof still works for contravariant F.

Robin

Re: On defining *-autonomous categories

[Robin Houston]

On Mon, Dec 17, 2007 at 02:29:17PM -0400, Peter Selinger wrote:
> On the other hand, none of the above matters in some sense, due to a
> theorem proved last year by Robin Houston (it was previously unknown
> at least to me):
>
>  Theorem. Let C be a symmetric monoidal category, and let D be an object.
>  If there *exists* a natural isomorphism f : A -> (A -o D) -o D,
>  then the *canonical* natural transformation g : A -> (A -o D) -o D
>  (coming from the symmetric monoidal structure) is an isomorphism
>  (although it may in general be different from f).

I suspect I may not have been the first to notice this, since it's
fairly easy, though I'm not aware that it's ever been mentioned
in print. (If anyone knows otherwise, I'd be interested to hear.)


Claim: Let C be a symmetric monoidal closed category, and
let D be an object of C. Then the following are equivalent:

1. There exists a natural isomorphism A = (A -o D) -o D,
2. The functor (- -o D) is full and faithful,
3. The canonical natural transformation A -> (A -o D) -o D is
   invertible.


Lemma 1. Let G: X -> Y and H: Y -> Z be functors. If HG is faithful
then G is faithful; if HG is full and G is essentially surjective,
then H is full.

Proof: easy.

Lemma 2. Let C be a category, and F: C -> C an endofunctor. If FF
is naturally isomorphic to 1_C, then F is an equivalence.

Proof: Certainly F is essentially surjective, since every object
X in C is naturally isomorphic to FFX. It then follows by Lemma 1
that F is full and faithful.


For the implication 1 => 2, take F = (- -o D) in Lemma 2.


For the implication 2 => 3, consider the following sequence of
isomorphisms natural in A \in C:

    C(A, A)
 -> C(A -o D,  A -o D)       ;apply the functor (- -o D)
 =  C((A -o D) @ A, D)       ;closure
 =  C(A @ (A -o D), D)       ;symmetry of tensor
 =  C(A,  (A -o D) -o D)     ;closure again

By definition, this natural transformation corresponds under Yoneda
to the canonical A -> (A -o D) -o D. Since (- -o D) is full and faithful,
the first step is invertible; the others are necessarily so. Therefore,
by the Yoneda correspondence, the canonical natural transformation with
components A -> (A -o D) -o D is invertible.

[ Robin Cockett pointed out to me that this can be decomposed into
  two steps, one easy and one well-known:
   a) The functor (- -o D) is self-adjoint on the right.
   b) For any adjunction, the left adjoint is full and faithful
      if and only if the unit of the adjunction is invertible. ]


Finally, the implication 3 => 1 is immediate.

Robin

Re: On defining *-autonomous categories

[Peter Selinger]

Dear Mike,

first, the definition that you "never noticed before" appears as
Definition C in your paper "Non-symmetric *-autonomous categories"
(Theoretical Computer Science, 139 (1995), 115-130). Okay, there are
minor differences, e.g., in that paper you considered the
non-symmetric case and you didn't require * to be an involution.

The definition precisely as stated in your email (and not in your
paper) is problematic: one obtains two canonical isomorphisms A ->
A**, and they do not in general coincide. Namely, the first such
morphisms is the isomorphism invol : A -> A** that comes from the
requirement "contravariant involution". The second one is lift : A ->
A** and comes from the monoidal closed structure. It is given
explicitly by the following string of equivalences:

= Hom(X, A)
= Hom(A*, X*)
= Hom(I, (A* @ X)*)  ax
= Hom(I, (X @ A*)*)  sym
= Hom(X, A**)        ax

To see that they do not, in general, coincide, consider a *-autonomous
category C in which there exists a non-trivial natural isomorphism
eta_A : A -> A from the identity functor to itself (for example,
finite dimensional vector spaces where eta is multiplication by -1).
Consider the usual functor (-)* and the usual isomophism Hom(A @
B,C*) = Hom(A,(B @ C)*). Let invol : A -> A** be the usual involution,
and let invol' = invol o eta: A -> A -> A**. Then invol' defines
another structure of "contravariant involution" on the functor
(-)*, different from lift.

Therefore, in general, for this definition to be useable, one needs
another coherence condition stating that invol = lift.  Or else, one
can just drop the a priori requirement that * is involutive, and just
let it follow from the other structure (as you did in the above-cited
paper).

This seems a good moment to mention that another definition of
*-autonomous category, which occasionally appears in the literature,
suffers from a similar affliction. Some authors define a *-autonomous
category to be a symmetric monoidal category C together with a functor
(-)* : C^op -> C and a natural isomorphism Hom(A @ B, C) = Hom(A, (B @
C*)*). Although this definition does not a priori assume * to be
involutive, it still yields two canonical maps C -> C** that do not in
general coincide, and therefore, it is missing a coherence condition.
The two competing maps f_1 and f_2 are given as follows:

   (A, A)   ==   (A x I, A)
            ==   (A, (I x A*)*)            (ax)
            ==   (A, A**).

   (A*, A*) ==   (A*, (A x I**)*)          (##)
            ==   (A* x A, I*)              (ax)
            ==   (A x A*, I*)
            ==   (A, (A* x I**)*)          (ax)
            ==   (A, A**)                  (##)

Here, (ax) is the axiom, and (##) denotes an application of the
isomorphism I = I**, which can be obtained by letting A=B=C in (ax).
To see that they don't in general coincide, consider the same
counterexample as above, and modify the isomorphism (ax) by
multiplication with the scalar -1. Since it is used an odd number of
times in the definition of f_1, but an even number of times in the
definition of f_2, it follows that f_1 != f_2.


On the other hand, none of the above matters in some sense, due to a
theorem proved last year by Robin Houston (it was previously unknown
at least to me):

 Theorem. Let C be a symmetric monoidal category, and let D be an object.
 If there *exists* a natural isomorphism f : A -> (A -o D) -o D,
 then the *canonical* natural transformation g : A -> (A -o D) -o D
 (coming from the symmetric monoidal structure) is an isomorphism
 (although it may in general be different from f).

Therefore, in the definition of *-autonomous category, the mere
existence of an isomorphism (not necessarily satisfying coherence
conditions) already implies the existence of a (possibly different)
isomorphism satisfying all the coherence conditions. In this sense,
both the Hom(A @ B,C*) = Hom(A,(B @ C)*) definition and the Hom(A @
B,C*) = Hom(A,(B @ C)*) definition are correct: they certainly imply
that the underlying category is *-autonomous - although not necessarily
with the given structure!

-- Peter


Michael Barr wrote:
>
> I got a note from a student named Benjamin Jackson saying that someone had
> told him that to define a *-autonomous category, you need only a symmetric
> monoidal category and a contravariant involution * such that Hom(A @ B,C*)
> = Hom(A,(B @ C)*).  Here "=" means natural equivalence and @ is the tensor
> product.  Not only is this apparently true but that equivalence is needed
> only for A = I, the tensor unit.  Of course, what is going on is that all
> the coherence is built-in to the structure of a symmetric monoidal
> category.
>
> First define A --o B = (A @ B*)*.  Then the isomorphism above implies that
>     Hom(A,B) = Hom(I @ A,B) = Hom(I,(A @ B*)*) = Hom(I,A --o B)
> Next we see that
>     (A @ B) --o C = (A @ B @ C*)* = A --o (B @ C*)* = A --o (B --o C)
> and, applying Hom(I,-), that
>        Hom(A @ B,C) = Hom(A,B --o C)
> Also we have that
>   A --o I* = (A @ I)* = A* and A --o B = (A @ B*)* = (B* @ A)* = B* --o A*
> which gives the structure of a *-autonomous category with dualizing
> object I*.
>
> The trouble with this is that generally speaking it is the --o which is
> obvious and the tensor is derived from it.  The coherences involving
> internal hom alone are much less well-known, although they are included
> in the original Eilenberg-Kelly paper in the La Jolla Proceedings.
> Still I am surprised that I never noticed this before.