On defining *-autonomous categories
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.
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.
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
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
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
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
The following is a little irrelevant now that PTJ has piped up with his beautiful lemma, but just for the sake of propriety I should correct yet another minor error in what I wrote. (I'm not posting this to the list.) On Tue, Dec 18, 2007 at 01:08:07PM +0000, Robin Houston wrote:
For the implication 2 => 3, consider the following sequence of isomorphisms natural in A \in C:
What I wrote isn't quite right, of course. You should really consider the following sequence of isomorphisms natural in A and B \in C: C(A, B) -> C(B -o D, A -o D) ;apply the functor (- -o D) = C((B -o D) @ A, D) ;closure = C(A @ (B -o D), D) ;symmetry of tensor = C(A, (B -o D) -o D) ;closure again with the rest of the argument as I said. But PTJ's argument is much more elegant! Robin
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
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.
participants (7)
-
Dusko Pavlovic -
John Baez -
Michael Barr -
Prof. Peter Johnstone -
Robin Houston -
selinger -
selinger＠mathstat.dal.ca