52
$\begingroup$

Recall that a dagger category is a category equipped with an involution $*:Hom(x,y)\to Hom(y,x)$ that satisfies $f^{**}=f$ and $f^* g^*=(gf)^*$. A prominent example of a dagger category is the category of Hilbert spaces and continuous linear maps.


Now, dagger categories are evil!
For example, here's a quote from the Nlab:

"Note that regarded as an extra structure on categories, a †-structure is evil, since it imposes equations on objects."

This is not just a little thing. It's a fundamental philosophical problem with category theory: category theory does not seem to be able to cope with this rather important category-theory-related notion which are dagger categories.

Also, because of this buit-in evilness, there's a whole bunch of very familiar concepts that one cannot apply to dagger categories without rethinking everything very, very carefully from the beginning: equivalences, limits, colimits, adjoint functors, duals, algebra objects, etc...

Here's another quote:

"It is possible that this problem will force a change in thinking in either the concept of the principle of equivalence or our thinking in quantum theory."

and yet another one:

"Often concepts violating the principle of equivalence (like the concept of “strict monoidal category”) have equivalence-invariant counterparts (like the concept of “monoidal category”). But in this particular case there appears to be no known way to express the idea without equations between objects."

Now here's my question:

Question: Can one improve the above "there appears to be no known way to express the idea without equations between objects" to "there is no way to express the idea without equations between objects"?

I expect dagger categories to be truly evil (in some yet-to-be-defined technical sense of "evil"). Having a proof of that fact might be very informative, and would at least force us to define the term "evil" at a mathematical level of precision.

$\endgroup$
  • 6
    $\begingroup$ I don't think the evil/non-evil distinction has anything to do with the fact that it is difficult to define the classical categorical concept like limit or co-limit in dagger categories: $C^*$-categories are dagger Banach categories satisfying an analogue of the $C^*$-identity, which happen to have a non-evil definition among categories enriched in Banach spaces (essentially because a Banach algebra can only have one $*$-operation making it into a $C^*$-algebra) but it is still very difficult to define what is a limit or a co-limit or an adjoint functor in a $C^*$-category... $\endgroup$ – Simon Henry Oct 5 '15 at 10:33
  • 10
    $\begingroup$ I found this post on the category theory list: permalink.gmane.org/gmane.science.mathematics.categories/5459 It gives a precise possible definition of what would be non-evil structures and proves that there is no reasonable weakening of Dagger category that can be such a non-evil structure. Maybe it will be interesting for you... $\endgroup$ – Simon Henry Oct 5 '15 at 12:09
  • 17
    $\begingroup$ I think the lesson is that dagger categories are not really categories. $\endgroup$ – Qiaochu Yuan Oct 5 '15 at 16:11
  • 12
    $\begingroup$ It is unfortunate that your question perpetuates the `evil' terminology, which is very bad terminology in my opinion. This terminology has been abandoned in many circles in favor of more suitable descriptive mathematical terms. The n-lab, for example, now redirects 'evil' to the 'principle of equivalence', which seems to get at the heart of the desired issue. The old terminology was once a bad inside joke, but please don't continue to use this archaic term. Can you omit it from the question? $\endgroup$ – Joel David Hamkins Oct 5 '15 at 23:30
  • 7
    $\begingroup$ I don't think there is any harm in the word "evil". Any mathematician knows that there is no moral dimension to mathematics, and that therefore "evil" is tongue-in-cheek. Such word choices are just symptoms of our attempts to map abstract mathematical concepts to concrete intuitive terms. There are lots of examples for this phenomenon, like sexy primes, or countless examples of defining certain properties as "good" or "bad". $\endgroup$ – Manuel Bärenz Sep 2 '16 at 13:56
37
$\begingroup$

I will have another go at arguing that dagger-categories are not evil.

Let’s look at a simpler case first. Consider the property “$1 \in X$” on sets. As a property of abstract sets, this is evil: it’s not invariant under isomorphism, e.g. any iso $\{1,2\} \cong \{2,3\}$.

But it is manifestly non-evil as a property of, say, “sets equipped with an injection to $\mathbb{N}$”. Looking at this gives a non-evil structure on abstract sets: “an injection $i : X \to \mathbb{N}$, such that $1 \in \mathrm{im}\ i$”.

Ah (you may say) so if this is non-evil, it can’t reflect our original idea correctly: it would have to transfer along that $\{1,2\} \cong \{2,3\}$. But that’s not such a clear-cut complaint. As a structure on abstract sets, it does transfer along that isomorphism. But we were thinking of them from the start not just as abstract sets, but as subsets of $\mathbb{N}$, i.e. as already equipped implicitly with injections to $\mathbb{N}$. Considered as such, one of them contains $1$ and the other doesn’t; and there’s no isomorphism between them which commutes with those injections.

Summing up: “containing 1” is certainly non-evil as a property of “sets with a mono to $\mathbb{N}$”. This induces a non-evil property/structure on abstract sets which you may or may not agree matches our original idea, because it requires considering different monos to $\mathbb{N}$ besides the ones we were already (implicitly) thinking of.

Now, back to dagger-categories. It seems reasonable that dagger-categories are evil when regarded as structure on categories. The post by Peter Selinger linked by Simon Henry argues this quite persuasively: proving a specific no-go theorem, showing there can exist no notion of dagger-structure satisfying certain desirable properties.

However, structure on categories is not the only way to look at dagger-categories. They can instead be seen as structure on “pairs of categories connected by a faithful and essentially surjective functor $i : \mathbf{C}_u \to \mathbf{C}$”. (Full definition below.)

You may be thinking: this can’t be right, because it induces a non-evil structure on categories (“equip with a fully faithful inclusion from some other category, and then the dagger-structure”) which would violate Selinger’s no-go argument. However, it doesn’t: this structure doesn’t allow a definition of unitary maps in the sense Selinger’s argument assumes. Given $A, B \in \mathbf{C}_u$, we can say a map $iA \to iB$ is unitary if it’s the image of some map $A \to B$. But given just $A, B \in \mathbf{C}$, this unitariness isn’t well-defined for $f : A \to B$; different ways of expressing $A$ as $iA'$ and $B$ as $iB'$ might give different answers as to whether $f$ is unitary.

Expressed in this form, transferring the “weak dagger structure” on $\mathbf{fdHilb}$ along the equivalence to $\mathbf{fdVect}$ yields a weak dagger structure where the functor $i$ is not injective on objects. Selinger’s argument shows that something like this is unavoidable.

Summing up again: dagger-structure is certainly not evil when viewed as a structure on “categories with a distinguished faithful, ess. surj. inclusion”. This gives a definition of weak dagger structure as a non-evil structure on categories, which you may or may not accept, because it requires us to loosen up our original expectation that the “subcategory” of unitary maps should be literally bijective on objects, i.e. to go beyond the kind of “subcategories” we were originally thinking of.


Full definition: a weak dagger category may be taken to consist of:

  • a category $\newcommand{\C}{\mathbf{C}}\C$;
  • a groupoid $\C_u$, with a faithful and essentially surjective functor $i : \C_u \to \C$;
  • a functor $\dagger : \newcommand{\op}{\mathrm{op}}\C^\op \to \C$;
  • a natural isomorphism $\varphi : \dagger \cdot i^\op \cong i \cdot (-)^{-1} : \C_u^\op \to \C$;
  • a natural isomorphism $\psi : \dagger \cdot \dagger^\op \cong 1_\C$;
  • such that for all $A \in \C_u$, $\psi_{iA} = \varphi_A (\varphi_{A}^\dagger)^{-1} : (iA)^{\dagger \dagger} \to iA$, or equivalently, as natural transformations, $\psi \cdot i = (\varphi \cdot (-)^{-1})(\dagger \cdot \varphi^\op)^{-1} : \dagger \cdot \dagger^\op \cdot i \to i$;
  • and such that for any $A, B \in \C_u$, the image of $\C_u(A,B) \to \C(iA,iB)$ consists of all $u$ such that $\varphi_A \cdot u^\dagger \cdot \varphi_B^{-1}$ is a 2-sided inverse for $u$.

Given this, I claim:

  1. each component is “non-evil” as structure on the earlier components (this can be made precise as a lifting property for forgetful functors between 2-categories);
  2. strict dagger categories are precisely weak dagger categories such that $i$ is bijective on objects and $\varphi_A = 1_{iA}$ for all $A \in \C_u$;
  3. given any weak dagger cat with $i$ bijective on objects, one can modify $\dagger$, $\varphi$, and $\psi$ to obtain a strict dagger-structure, equivalent to the original, with the equivalence acting trivially on $\C$, $\C_u$, and $i$;
  4. therefore, given a category $\C$ equipped with a distinguished all-objects subgroupoid $\C_u$, “strict dagger structures on $\C$ with unitaries $\C_u$” correspond to “weak dagger structures on $\C_u \to \C$”; so strict dagger structure is non-evil as a structure on “cats with a distinguished all-objects subgroupoid”;
  5. if we drop the last component of the definition, we similarly get a non-evil structure of “strict dagger structures on $\C$ with unitaries including at least $\C_u$”;
  6. given any weak dagger cat $\C$, there is an equivalent strict one, with the same unitary category $\C_u$, but with new ambient category given by the objects of $\C_u$ with the morphisms of $\C$. So overall, weak dagger categories do not give us anything essentially different from strict ones.

(I’m pretty sure that I’m remembering most of the ideas here from somewhere, but I can’t find where. The nearest I can find is this post by Mike Shulman on that same categories list thread. Better references very welcome.)

$\endgroup$
  • 1
    $\begingroup$ This is an excellent answer. May I ask you to expand on "(The dagger is a contravariant functor on C, and the “involutivity” is a natural isomorphism †⋅†op⋅i≅i.)". In particular, given a morphism $f:x\to y$, how does one encode the idea that $f^*$ should go from $y$ to $x$. $\endgroup$ – André Henriques Oct 6 '15 at 8:13
  • 2
    $\begingroup$ You can do this using John Pardon's version of dagger category, but where you modify it slightly. Instead of the category $Fun(\Delta^1, \mathcal{C})_{isom}$, you use a category of arrows where the morphisms are squares with sides coming from your distinguished "subcategory" of "unitary isomorphisms". Then the problem which I pointed out goes away since then you only need naturality with respect to the unitary isomorphisms, which is fine. $\endgroup$ – Chris Schommer-Pries Oct 6 '15 at 9:27
  • $\begingroup$ I have one more concern, which is that one should probably encode the condition that the unitary morphisms are those satisfying $u^\dagger=u^{-1}$. Presumably, that can that be done... (Anyways, I would appreciate having a proposal of an actual of full definition of "non-evil dagger category", as opposed to just a sketch of definition). $\endgroup$ – André Henriques Oct 6 '15 at 10:41
  • $\begingroup$ @AndréHenriques: thanks for pointing this out; I’d made an error in the sketch. I’ll fix it and flesh out the definition. $\endgroup$ – Peter LeFanu Lumsdaine Oct 6 '15 at 10:46
  • 2
    $\begingroup$ Wonderful! I wish I could accept more than one answer: Simon Henry's answer is equally good and nicely complements this one. My overall conviction is that (quoting Qiaochu) "dagger categories are not really categories". They should be compared with, say, the notion of non-unital category. Hurkyl summarised this nicely: "dagger ought to be extra internal algebraic structure (at the same level as sources, targets, identities and composition)". I also want to point out that the above "weak dagger categories" become really awkward if one tries to, e.g. model the notion of a linear dagger category. $\endgroup$ – André Henriques Oct 6 '15 at 13:33
25
$\begingroup$

John Pardon's invariant version of $\dagger$-category is very good, but unfortunately it does not capture the examples. Specifically the category of Hilbert spaces doesn't have this structure.

There is a problem in making the isomorphisms such as $s \circ \dagger_* \cong t$ natural. Such a natural isomorphism gives component morphisms $$\phi_y: y^\dagger \cong y$$ for each object $y \in \mathcal{C}$ (well more correctly for each object of the arrow category $Fun(\Delta^1, \mathcal{C})_{isom}$, but we can restrict to identity arrows).

The point is that in order for this to be natural certain squares have to commute.

Suppose that we have a morphism in $Fun(\Delta^1, \mathcal{C})_{isom}$. Such a morphism is a commutative square in $\mathcal{C}$ where the sides are isomorphisms. Applying the functor $t$ to this square gives us an isomorphism in $\mathcal{C}$: $$h: y \to y'$$ Applying the functor $s \circ \dagger_*$ gives us $$ (h^\dagger)^{-1}: y^\dagger \to (y')^\dagger $$ Note that we had to take an inverse here, which is why we had to restrict to the invertible morphisms between arrows in the first place.

In particular let's look at squares (i.e morphisms of $Fun(\Delta^1, \mathcal{C})_{isom}$) which go from $id_y$ to $id_y$. Then we see that in this case $h: y \cong y$ is an automorphism (and determines the square). Naturality gives us the equation: $$(h^\dagger)^{-1} = \phi_y^{-1} \circ h \circ \phi_y$$ So this means that taking dagger-inverse of automorphisms is implemented by conjugating by a fixed isomorphism!

This is not satisfied by the category of Hilbert spaces, the main example. In that case $\dagger$ is actually the identity on all objects, but there is no possible choice of $\phi_y$ that works. Such a $\phi_y$ would have to commute with all unitary endomorphisms, and hence has to be a multiple of the identity. But then the above equation would mean that every invertible morphism was already unitary, a contradiction. So the category of Hilbert spaces does not support the proposed, manifestly invariant (i.e. non-evil), notion.

$\endgroup$
19
$\begingroup$

In my opinion, dagger categories are not evil, but they are not categories with extra structure (in the ordinary sense) either. (I think this is what Qiaochu Yuan meant in his comment.) More specifically, I wouldn't think of $\dagger$ as a functor. Let me give a comparison.

In some parallel universe, people started to study "ategories", before they studied categories. Ategories are like categories, but without composition. That is, a small ategory $\mathcal{A}$ consists of a set of objects $\operatorname{ob} \mathcal{A}$ and a set of morphisms $\operatorname{mor} \mathcal{A}$ with source and target maps $s, t\colon \operatorname{mor} \mathcal{A} \to \operatorname{ob} \mathcal{A}$.

Now, suddenly people start to consider the composition of morphisms, $-\circ-\colon \operatorname{mor} \mathcal{A} \times_{s,t} \operatorname{mor} \mathcal{A} \to \operatorname{mor} \mathcal{A}$. And they demand that $g \circ f$ has the same source object like $f$, on the nose! How dare they, that's an evil concept! Maybe some other people try to find a weakened version of composition, but they fail, or their results are not as satisfying as they expected.

The point is, that doesn't have to think of a category as an ategory with an extra piece of global structure. One should think of the morphisms as a set $\mathcal{A}(X,Y)$ for any two objects $X, Y \in \operatorname{ob} \mathcal{A}$, and of the composition as a map $-\circ_{X,Y,Z}-\colon \mathcal{A}(Y,Z) \times \mathcal{A}(X,Y) \to \mathcal{A}(X,Z)$ for every triple of objects $X,Y,Z \in \operatorname{ob} \mathcal{A}$.

This comparison might be quite artificial, I admit. But let's try and translate the lesson to dagger structures.

Definition: A small dagger category $\mathcal{C}$ consists of:

  • A set $\operatorname{ob} \mathcal{C}$
  • $\forall X,Y \in \operatorname{ob} \mathcal{C}$, a set $\mathcal{C}(X,Y)$
  • $\forall X,Y,Z \in \operatorname{ob} \mathcal{C}$, a map $-\circ_{X,Y,Z}-\colon \mathcal{A}(Y,Z) \times \mathcal{A}(X,Y) \to \mathcal{A}(X,Z)$
  • $\forall X \in \operatorname{ob} \mathcal{C}$, an element $1_X \in \mathcal{A}(X,X)$
  • $\forall X,Y \in \operatorname{ob} \mathcal{C}$, a map $\dagger_{X,Y}\colon \mathcal{C}(X,Y) \to \mathcal{C}(Y,X)$
  • satisfying certain axioms which you all know.

Dagger categories generalise involutive monoids in the same way groupoids generalise groups.

Bottom line: In my opinion, dagger structures are the same kind of structure as "composition structures". The natural definition is pointwise and the equality on objects arises as a typing constraint. It just so happens that one can see them as functors as well, and that definition is then evil. But the natural definition is perfectly fine, and the terminology "evil" does not apply.

$\endgroup$
  • 7
    $\begingroup$ That rings very much true. One could even go a little bit further in that 'plain' categories are composition structures in which one can compose a bunch of morphisms aligned like $\bullet\to\bullet\to\bullet\to\bullet$, while in a dagger category one can compose a bunch of morphisms aligned also as e.g. in $\bullet\to\bullet\leftarrow\bullet\leftarrow\bullet\rightarrow\bullet$. In both cases, the axioms form a presentation of a limit sketch whose models are plain categories or dagger categories, respectively. $\endgroup$ – Tobias Fritz Dec 18 '15 at 10:35
  • 1
    $\begingroup$ For plain categories, one can also express the compostionality in terms of properties of the nerve, which is a particular kind of simplicial set. Is there an analogous description of the compositionality in a dagger category? What is the nerve of a dagger category, if not just a simplicial set? Maybe we should discuss that in person soon ;) $\endgroup$ – Tobias Fritz Dec 18 '15 at 10:36
  • $\begingroup$ This is a very nice summary of the situation, which which I completely agree. $\endgroup$ – André Henriques Dec 18 '15 at 11:38
  • 1
    $\begingroup$ Ategories, aka quivers. $\endgroup$ – mattecapu Jul 11 '19 at 19:59
  • 1
    $\begingroup$ Quivers, aka multidigraphs. $\endgroup$ – Manuel Bärenz Jul 12 '19 at 13:57
15
$\begingroup$

As I Said in a comment above, Peter Selinger posted a few years ago on the category theory list a definition of a "non-evil structure" and showed that there is no reasonable way to make the notion of dagger categories into such a notion. His post can be found here.

The core of the argument, as I understand it, is that if you have an equivalence of category $F :C \rightarrow D$ such that $D$ is a Dagger category, there is a unique way to make $C$ into a Dagger category such that $F$ is compatible to the dagger structure, but the weak inverse of $F$ won't necessary be compatible with the dagger structure. This is not something acceptable for a structure that can be defined using only purely "categorical notion".

The typical example of this is the forgetful functor $F$ from finite dimensional Hilbert space to finite dimensional vector space over $\mathbb{C}$.

It is a categorical equivalence, so if you pick any weak inverse it will put a dagger structure on the category of finite dimensional vector spaces but this structure is never* going to be compatible with the dagger structure.

*: with the usual set theoretic definition at least.

$\endgroup$
  • 3
    $\begingroup$ This being said I would be very interested to see the definition that Peter LeFanu Lumsdaine mentioned in his comment above as this obstruction seems pretty solid but maybe not completely unbreakable: specifying a specific class of isomorphism is enough to modify the notion of equivalence and hence to break the above argument. $\endgroup$ – Simon Henry Oct 5 '15 at 22:01
  • 1
    $\begingroup$ See my answer for that definition, and an explanation of why it’s not covered by Selinger’s no-go theorem. The definition is certainly not original — indeed, I seem to recall some author(s) developing the basics of the theory of dagger-categories using it — but I am having trouble finding the references, and I should probably get some sleep instead of searching longer now… $\endgroup$ – Peter LeFanu Lumsdaine Oct 5 '15 at 22:37
  • 4
    $\begingroup$ This answer deserves to be accepted, and the only reason it's not accepted is that I can't accept more than one answer. $\endgroup$ – André Henriques Oct 6 '15 at 12:07
7
$\begingroup$

What about the following definition of $\dagger$-categories (which looks non-evil, at least to my untrained eye).

A $\dagger$-structure on $\mathcal C$ consists firstly of a functor $\dagger:\mathcal C\to\mathcal C^{op}$ with a natural isomorphism $\dagger\circ\dagger=\operatorname{id}_{\mathcal C}$. Now we just have to figure out how to state the "is the identity on objects" part in a non-evil way.

For any category $\mathcal C$, let's denote by $\mathcal C_{iso}$ the subcategory of $\mathcal C$ taking only isomorphisms as morphisms (i.e. $\mathcal C\mapsto\mathcal C_{iso}$ is the right adjoint to the inclusion of groupoids into all categories).

Now consider $\operatorname{Fun}(\Delta^1,\mathcal C)_{iso}$, with its two forgetful functors $s,t:\operatorname{Fun}(\Delta^1,\mathcal C)_{iso}\to\mathcal C_{iso}$. A functor $\dagger:\mathcal C\to\mathcal C^{op}$ induces a pushforward: $$\dagger_\ast:\operatorname{Fun}(\Delta^1,\mathcal C)_{iso}\to\operatorname{Fun}(\Delta^1,\mathcal C^{op})_{iso}=\operatorname{Fun}((\Delta^1)^{op},\mathcal C)_{iso}=\operatorname{Fun}(\Delta^1,\mathcal C)_{iso}$$ Now we specify natural isomorphisms:

  1. $s\circ\dagger_\ast\xrightarrow\sim t$

  2. $t\circ\dagger_\ast\xrightarrow\sim s$

with the following coherence conditions:

  1. The composition $s\circ\dagger_\ast\circ\dagger_\ast\xrightarrow\sim t\circ\dagger_\ast\xrightarrow\sim s$ should agree with the map $s\circ\dagger_\ast\circ\dagger_\ast\xrightarrow\sim s$ coming from the natural isomorphism $\dagger\circ\dagger=\operatorname{id}_{\mathcal C}$.

  2. The same with $s$ and $t$ reversed.

Is there any reason why this (or some small modification thereof) shouldn't work?

$\endgroup$
  • 2
    $\begingroup$ I don't see anything forcing to have an analogue of $(fg)^* = g^* f^*$ ? $\endgroup$ – Simon Henry Oct 5 '15 at 10:40
  • $\begingroup$ @AndréHenriques: Your first sentence is not true I think. the "iso" is not inside the $Fun( \_, \_ )$ $\endgroup$ – Simon Henry Oct 5 '15 at 10:56
  • $\begingroup$ Oops. You're right. I'll delete my comment. $\endgroup$ – André Henriques Oct 5 '15 at 10:59
  • 5
    $\begingroup$ @JohnPardon: Your last sentence "is there any reason some construction such as this shouldn't work?" is a perfect summary of my question. I believe that the answer is "yes, there is a reason why such an approach can't work" and I would like to know what that reason is. $\endgroup$ – André Henriques Oct 5 '15 at 11:14
  • $\begingroup$ @SimonHenry: Thanks! I believe I have now fixed this; see the edit. $\endgroup$ – John Pardon Oct 5 '15 at 11:39
6
$\begingroup$

Here's a notion of undirected category, which is equivalent to the notion of dagger category. It's a bit cumbersome to work with, but the main point is to underscore Qiaochu Yuan and Manuel Bärenz's points that daggers are not really a categorical structure, and dagger categories are their own thing.

An undirected category consists of a pair of maps $s,t:C_1 \to C_0$, with constant $\mathrm{id} : C_0 \to C_1$ and instead of one composition operation for composing arrows tip to tail, there are four composition operations for composing in any direction (composition is in diagrammatic order):

${}_t;_s : Hom(A,B) \times Hom(B,C) \to Hom(A,C)$

${}_s;_s : Hom(B,A) \times Hom(B,C) \to Hom(A,C)$

${}_t;_t : Hom(A,B) \times Hom(C,B) \to Hom(A,C)$

${}_s;_t : Hom(B,A) \times Hom(C,B) \to Hom(A,C)$

Satisfying the following equations ($a, b$ and $c$ are variables in $s$ and $t$, and $-s = t$, $-t = s$)

$f = f {}_t;_a \mathrm{id} = \mathrm{id} {}_a;_s f$ (usual identity)

$f {}_s;_a \mathrm{id} = \mathrm{id} {}_a;_t f =: f^\dagger$

$(f {}_a;_b g) {}_s;_c h = (g {}_b;_a f) {}_t;_c h = g {}_b;_s (f {}_{-a};_c h) = g {}_b;_t (h {}_{c};_{-a} f)$ (the middle one includes usual associativity).

It's not hard to show that given a dagger category, you can get an undirected category by defining the compositions as $f {}_s;_t g := f^\dagger ; g^\dagger$ and the like, with the same identity, and given an undirected category, define a dagger as in the second line of equations above, and to show that these are inverses of each other.

Then there is also the fact that algebras of the path monad on the category of undirected graphs is exactly an undirected/dagger category, just as an algebra of the path monad on the category of directed graphs is a category.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.