Quantum computation and categories
Dear Dusko - You wrote: bob coecke proposed to add quantum computing to andre joyal's list of
important directions of categorical research, but andre rejected it.
most results in quantum computing are theorems about hilbert spaces. quantum
computing is a *tensor calculus*. but it is a tensor calculus of a special kind: it attempts to describe a wildly unintuitive world. even the greatest contributors, like von neumann and feynman, deplored the gap between the quantum world, imposed on us in the lab, and the intuitions imposed on us in everyday life. now category theory often helps where the common intuitions fail. many of its applications demonstrate this. so quantum computation might be an opportunity for an effective application of *geometry of tensor calculus*.
Exactly! Samson Abramsky, Bob Coecke, Peter Selinger and others have been doing great work along these lines. I think this line of research will eventually be the key to understanding quantum gravity, because string diagrams reveal the common features of the tensor category of Hilbert spaces (Hilb, fundamental to quantum theory) and the tensor category of cobordisms (nCob, fundamental to our traditional notion of spacetime). I argued this case here, in a nontechnical way: http://math.ucr.edu/home/baez/quantum/ And I think that regardless of whether quantum computers or quantum gravity ever work, this line of research is very interesting.
is it really wise to reject an attempt to develop this, as objectionable as it might be in any details?
Andre didn't precisely "reject an attempt to develop" these ideas. He said "I am not convinced that quantum computing can contribute significantly to category theory". And that's fine. The bold researchers listed above will now redouble their efforts to convince Andre by proving lots of wonderful theorems. Here's one point where work on quantum computing, quantum gravity, and TQFT could have a radical effect on category theory. Researchers in these subjects have been forced by the nature of the material to embrace "dagger-categories". I explain why in my article above, but I called them "*-categories" instead of dagger-categories. A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1. Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories. Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way! Once Andre told me some ideas about this, relating to the case of Hilb, but unfortunately I don't see that how they could apply to nCob. I was very interested at Mark Weber's reaction to this problem. He said, roughly, "So dagger-categories aren't really categories with extra structure. Okay: they're something else! And that's fine." (I'd be happy for him to correct my rough summary and make his point more precisely.) I like this bold attitude, especially coming from someone like Mark, who knows enough category theory to carry it off. This could lead to really new developments. Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
John Baez wrote in part:
A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1.
Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories.
Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way!
By default, there is a non-evil way to say it: Given a category C, a _non-evil dagger-category structure_ on C consists of a dagger-category C' and an equivalence F: C -> C' of categories. So one question is whether there is a less long-winded way to say that. Another question (which logically comes before the first question) is what is the right notion of equivalence of such structures. --Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Several people attempted to give a "non-evil" definition of a dagger category. Not much of this makes sense. Consider the following two categories: (a) the category of finite dimensional complex vector spaces and linear maps, and (b) the category of finite dimensional Hilbert spaces and linear maps. Clearly, they are equivalent categories. They have the same morphisms! Yet everyone knows that Hilbert spaces and complex vector spaces are not the same. For example, one can define unitary morphisms w.r.t. Hilbert spaces, but not w.r.t. complex vector spaces. The concept of "unitary" is itself "evil", because it is not preserved under isomorphism of objects in the category (b)! So whatever extra structure the category (b) has, which allows a definition of "unitary", must be evil. Transporting this along equivalences does not make any sense whatsoever. Specifically, take Toby's proposal, and consider two different objects A,B of (b) such that both A and B are two-dimensional Hilbert spaces. Let u:A->B be some non-unitary isomorphism. Then you can easily find an equivalence of categories which identifies both A and B with the two-dimensional vector space C^2, and which identifies u with the identity morphism on C^2. At this point, you have not equipped the category (a) with anything useful, because it does not induce a notion of unitary map on C^2. It is tempting to say that what is wrong with the category (b) is that the morphisms don't accurately reflect the structure of the spaces. Perhaps one would prefer to equip the category of finite dimensional Hilbert spaces with unitary maps. Or with self-adjoint maps. Or with isometries. Or with positive maps. The fact that there are so many possible choices, and neither is strong enough to express all the others internally, shows that this is not a good solution. One nice feature of the dagger structure is that it does allow all of the above to be expressed internally. So one gets lots of "evils" for the price of one! A sensible thing to do is to consider the category (b) of finite dimensional Hilbert spaces with linear maps, to be also *equipped*, as extra structure, with a distinguished lluf subcategory of isomorphisms (the "unitary") ones. There is a natural notion of equivalence between such categories-with-distinguished-subcategory (in particular, where each component of the natural isomorphisms FG -> id and GF -> id is required to lie in the subcategory). One can define a version of the dagger structure for such categories-with-distinguished-subcategory (in addition to the usual dagger axioms, one also must require that the notion of "unitary" induced by the dagger structure coincides with the distinguished subcategory that is a priori given). Observe that the dagger structure can be transported along such equivalence of categories-with-distinguished-subcategory. So the dagger definition is non-evil on categories-with-distinguished-subcategory. Unfortunately, the concept of a "distinguished subcategory" is itself evil, if one does not require the subcategory to contain all isomorphisms of the original category. So it seems that, to define the extra structure of Hilbert spaces (on top of vector spaces), one needs at least one "evil" concept, be it that of unitary maps or the dagger structure. -- Peter Toby Bartels wrote:
John Baez wrote in part:
A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1.
Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories.
Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way!
By default, there is a non-evil way to say it:
Given a category C, a _non-evil dagger-category structure_ on C consists of a dagger-category C' and an equivalence F: C -> C' of categories.
So one question is whether there is a less long-winded way to say that. Another question (which logically comes before the first question) is what is the right notion of equivalence of such structures.
--Toby
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Hi Bob, I just bounced the message to you, and here I am forwarding it again just in case. Strange that it got lost. Let me know if you get this. This logically precedes my message to Dusko, in which I say that I "state again" something that I first stated in this here message. -- Peter ----------------------------------------------------------------------
From selinger Wed Dec 30 10:52:47 2009 Subject: Re: categories: Re: Quantum computation and categories To: toby+categories@ugcs.caltech.edu Date: Wed, 30 Dec 2009 10:52:47 -0400 (AST) Cc: categories@mta.ca (categories)
Several people attempted to give a "non-evil" definition of a dagger category. Not much of this makes sense. Consider the following two categories: (a) the category of finite dimensional complex vector spaces and linear maps, and (b) the category of finite dimensional Hilbert spaces and linear maps. Clearly, they are equivalent categories. They have the same morphisms! Yet everyone knows that Hilbert spaces and complex vector spaces are not the same. For example, one can define unitary morphisms w.r.t. Hilbert spaces, but not w.r.t. complex vector spaces. The concept of "unitary" is itself "evil", because it is not preserved under isomorphism of objects in the category (b)! So whatever extra structure the category (b) has, which allows a definition of "unitary", must be evil. Transporting this along equivalences does not make any sense whatsoever. Specifically, take Toby's proposal, and consider two different objects A,B of (b) such that both A and B are two-dimensional Hilbert spaces. Let u:A->B be some non-unitary isomorphism. Then you can easily find an equivalence of categories which identifies both A and B with the two-dimensional vector space C^2, and which identifies u with the identity morphism on C^2. At this point, you have not equipped the category (a) with anything useful, because it does not induce a notion of unitary map on C^2. It is tempting to say that what is wrong with the category (b) is that the morphisms don't accurately reflect the structure of the spaces. Perhaps one would prefer to equip the category of finite dimensional Hilbert spaces with unitary maps. Or with self-adjoint maps. Or with isometries. Or with positive maps. The fact that there are so many possible choices, and neither is strong enough to express all the others internally, shows that this is not a good solution. One nice feature of the dagger structure is that it does allow all of the above to be expressed internally. So one gets lots of "evils" for the price of one! A sensible thing to do is to consider the category (b) of finite dimensional Hilbert spaces with linear maps, to be also *equipped*, as extra structure, with a distinguished lluf subcategory of isomorphisms (the "unitary") ones. There is a natural notion of equivalence between such categories-with-distinguished-subcategory (in particular, where each component of the natural isomorphisms FG -> id and GF -> id is required to lie in the subcategory). One can define a version of the dagger structure for such categories-with-distinguished-subcategory (in addition to the usual dagger axioms, one also must require that the notion of "unitary" induced by the dagger structure coincides with the distinguished subcategory that is a priori given). Observe that the dagger structure can be transported along such equivalence of categories-with-distinguished-subcategory. So the dagger definition is non-evil on categories-with-distinguished-subcategory. Unfortunately, the concept of a "distinguished subcategory" is itself evil, if one does not require the subcategory to contain all isomorphisms of the original category. So it seems that, to define the extra structure of Hilbert spaces (on top of vector spaces), one needs at least one "evil" concept, be it that of unitary maps or the dagger structure. -- Peter Toby Bartels wrote:
John Baez wrote in part:
A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1.
Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories.
Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way!
By default, there is a non-evil way to say it:
Given a category C, a _non-evil dagger-category structure_ on C consists of a dagger-category C' and an equivalence F: C -> C' of categories.
So one question is whether there is a less long-winded way to say that. Another question (which logically comes before the first question) is what is the right notion of equivalence of such structures.
--Toby
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Greetings all and thanks to John for the friendly provocation ... I was very interested at Mark Weber's reaction to this problem. He said,
roughly, "So dagger-categories aren't really categories with extra structure. Okay: they're something else! And that's fine." (I'd be happy for him to correct my rough summary and make his point more precisely.)
OK. First of all when thinking about cobordisms, or paths, or homotopies, the act of reversing orientation is fundamentally strictly involutive. So at first glance, it's not at all clear what would be gained by weakening in this case, despite the light that replacing equations by isomorphisms sheds on so many other mathematical situations. Algebraically also, it appears natural to think of the strict involutions as more fundamental. Just as categories are algebras of a very nice and easily described monad on the presheaf topos of graphs, "dagger categories" (I think the terminology "involutive category" would be better) are algebras of an analogous monad on the presheaf topos of involutive graphs. An involutive graph is a graph together with an involution on the set of edges which switches sources and targets. Formally the dagger category monad is obtained by a canonical lifting of the category monad through the forgetful functor from involutive graphs to graphs, so we have a canonical monad distributive law describing this situation. The observations of the previous paragraph generalise a lot and rather easily, and this encourages me to resist any urge to weaken the involutory aspects of the notion of dagger category. So the "something else" of John's post is that dagger categories are *involutive graphs* with structure, and their higher dimensional analogues are *involutive n-globular sets* with structure. So all the way up the dimensional ladder, regardless of how weak your higher compositions happen to be, if involutions (to model orientation reversals) are to be part of the picture, then I think they should be strict and strictly compatible with all the compositions and coherence data. For those still interested, I'll now give a few more details. First some background. In http://arxiv.org/abs/0909.4715 Michael Batanin, Denis-Charles Cisinski and I reformulated much of the "Batanin approach" to defining higher categories as the study of monads on categories of enriched graphs, particularly those that arise from multitensors. Briefly, given a category V, one can associate to any "distributive multitensor on V" (which is a lax monoidal structure on V such that the n-ary tensor product functor V^n-->V preserves coproducts in each variable), a monad on the category GV of graphs enriched in V. So for example this process takes the cartesian product for Set to the category monad on Graph. The operads used by Batanin to define weak higher categories, seen as certain monads on the presheaf topos G^n(Set) of n-globular sets, also arise in this way. One can also consider the category G_i(V) of involutive graphs enriched in V, and so begin to consider structures defined by monads on the presheaf topos (G_i)^n(Set) of what would be sensible to call "involutive n-globular sets". An involutive graph enriched in V is a V-graph X together with, for each pair of objects a,b from X, maps i_(a,b) : X(a,b) --> X(b,a) in V such that for all a,b, i_(b,a)i_(a,b) = identity. It is easy to verify that both processes V |-> GV and V |-> G_i(V) preserve presheaf toposes, so (G_i)^n(Set) really is a presheaf topos. To spell out the generalisation alluded to above, let E be a distributive multitensor on V, and write (as in the above paper) Gamma(E) for its associated monad on GV -- corollary(4.5) of our paper indicates an explicit formula. This formula is easily adapted to the involutive case to describe the monad Gamma_i(E) on G_i(V) and this is by definition a canonical lifting of Gamma(E) though the forgetful G_i(V)-->GV. In summary, for any higher categorical structure of interest, there is an involutive version (eg one can define involutive Gray categories), and from the above remarks we understand as much about the monads which describe them as we do their non-involutive counterparts, and moreover there's a canonical distributive law relating them. For me the interesting question now is how to adapt this to give an explicit description of monads which describe weak higher groupoids (with strictly involutive "inverse operations"). Steve Lack and I observed recently that ordinary groupoids are algebras for a monad on the category of involutive graphs, which arises via a *weak* distributive law in the sense of http://www.tac.mta.ca/tac/volumes/22/12/22-12abs.html between the category monad on Graph and the involutive graph monad on Graph, but I really don't see yet how this generalises. Best new years wishes to all, Mark Weber [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Several people attempted to give a "non-evil" definition of a dagger category. Not much of this makes sense. Consider the following two categories: (a) the category of finite dimensional complex vector spaces and linear maps, and (b) the category of finite dimensional Hilbert spaces and linear maps. Clearly, they are equivalent categories. They have the same morphisms! Yet everyone knows that Hilbert spaces and complex vector spaces are not the same. For example, one can define unitary morphisms w.r.t. Hilbert spaces, but not w.r.t. complex vector spaces. The concept of "unitary" is itself "evil", because it is not preserved under isomorphism of objects in the category (b)! So whatever extra structure the category (b) has, which allows a definition of "unitary", must be evil. Transporting this along equivalences does not make any sense whatsoever. Specifically, take Toby's proposal, and consider two different objects A,B of (b) such that both A and B are two-dimensional Hilbert spaces. Let u:A->B be some non-unitary isomorphism. Then you can easily find an equivalence of categories which identifies both A and B with the two-dimensional vector space C^2, and which identifies u with the identity morphism on C^2. At this point, you have not equipped the category (a) with anything useful, because it does not induce a notion of unitary map on C^2. It is tempting to say that what is wrong with the category (b) is that the morphisms don't accurately reflect the structure of the spaces. Perhaps one would prefer to equip the category of finite dimensional Hilbert spaces with unitary maps. Or with self-adjoint maps. Or with isometries. Or with positive maps. The fact that there are so many possible choices, and neither is strong enough to express all the others internally, shows that this is not a good solution. One nice feature of the dagger structure is that it does allow all of the above to be expressed internally. So one gets lots of "evils" for the price of one! A sensible thing to do is to consider the category (b) of finite dimensional Hilbert spaces with linear maps, to be also *equipped*, as extra structure, with a distinguished lluf subcategory of isomorphisms (the "unitary") ones. There is a natural notion of equivalence between such categories-with-distinguished-subcategory (in particular, where each component of the natural isomorphisms FG -> id and GF -> id is required to lie in the subcategory). One can define a version of the dagger structure for such categories-with-distinguished-subcategory (in addition to the usual dagger axioms, one also must require that the notion of "unitary" induced by the dagger structure coincides with the distinguished subcategory that is a priori given). Observe that the dagger structure can be transported along such equivalence of categories-with-distinguished-subcategory. So the dagger definition is non-evil on categories-with-distinguished-subcategory. Unfortunately, the concept of a "distinguished subcategory" is itself evil, if one does not require the subcategory to contain all isomorphisms of the original category. So it seems that, to define the extra structure of Hilbert spaces (on top of vector spaces), one needs at least one "evil" concept, be it that of unitary maps or the dagger structure. -- Peter Toby Bartels wrote:
John Baez wrote in part:
A dagger-category is a category C with a functor F: C -> C^{op} which is the identity on objects and has F^2 = 1.
Category theorists will note that the above definition is "evil", in the technical sense of that term: http://ncatlab.org/nlab/show/evil Namely, it imposes equations between objects, so we cannot transport a dagger-category structure along an equivalence of categories.
Often evil concepts (like the concept of "strict monoidal category") have non-evil counterparts (like the concept of "monoidal category"). But in this particular case I know no way to express the idea without equations between objects. Both Hilb and nCob are dagger-categories. This fact is important. Try saying it in a non-evil way!
By default, there is a non-evil way to say it:
Given a category C, a _non-evil dagger-category structure_ on C consists of a dagger-category C' and an equivalence F: C -> C' of categories.
So one question is whether there is a less long-winded way to say that. Another question (which logically comes before the first question) is what is the right notion of equivalence of such structures.
--Toby
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Happy New Year! Peter wrote: Consider the following two categories:
(a) the category of finite dimensional complex vector spaces and linear maps, and (b) the category of finite dimensional Hilbert spaces and linear maps.
Specifically, take Toby's proposal, and consider two different objects A,B of (b) such that both A and B are two-dimensional Hilbert spaces. Let u:A->B be some non-unitary isomorphism.
Using "u" to stand for a non-unitary morphism! Reminds me of the joke: Teacher: Suppose p is a prime number... Student: But what if it's not? Teacher: Well then it wouldn't be called "p", now, would it!
Then you can easily find an equivalence of categories which identifies both A and B with the two-dimensional vector space C^2, and which identifies u with the identity morphism on C^2. At this point, you have not equipped the category (a) with anything useful, because it does not induce a notion of unitary map on C^2.
Okay, that's a nice argument. I'm pretty sure Lurie gave me some similar argument: take a dagger-category, try to transport the structure along an equivalence of categories, and get something unacceptable. So it seems that, to define the extra structure of Hilbert spaces (on top of
vector spaces), one needs at least one "evil" concept, be it that of unitary maps or the dagger structure.
If this is really true (and I think it is), we're pushed towards Mark Weber's idea: dagger-categories are not best thought of as categories but rather something new, based on graphs-with-involution instead of graphs. Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Fred E.J. Linton wrote:
Peter Selinger offered the thought that, considering
... the category of finite dimensional complex vector spaces vs. the category of finite dimensional Hilbert spaces. They are equivalent ...
Hmmm ... you mean just *any* linear transformation is allowed between two Hilbert spaces?
In applications to quantum mechanics people really want to work with both unitary and self-adjoint operators, and often others as well. So they work with the category of finite-dimensional Hilbert spaces and *all* linear maps between these. As a mere category this is equivalent to the category of finite-dimensional vector spaces - so to understand the "Hilbertness" of Hilbert spaces, they introduce a dagger structure as well. (The infinite-dimensional case would introduce extra wrinkles, like unbounded self-adjoint operators. It's possible that only after we treat this case correctly can we declare that we know what's going on. Perhaps trying to treat both unitary and self-adjoint operators as morphisms in the same category is simply a bad idea. There are a lot of options worth exploring.) If so, I'm not so sure my Hilbert spaces are the same as yours :-) .
Indeed! If you treat Hilbert spaces as "sets with structure", the obvious morphisms are isometries - inner-product-preserving linear operators. But in quantum theory, Hilbert spaces are being used for something quite different. And so there's a struggle going on to understand this. Best, jb [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
John Baez wrote in part:
If you treat Hilbert spaces as "sets with structure", the obvious morphisms are isometries - inner-product-preserving linear operators. But in quantum theory, Hilbert spaces are being used for something quite different. And so there's a struggle going on to understand this.
Even in quantum theory, the obvious isomorphisms --that is, the notions of how one Hilbert space may be equivalent to another-- are invertible linear isometries, equivalently the unitary maps. To know what Hilbert spaces really "are", we only need to understand the groupoid of Hilbert spaces, which has ~unitary~ maps as morphisms. But we don't stop there; we look for a more interesting or useful category whose underlying groupoid (in an appropriate sense) is this groupoid. We could take the category whose morphisms are short linear maps; then the invertible morphisms are precisely the unitary maps. Or we could take the dagger category whose morphisms are bounded linear maps and with the usual adjoint as the dagger; the appropriate underlying groupoid in this context consists not of all invertible morphisms but only of those morphisms whose daggers are their inverses, which again are the unitary maps. (I leave open the problem of defining an appropriate structure on the category whose morphisms are all densely defined linear maps; in fact, I'm not even sure whether this is even a category. But this reduces to the previous case if we restrict to finite dimensions.) We might instead take the category whose morphisms are bounded linear maps, with no additional structure; but this gives us the ~wrong~ isomorphisms. So going only half way is no good here. --Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
John Baez wrote:
(The infinite-dimensional case would introduce extra wrinkles, like unbounded self-adjoint operators. It's possible that only after we treat this case correctly can we declare that we know what's going on. Perhaps trying to treat both unitary and self-adjoint operators as morphisms in the same category is simply a bad idea. There are a lot of options worth exploring.)
How about starting with rigged Hilbert space? If anything can restore your dagger that should. There's even a Wikipedia article on it; something on dagger categories would be a useful addition to that article. Vaughan [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Here is a bit of hyperbole. Hopefully entertaining. Suppose, hypothetically, that category theorist X had a close look at the definition of "inverse": morphisms f : A -> B and g : B -> A are inverses if fg = id_B and gf = id_A. Suppose that she makes the following argument: "The definition of inverse is really too strict. It requires an equation between objects, namely, the domain of f must equal the codomain of g, and vice versa. A natural thing to do would be to weaken the definition to replace this equality by an isomorphism." So what definition would she come up with? Definition. Let f : A -> B be a morphism. A *weak inverse* of f is given by the following data: (1) Objects A', B', and a morphism g : B' -> A' (2) an isomorphism a : A' -> A (3) an isomorphism b : B' -> B (4) such that the following diagram commutes: g A' <------- B' a | | b v f v A --------> B Everybody can see that this is nonsense. First, one must have a prior definition of isomorphism before one can define inverse in this way. But the definition of isomorphism depends on inverses, so this is circular. Second, each "weak inverse" in the above sense already gives rise to an ordinary inverse, namely a o g o (b^{-1}). Perhaps category theorist X would like to formulate this as a Coherence Lemma ("each weak inverse is canonically equivalent to a strict inverse"). But it is clearly nonsense nevertheless. Naive attempts to define a weak version of dagger structure fall into the same category. Recall the definition of a dagger structure on a category, namely a contravariant, involutive, identity-on-objects functor. Or in elementary terms: to each f : A -> B, associate some f+ : B -> A, such that f++ = f, (fg)+ = (g+)(f+), and id+ = id. Each category theorist (including myself) who sees this definition immediately dislikes the identity-on-objects part. The first instinct is to try to weaken it. But what would one come up with? After one or two failed attempts, it seems that the "correct" definition is the following: a contravariant functor (-)+, and for each object A a chosen unitary isomorphism a_A : A+ -> A, such that one has the following diagram (but note that it doesn't have to commute): f+ A+ <------- B+ a_A | | a_B [not assumed to commute] v f v A --------> B Plus, there should be some further requirement to replace the "involutive" condition (i.e., the obvious diagram involving f and f++ should commute), and perhaps a coherence condition or two. Note that a_A and a_B must be assumed to be unitary. The analogous definition where they are just isomorphisms does not work for a variety of reasons. For example, this is supposed to be a weakening of the strict situation, and identities are always unitary. The problem with any such definition is the same as for the "weak inverses" hyperbole above. First, to define dagger in this way, one must have a prior definition of "unitary", but the definition of "unitary" depends on "dagger", so this is circular. Second, given any weak dagger structure in this sense, it already induces a strict dagger structure, namely by using a_A o f+ o (a_B^{-1}) : B -> A as the strict dagger. One could again regard this as a coherence lemma, but it's clearly a pointless one. Actually, my leading example of "weak inverses", while ludicrous, is not entirely besides the point. One of the main reasons for considering dagger structure is so that we can define a morphism u : A -> B to be unitary if u+ is the inverse of u. Trying to say this with the "weak" dagger structure inevitably leads to weak inverses. In light of all this, I completely agree with Mark Weber that dagger structure should be strict and that is what we should live with. -- Peter [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Here is a bit of hyperbola. Hopefully entertaining. Suppose, hypothetically, that category theorist X had a close look at the definition of "inverse": morphisms f : A -> B and g : B -> A are inverses if fg = id_B and gf = id_A. Suppose that she makes the following argument: "The definition of inverse is really too strict. It requires an equation between objects, namely, the domain of f must equal the codomain of g, and vice versa. A natural thing to do would be to weaken the definition to replace this equality by an isomorphism." So what definition would she come up with? Definition. Let f : A -> B be a morphism. A *weak inverse* of f is given by the following data: (1) Objects A', B', and a morphism g : B' -> A' (2) an isomorphism a : A' -> A (3) an isomorphism b : B' -> B (4) such that the following diagram commutes: g A' <------- B' a | | b v f v A --------> B Everybody can see that this is nonsense. First, one must have a prior definition of isomorphism before one can define inverse in this way. But the definition of isomorphism depends on inverses, so this is circular. Second, each "weak inverse" in the above sense already gives rise to an ordinary inverse, namely a o g o (b^{-1}). Perhaps category theorist X would like to formulate this as a Coherence Lemma ("each weak inverse is canonically equivalent to a strict inverse"). But it is clearly nonsense nevertheless. Naive attempts to define a weak version of dagger structure fall into the same category. Recall the definition of a dagger structure on a category, namely a contravariant, involutive, identity-on-objects functor. Or in elementary terms: to each f : A -> B, associate some f+ : B -> A, such that f++ = f, (fg)+ = (g+)(f+), and id+ = id. Each category theorist (including myself) who sees this definition immediately dislikes the identity-on-objects part. The first instinct is to try to weaken it. But what would one come up with? After one or two failed attempts, it seems that the "correct" definition is the following: a contravariant functor (-)+, and for each object A a chosen unitary isomorphism a_A : A+ -> A, such that one has the following diagram (but note that it doesn't have to commute): f+ A+ <------- B+ a_A | | a_B [not assumed to commute] v f v A --------> B Plus, there should be some further requirement to replace the "involutive" condition (i.e., the obvious diagram involving f and f++ should commute), and perhaps a coherence condition or two. Note that a_A and a_B must be assumed to be unitary. The analogous definition where they are just isomorphisms does not work for a variety of reasons. For example, this is supposed to be a weakening of the strict situation, and identities are always unitary. The problem with any such definition is the same as for the "weak inverses" hyperbola above. First, to define dagger in this way, one must have a prior definition of "unitary", but the definition of "unitary" depends on "dagger", so this is circular. Second, given any weak dagger structure in this sense, it already induces a strict dagger structure, namely by using a_A o f+ o (a_B^{-1}) : B -> A as the strict dagger. One could again regard this as a coherence lemma, but it's clearly a pointless one. Actually, my leading example of "weak inverses", while ludicrous, is not entirely besides the point. One of the main reasons for considering dagger structure is so that we can define a morphism u : A -> B to be unitary if u+ is the inverse of u. Trying to say this with the "weak" dagger structure inevitably leads to weak inverses. In light of all this, I completely agree with Mark Weber that dagger structure should be strict and that is what we should live with. -- Peter
Here is a bit of hyperbole. Hopefully entertaining. Suppose, hypothetically, that category theorist X had a close look at the definition of "inverse": morphisms f : A -> B and g : B -> A are inverses if fg = id_B and gf = id_A. Suppose that she makes the following argument: "The definition of inverse is really too strict. It requires an equation between objects, namely, the domain of f must equal the codomain of g, and vice versa. A natural thing to do would be to weaken the definition to replace this equality by an isomorphism." So what definition would she come up with? Definition. Let f : A -> B be a morphism. A *weak inverse* of f is given by the following data: (1) Objects A', B', and a morphism g : B' -> A' (2) an isomorphism a : A' -> A (3) an isomorphism b : B' -> B (4) such that the following diagram commutes: g A' <------- B' a | | b v f v A --------> B Everybody can see that this is nonsense. First, one must have a prior definition of isomorphism before one can define inverse in this way. But the definition of isomorphism depends on inverses, so this is circular. Second, each "weak inverse" in the above sense already gives rise to an ordinary inverse, namely a o g o (b^{-1}). Perhaps category theorist X would like to formulate this as a Coherence Lemma ("each weak inverse is canonically equivalent to a strict inverse"). But it is clearly nonsense nevertheless. Naive attempts to define a weak version of dagger structure fall into the same category. Recall the definition of a dagger structure on a category, namely a contravariant, involutive, identity-on-objects functor. Or in elementary terms: to each f : A -> B, associate some f+ : B -> A, such that f++ = f, (fg)+ = (g+)(f+), and id+ = id. Each category theorist (including myself) who sees this definition immediately dislikes the identity-on-objects part. The first instinct is to try to weaken it. But what would one come up with? After one or two failed attempts, it seems that the "correct" definition is the following: a contravariant functor (-)+, and for each object A a chosen unitary isomorphism a_A : A+ -> A, such that one has the following diagram (but note that it doesn't have to commute): f+ A+ <------- B+ a_A | | a_B [not assumed to commute] v f v A --------> B Plus, there should be some further requirement to replace the "involutive" condition (i.e., the obvious diagram involving f and f++ should commute), and perhaps a coherence condition or two. Note that a_A and a_B must be assumed to be unitary. The analogous definition where they are just isomorphisms does not work for a variety of reasons. For example, this is supposed to be a weakening of the strict situation, and identities are always unitary. The problem with any such definition is the same as for the "weak inverses" hyperbole above. First, to define dagger in this way, one must have a prior definition of "unitary", but the definition of "unitary" depends on "dagger", so this is circular. Second, given any weak dagger structure in this sense, it already induces a strict dagger structure, namely by using a_A o f+ o (a_B^{-1}) : B -> A as the strict dagger. One could again regard this as a coherence lemma, but it's clearly a pointless one. Actually, my leading example of "weak inverses", while ludicrous, is not entirely besides the point. One of the main reasons for considering dagger structure is so that we can define a morphism u : A -> B to be unitary if u+ is the inverse of u. Trying to say this with the "weak" dagger structure inevitably leads to weak inverses. In light of all this, I completely agree with Mark Weber that dagger structure should be strict and that is what we should live with. -- Peter
participants (7)
-
John Baez -
Mark Weber -
Peter Selinger -
selinger -
selinger＠mathstat.dal.ca
-
Toby Bartels -
Vaughan Pratt