evil (fwd) Re: Quantum computation and categories
[yesterday john baez sent his message only to me, and i replied only to him. he actually meant to send it to the list, and encouraged me to resend the reply. i apologize for posting so much these days. -- dusko (in bed with a flu and a computer)] hi john, thanks for your note. the notion of evil is an interesting challenge in any context.
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!
let me try. DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is * self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X. LEMMA. Suppose that every object in CC comes with a Frobenius algebra structure. Then there are coherent natural isomorphisms PX-->X. PROOF. The Frobenius algebra structure induces ** ee_X : X (x) X ---> I ** hh_X : I---> X (x) X which make X-|X. the natural isomorphisms PX-->X are composed from the adjunction equipment (along the proof that an adjoint is unique up to a coherent iso). QED DEF. A strict dagger is a functor D:CC^op ---> CC obtained by transferring a dagger along the canonical isomorphisms from the lemma. COROLLARY. strict daggers are not evil: they are preserved under the equivalences. PROOF. daggers are obviously preserved. frobenius algebras are preserved. hence the canonical isomorphisms are preserved. FACT 1. a frobenius algebra structure on a hilbert space is just a choice of a basis. (hence we can a non-evil adjoint by first defining a preadjoint to be the conjugate of the dual operator, and then transferring along the isomorphism X^* ---> X induced by the chosen basis.) FACT 2. a frobenius algebra structure in nCob is the underwear structure. -- dusko PS the hope is that this provides a nonevil view of the daggers in FHilb and nCob. i guess the general suggestion might be to define dagger compact structure by a self-adjoint equivalence, plus a requirement that every object admits a frobenius algebra structure. that structure is not evil, and it is carried by all examples considered so far. i don't think that there is a general solution for the problem of evil in categories: we can only pin down a particular object, as an element of an isomorphism class, in the lucky cases when there is some additional structure that characterizes it. but in general, evil exists. every functor can be factored as an identity-on-the-objects-functor (ioof), followed by an embedding. the embedding is good, but ioofs are evil, and i think that they deserve their name. lord knows how much we use them. in a sense, category theory can be distinguished from set theory by the presence of evil. [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear all, I apologize for sending out a third (long) email about dagger categories today. There have been some proposals on this list for defining "non-evil" analogues of dagger structure. None of them make sense, and I do feel an obligation to rebut them one by one. It's easy to give the subject two minutes of thought and produce some half-baked ideas, but unfortunately it takes much longer to explain why the ideas don't work. I am afraid that if I don't nib this in the bud, I will have to read it in referee's reports for the next 10 years ("why isn't Selinger using the non-strict dagger structure proposed by so-and-so...?"). I imagine most readers of this list are tired of this subject, and I invite you to ignore the rest of this email. Before I dissect Dusko's proposed definition, let me repeat the main reason why *every* such definition is doomed to failure. It is a fact that the notion of dagger, however defined, intrinsically does not transport along equivalences. This is a hard fact, in the sense that it is a consequence of examples, rather than definitions. There is no way to fudge the definitions to make this fact go away, unless one changes the definitions so radically that they no longer fit the fundamental example. The fundamental example is the category of finite dimensional complex vector spaces vs. the category of finite dimensional Hilbert spaces. They are equivalent, the latter has a dagger structure, and the former does not. For this argument, it is irrelevant how dagger structure is defined (strict, weak, abstract, concrete...): all that is required is that the definition is strong enough to yield a notion of unitary map, and that the latter coincides with the "usual" notion in the category of Hilbert spaces. Here is the specific rebuttal of Dusko's proposal.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
Assuming here that the monoidal category is symmetric monoidal, this is precisely the definition of a compact closed structure. The first two conditions are redundant. The whole point of Abramsky and Coecke's work on dagger categories was to explain, in categorical terms, that the adjoint (i.e., dagger) of a linear function f:A->B is *not* the same as the transpose. The adjoint goes B -> A, whereas the transpose goes B* -> A*. This is something people used to be confused about. Abramsky and Coecke cleared up the confusion; the above definition reintroduces it. To remove the distinction between a morphism B* -> A* and a morphism B -> A, Dusko now assumes that each object A is equipped with a chosen isomorphism A* -> A. (He actually assumes chosen Frobenius algebra structures, which is a stonger assumption, but only the isomorphisms are needed for the present purpose). With this assumption, given a map f : A -> B, we can take the transpose f* : B* -> A*, and then compose it with the given isomorphisms to get a map B -> B* -> A* -> A. This is of the type required for a (strict) dagger structure. There are many things wrong with this: 1) The main example, which is the category of finite dimensional Hilbert spaces, does not have the structure Dusko requires. There are no such chosen isomorphisms or Frobenius structures or chosen bases. However, to continue the argument, let's assume that we have chosen such additional structure in some arbitrary way. 2) In the main example, the category of finite dimensional Hilbert spaces, Dusko's definition does not coincide with reality, i.e., the *actual* definition of the adjoint of a linear map. No matter how the bases are chosen, the resulting map B -> B* -> A* -> A is *not* the adjoint of f for most f. Indeed, when written as a matrix in the chosen basis, this is still the transpose, and not the adjoint, of the matrix of f. 3) In any case, the structure of "having a chosen Frobenius structure on each object" is itself an evil structure on categories. Quite clearly, there will be some isomorphisms of the category that don't preserve the Frobenius structure. There will be equivalences of categories sending those isomorphisms to identities. Identities always preserve Frobenius structure, so therefore Frobenius structure does not transport along such equivalences. The same argument shows that the structure of "having a chosen isomorphism A* -> A on each object" is evil too. In summary, Dusko's definition does not coincide with the intended example, and is evil anyway, so doesn't solve the problem. -- Peter Dusko Pavlovic wrote:
[yesterday john baez sent his message only to me, and i replied only to him. he actually meant to send it to the list, and encouraged me to resend the reply. i apologize for posting so much these days. -- dusko (in bed with a flu and a computer)]
hi john,
thanks for your note. the notion of evil is an interesting challenge in any context.
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!
let me try.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
LEMMA. Suppose that every object in CC comes with a Frobenius algebra structure. Then there are coherent natural isomorphisms PX-->X.
PROOF. The Frobenius algebra structure induces
** ee_X : X (x) X ---> I ** hh_X : I---> X (x) X
which make X-|X. the natural isomorphisms PX-->X are composed from the adjunction equipment (along the proof that an adjoint is unique up to a coherent iso). QED
DEF. A strict dagger is a functor D:CC^op ---> CC obtained by transferring a dagger along the canonical isomorphisms from the lemma.
COROLLARY. strict daggers are not evil: they are preserved under the equivalences.
PROOF. daggers are obviously preserved. frobenius algebras are preserved. hence the canonical isomorphisms are preserved.
FACT 1. a frobenius algebra structure on a hilbert space is just a choice of a basis. (hence we can a non-evil adjoint by first defining a preadjoint to be the conjugate of the dual operator, and then transferring along the isomorphism X^* ---> X induced by the chosen basis.)
FACT 2. a frobenius algebra structure in nCob is the underwear structure.
-- dusko
PS the hope is that this provides a nonevil view of the daggers in FHilb and nCob. i guess the general suggestion might be to define dagger compact structure by a self-adjoint equivalence, plus a requirement that every object admits a frobenius algebra structure. that structure is not evil, and it is carried by all examples considered so far.
i don't think that there is a general solution for the problem of evil in categories: we can only pin down a particular object, as an element of an isomorphism class, in the lucky cases when there is some additional structure that characterizes it. but in general, evil exists. every functor can be factored as an identity-on-the-objects-functor (ioof), followed by an embedding. the embedding is good, but ioofs are evil, and i think that they deserve their name. lord knows how much we use them.
in a sense, category theory can be distinguished from set theory by the presence of evil.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
Dear Dusko, your proposed definition of a non-evil dagger structure is a nice try, but it doesn't work at all. Before I dissect your definition, let me state again the reason why *every* such definition will fail. It is a hard fact that the notion of dagger, however defined, intrinsically does not transport along equivalences. By "hard fact", I mean that it is a consequence of examples, rather than definitions. There is no way to fudge the definitions to make this fact go away, unless one changes the definitions so radically that they no longer fit the fundamental example. The fundamental example is the category of finite dimensional complex vector spaces vs. the category of finite dimensional Hilbert spaces. They are equivalent, the latter has a dagger structure, and the former does not. This shows that the notion is evil. For this argument, it is irrelevant how dagger structure is actually defined (strict, weak, abstract, concrete...): all that is required is that the definition is strong enough to yield a notion of unitary map, and that this unitary notion coincides with the "usual" one in the category of Hilbert spaces. Now let me comment on your definitions in detail.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
Assuming here that the category is symmetric monoidal, this is precisely the definition of a compact closed structure. The first two conditions are redundant. The point of Abramsky and Coecke's work on dagger categories was to explain, in categorical terms, that the adjoint (i.e., dagger) of a linear function f:A->B is *not* the same as the transpose. The adjoint goes B -> A, whereas the transpose goes B* -> A*. This is something people used to be confused about. Abramsky and Coecke cleared up the confusion; the above definition reintroduces it. To remove the distinction between a morphism B* -> A* and a morphism B -> A, you next assume that each object A is equipped with a chosen isomorphism A* -> A. (You actually assume chosen Frobenius algebra structures, which is a stonger assumption, but only the isomorphisms are needed for the present purpose). With this assumption, given a map f : A -> B, we can take the transpose f* : B* -> A*, and then compose it with the given isomorphisms to get a map B -> B* -> A* -> A. This is of the type required for a (strict) dagger structure. There are a number of things wrong with this: 1) The main example, which is the category of finite dimensional Hilbert spaces, does not have the structure you require. It isn't equipped with chosen Frobenius structures (equivalently chosen bases), nor with chosen isomorphisms A* -> A. However, to continue the argument, let's assume that we have arbitrarily chosen such additional structure. 2) In the main example, the category of finite dimensional Hilbert spaces, your definition does not coincide with reality. Namely, the *actual* definition of the adjoint of a linear map does not coincide with what one gets as the result of your definition. To see this, assume chosen bases, and note that the matrix of the map B -> B* -> A* -> A is exactly the transpose of the matrix of f : A -> B, in the given bases of A and B. On the other hand, the matrix of f+ : B -> A is the adjoint. 3) Moreover, contrary to what you wrote, the structure of "having a chosen Frobenius structure on each object" is itself an evil structure on categories. Namely, there will be some isomorphisms of the category that don't preserve the Frobenius structure (think linear map that does not preserve the chosen bases). Choose one such isomorphism s : U -> V, and construct an equivalence F to some other category such that the chosen isomorphism is sent to an identity. By transporting the Frobenius structure along F, you end up with two different Frobenius structures on F(U)=F(V). So there is no coherent way to transport. The same argument shows that the structure of "having a chosen isomorphism A* -> A on each object" is also evil. In summary, your definition does not coincide with the intended example (linear adjoints in Hilbert spaces), and ends up being evil anyway, so doesn't solve the problem. It also assumes too much structure (for example, the usual definition of a dagger category neither requires a monoidal structure nor a closed one. It works on any category). I hope we can agree that, to capture something essential about Hilbert spaces, some amount of evil structure is required, and we should embrace the evil definition and live with it. In fact, I am surprised that there are not more well-known examples of evil structures in category theory. In principle, any structure that allows the definition of a distinguished subcategory of isomorphisms (in this case, the unitary ones) should be evil. Does anybody know further examples? -- Peter Dusko Pavlovic wrote:
[yesterday john baez sent his message only to me, and i replied only to him. he actually meant to send it to the list, and encouraged me to resend the reply. i apologize for posting so much these days. -- dusko (in bed with a flu and a computer)]
hi john,
thanks for your note. the notion of evil is an interesting challenge in any context.
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!
let me try.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
LEMMA. Suppose that every object in CC comes with a Frobenius algebra structure. Then there are coherent natural isomorphisms PX-->X.
PROOF. The Frobenius algebra structure induces
** ee_X : X (x) X ---> I ** hh_X : I---> X (x) X
which make X-|X. the natural isomorphisms PX-->X are composed from the adjunction equipment (along the proof that an adjoint is unique up to a coherent iso). QED
DEF. A strict dagger is a functor D:CC^op ---> CC obtained by transferring a dagger along the canonical isomorphisms from the lemma.
COROLLARY. strict daggers are not evil: they are preserved under the equivalences.
PROOF. daggers are obviously preserved. frobenius algebras are preserved. hence the canonical isomorphisms are preserved.
FACT 1. a frobenius algebra structure on a hilbert space is just a choice of a basis. (hence we can a non-evil adjoint by first defining a preadjoint to be the conjugate of the dual operator, and then transferring along the isomorphism X^* ---> X induced by the chosen basis.)
FACT 2. a frobenius algebra structure in nCob is the underwear structure.
-- dusko
PS the hope is that this provides a nonevil view of the daggers in FHilb and nCob. i guess the general suggestion might be to define dagger compact structure by a self-adjoint equivalence, plus a requirement that every object admits a frobenius algebra structure. that structure is not evil, and it is carried by all examples considered so far.
i don't think that there is a general solution for the problem of evil in categories: we can only pin down a particular object, as an element of an isomorphism class, in the lucky cases when there is some additional structure that characterizes it. but in general, evil exists. every functor can be factored as an identity-on-the-objects-functor (ioof), followed by an embedding. the embedding is good, but ioofs are evil, and i think that they deserve their name. lord knows how much we use them.
in a sense, category theory can be distinguished from set theory by the presence of evil.
Dear Dusko, your proposed definition of a non-evil dagger structure is a nice try, but it doesn't work at all. Before I dissect your definition, let me state again the reason why *every* such definition will fail. It is a hard fact that the notion of dagger, however defined, intrinsically does not transport along equivalences. By "hard fact", I mean that it is a consequence of examples, rather than definitions. There is no way to fudge the definitions to make this fact go away, unless one changes the definitions so radically that they no longer fit the fundamental example. The fundamental example is the category of finite dimensional complex vector spaces vs. the category of finite dimensional Hilbert spaces. They are equivalent, the latter has a dagger structure, and the former does not. This shows that the notion is evil. For this argument, it is irrelevant how dagger structure is actually defined (strict, weak, abstract, concrete...): all that is required is that the definition is strong enough to yield a notion of unitary map, and that this unitary notion coincides with the "usual" one in the category of Hilbert spaces. Now let me comment on your definitions in detail.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
Assuming here that the category is symmetric monoidal, this is precisely the definition of a compact closed structure. The first two conditions are redundant. The point of Abramsky and Coecke's work on dagger categories was to explain, in categorical terms, that the adjoint (i.e., dagger) of a linear function f:A->B is *not* the same as the transpose. The adjoint goes B -> A, whereas the transpose goes B* -> A*. This is something people used to be confused about. Abramsky and Coecke cleared up the confusion; the above definition reintroduces it. To remove the distinction between a morphism B* -> A* and a morphism B -> A, you next assume that each object A is equipped with a chosen isomorphism A* -> A. (You actually assume chosen Frobenius algebra structures, which is a stonger assumption, but only the isomorphisms are needed for the present purpose). With this assumption, given a map f : A -> B, we can take the transpose f* : B* -> A*, and then compose it with the given isomorphisms to get a map B -> B* -> A* -> A. This is of the type required for a (strict) dagger structure. There are a number of things wrong with this: 1) The main example, which is the category of finite dimensional Hilbert spaces, does not have the structure you require. It isn't equipped with chosen Frobenius structures (equivalently chosen bases), nor with chosen isomorphisms A* -> A. However, to continue the argument, let's assume that we have arbitrarily chosen such additional structure. 2) In the main example, the category of finite dimensional Hilbert spaces, your definition does not coincide with reality. Namely, the *actual* definition of the adjoint of a linear map does not coincide with what one gets as the result of your definition. To see this, assume chosen bases, and note that the matrix of the map B -> B* -> A* -> A is exactly the transpose of the matrix of f : A -> B, in the given bases of A and B. On the other hand, the matrix of f+ : B -> A is the adjoint. 3) Moreover, contrary to what you wrote, the structure of "having a chosen Frobenius structure on each object" is itself an evil structure on categories. Namely, there will be some isomorphisms of the category that don't preserve the Frobenius structure (think linear map that does not preserve the chosen bases). Choose one such isomorphism s : U -> V, and construct an equivalence F to some other category such that the chosen isomorphism is sent to an identity. By transporting the Frobenius structure along F, you end up with two different Frobenius structures on F(U)=F(V). So there is no coherent way to transport. The same argument shows that the structure of "having a chosen isomorphism A* -> A on each object" is also evil. In summary, your definition does not coincide with the intended example (linear adjoints in Hilbert spaces), and ends up being evil anyway, so doesn't solve the problem. It also assumes too much structure (for example, the usual definition of a dagger category neither requires a monoidal structure nor a closed one. It works on any category). I hope we can agree that, to capture something essential about Hilbert spaces, some amount of evil structure is required, and we should embrace the evil definition and live with it. In fact, I am surprised that there are not more well-known examples of evil structures in category theory. In principle, any structure that allows the definition of a distinguished subcategory of isomorphisms (in this case, the unitary ones) should be evil. Does anybody know further examples? -- Peter Dusko Pavlovic wrote:
[yesterday john baez sent his message only to me, and i replied only to him. he actually meant to send it to the list, and encouraged me to resend the reply. i apologize for posting so much these days. -- dusko (in bed with a flu and a computer)]
hi john,
thanks for your note. the notion of evil is an interesting challenge in any context.
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!
let me try.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
LEMMA. Suppose that every object in CC comes with a Frobenius algebra structure. Then there are coherent natural isomorphisms PX-->X.
PROOF. The Frobenius algebra structure induces
** ee_X : X (x) X ---> I ** hh_X : I---> X (x) X
which make X-|X. the natural isomorphisms PX-->X are composed from the adjunction equipment (along the proof that an adjoint is unique up to a coherent iso). QED
DEF. A strict dagger is a functor D:CC^op ---> CC obtained by transferring a dagger along the canonical isomorphisms from the lemma.
COROLLARY. strict daggers are not evil: they are preserved under the equivalences.
PROOF. daggers are obviously preserved. frobenius algebras are preserved. hence the canonical isomorphisms are preserved.
FACT 1. a frobenius algebra structure on a hilbert space is just a choice of a basis. (hence we can a non-evil adjoint by first defining a preadjoint to be the conjugate of the dual operator, and then transferring along the isomorphism X^* ---> X induced by the chosen basis.)
FACT 2. a frobenius algebra structure in nCob is the underwear structure.
-- dusko
PS the hope is that this provides a nonevil view of the daggers in FHilb and nCob. i guess the general suggestion might be to define dagger compact structure by a self-adjoint equivalence, plus a requirement that every object admits a frobenius algebra structure. that structure is not evil, and it is carried by all examples considered so far.
i don't think that there is a general solution for the problem of evil in categories: we can only pin down a particular object, as an element of an isomorphism class, in the lucky cases when there is some additional structure that characterizes it. but in general, evil exists. every functor can be factored as an identity-on-the-objects-functor (ioof), followed by an embedding. the embedding is good, but ioofs are evil, and i think that they deserve their name. lord knows how much we use them.
in a sense, category theory can be distinguished from set theory by the presence of evil.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
hi peter, happy new year! may the daggers over hilbert spaces be the worst evil cast upon us :) but i think that this "defense" view of evil suggests that you may be missing the point. 1) THE PROBLEM OF EVIL if someone gives you two big complicated hilbert spaces, or two big complicated groups --- how do you decide whether they are the same? what does it mean that to be the same group? well, one thing you could try is to map the elements of one to the elements of the other one. this may give you an isomorphism. OR you may look at the actual presentations, say of the group structures that they gave you, and see whether these are completely equal. if you are extremely lucky, the two groups may be given by the same equational presentation. otherwise, if you live in a set theoretic universe, each of the groups would be given to you as a set, and the two sets can be equal, or not. in a computer system, each of the groups would be given as a software module, and they may, or may not be identical as executable binaries. the main problem with this is that the various implementation conventions need to be consistent and interoperable. i think it was peter freyd who once asked something like: "How can you tell that the set corresponding to the Monster Group is not the same as the set corresponding to an initial segment of the number pi?" the same question applies to the binaries, that may represent an executable group operation, or a piece of data in another encoding. note that the problem is NOT a mere philosophic disagreement between a categorical/structuralist and a set-theoretical/positivist view of math. it is an eminently PRACTICAL problem of computation. every crypto system consists of some groups. all these groups are implemented. some attacks depend on the implementations. other attacks only depend on the structure of a group, and apply to all implementations. the latter attacks are more dangerous, but easier to eliminate --- by avoiding all evil definitions. the former attacks cannot be completely eradicated: at the end of the day, every new implementation opens some new avenues of attack. ((the distinction between the evil and the non-evil definitions is becoming a big deal in cryptography, since mixing them led to some awkward attacks. eg, one of the most standardized key agreement protocols, ECMQV, is all in terms picard groups --- and then at one point it suddenly truncates a key from 160 to 80 bits. which is of course evil. this led to an attack. and this protocol is "critical for national security" and brings about $50M annyally just to one company...)) no one is proposing to eradicate evil. like other things in science, evil is neither good mor bad; it's just there. our goal should be to understand it. 2) EVIL IN HILBERT SPACES john baez asked if we can define the dagger structure of FHilb and nCob in a non-evil way. i think that the structure that i described achieves that goal. [[i am sorry if the rest of this gets longer than desirable, but since peter "dissected" my post, the code of flames requires a clarification. pls skip or enjoy.]]
*every* such definition will fail. It is a hard fact that the notion of dagger, however defined, intrinsically does not transport along equivalences. By "hard fact", I mean that it is a consequence of examples, rather than definitions.
the fact that an operation does not transport on the nose does not mean that it is impossible to find an isomorphic copy that will be preserved. that is what i proposed.
The fundamental example is the category of finite dimensional complex vector spaces vs. the category of finite dimensional Hilbert spaces. They are equivalent, the latter has a dagger structure, and the former does not. This shows that the notion is evil.
i am sorry if i am being extremely stupid, but how does this example differ from saying: "ordered group of integers is equivalent as a poset with the ordered ring of integers; the latter has multiplication and the former does not"? what do i learn from the fact that an algebraic operation (inner product, multiplication...) not specified in a signature, turns out to be derivable?
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
Assuming here that the category is symmetric monoidal, this is precisely the definition of a compact closed structure. The first two conditions are redundant.
sorry: the word "dinaturals" should be omitted. i corrected this after the original post. i am sorry about the confusion. if e_X and h_X happen to be dinatural, then P is just the star functor. in general, all we know about P is that it is a functor whose object part maps each object to some dual. the duals are determined up to isomorphism; any will do.
The point of Abramsky and Coecke's work on dagger categories was to explain, in categorical terms, that the adjoint (i.e., dagger) of a linear function f:A->B is *not* the same as the transpose.
except in the cases when it is, eg in Rel etc.
The adjoint goes B -> A, whereas the transpose goes B* -> A*. This is something people used to be confused about. Abramsky and Coecke cleared up the confusion; the above definition reintroduces it.
oh this was nice: people were confused, the confusion got cleared up, the period of enlightment ensued. but the story never ends, as we can always refine the picture. the point of evil is that your first sentence in the above paragraph does not refer to anything that can be stated in categorical terms. if i give you B and B*, how do you really know which is which? you look for a star? think about it: what do you need to be able to really tell when they are equal and when not?
There are a number of things wrong with this:
1) The main example, which is the category of finite dimensional Hilbert spaces, does not have the structure you require. It isn't equipped with chosen Frobenius structures (equivalently chosen bases), nor with chosen isomorphisms A* -> A.
there is no need for the *chosen* ones. the entire subject of linear algebra is based on the assumption that every space has *a* basis. that means that every hilbert space has *a* frobenius structure. non-canonical, and not preserved by the morphisms of the category.
2) In the main example, the category of finite dimensional Hilbert spaces, your definition does not coincide with reality. Namely, the *actual* definition of the adjoint of a linear map does not coincide with what one gets as the result of your definition. To see this, assume chosen bases, and note that the matrix of the map B -> B* -> A* -> A is exactly the transpose of the matrix of f : A -> B, in the given bases of A and B. On the other hand, the matrix of f+ : B -> A is the adjoint.
this is not true. maybe you used the dinaturality of the initial (overconstrained) definition P in your calculation.
3) Moreover, contrary to what you wrote, the structure of "having a chosen Frobenius structure on each object" is itself an evil structure on categories. [snip] Frobenius structures on F(U)=F(V). So there is no coherent way to transport. The same argument shows that the structure of "having a chosen isomorphism A* -> A on each object" is also evil.
i don't think that i could have required a *chosen structure* at any point, even under torture, or coherent transport, or canonical isomorphisms. all of that is in the eye of the beholder. i was talking about the actual practice of linear algebra: spaces have bases, the bases are not unique, nor preserved under the morphisms. in the finite case, the isomoprhisms B~B* are not natural, but the non-canonical ones are available when needed. -- my only point was that this can be used to avoid evil. (this was already used in our work on dagger monoidal structuralism.) i would be the last person to suggest that a simple evil structure should be *replaced* by a less simple non-evil structure. i use evil as much as everyone else, and more. but it may be useful (and an interesting exercise) to observe that a particular evil structure may be isomorphic to something non-evil, and that it can be derived from it. sorry again about clogging everyones holiday mailboxes. i hope that peter and i won't seriously annoy each other. lets stop defending things, or taking ouresleves too seriously. we do math, and the damage to the environment is minimal. and i think i am going to stop posting for a while. with the very best wishes to all, -- dusko
-- Peter
Dusko Pavlovic wrote:
[yesterday john baez sent his message only to me, and i replied only to him. he actually meant to send it to the list, and encouraged me to resend the reply. i apologize for posting so much these days. -- dusko (in bed with a flu and a computer)]
hi john,
thanks for your note. the notion of evil is an interesting challenge in any context.
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!
let me try.
DEF. Let CC be a monoidal category. a *dagger* on CC is a functor P: CC^op ---> CC which is
* self-adjoint * equivalence * given together with the dinaturals ** e_X : X (x) PX ---> I ** h_X : I--->PX (x) X which make PX -| X.
... [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
but in general, evil exists. every functor can be factored as an identity-on-the-objects-functor (ioof), followed by an embedding. the embedding is good, but ioofs are evil, and i think that they deserve their name. lord knows how much we use them.
An ioof is 'evil' in a subtly different way to what was discussed, in my opinion, in that the property of being such a functor is not invariant under natural isomorphism. This is then really a 2-categorical notion of evil. Are there many examples/other commonly used properties of functors that are evil in this way? Happy new year David [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (4)
-
David Roberts -
Dusko Pavlovic -
selinger -
selinger＠mathstat.dal.ca