A survey of graphical languages for monoidal categories

Peter Selinger

Introduction

There are many kinds of monoidal categories with additional structure — braided, rigid, pivotal, balanced, tortile, ribbon, autonomous, sovereign, spherical, traced, compact closed, *-autonomous, to name a few. Many of them have an associated graphical language of “string diagrams”. The proliferation of different notions is often confusing to non-experts, and occasionally to experts as well. To add to the confusion, one concept often appears in the literature under multiple names (for example, “rigid” is the same as “autonomous”, “sovereign” is the same as “pivotal”, and “ribbon” is the same as “tortile”).

In this survey, I attempt to give a systematic overview of the main notions and their associated graphical languages. My initial intention was to summarize, without proof, only the main definitions and coherence results that appear in the literature. However, it quickly became apparent that, in the interest of being systematic, I had to include some additional notions. This led to the sections on spacial categories, and planar and braided traced categories.

Historically, the terminology was often fixed for special cases before more general cases were considered. As a result, some concepts have a common name (such as “compact closed category”) where another name would have been more systematic (e.g. “symmetric autonomous category”). I have resisted the temptation to make major changes to the established terminology. However, I propose some minor tweaks that will hopefully not be disruptive. For example, I prefer “traced category”, which can be combined with various qualifying adjectives, to the longer and less flexible “traced monoidal category”.

Many of the coherence results are widely known, or at least presumed to be true, but some of them are not explicitly found in the literature. For those that can be attributed, I have attempted to do so, sometimes with a caveat if only special cases have been proved in the literature. For some easy results, I have provided proof sketches. Some unproven results have been included as conjectures.

While the results surveyed here are mathematically rigorous, I have shied away from giving the full technical details of the definitions of the graphical languages and their respective notions of equivalence of diagrams. Instead, I present the graphical languages somewhat informally, but in a way that will be sufficient for most applications. Where appropriate, full mathematical details can be found in the references.

Readers who want a quick overview of the different notions are encouraged to first consult the summary chart at the end of this article.

An updated version of this article will be maintained on the ArXiv, so I encourage readers to contact me with corrections, literature references, and updates.

The use of graphical notations for operator diagrams in physics goes back to Penrose . Initially, such notations applied to multiplications and tensor products of linear operators, but it became gradually understood that they are applicable in more general situations.

To see how graphical languages arise from matrix multiplication, consider the following example. Let $M:A\rightarrow B$ , $N:B\otimes C\rightarrow D$ , and $P:D\rightarrow E$ be linear maps between finite dimensional vector spaces $A,B,C,D,E$ . These maps can be combined in an obvious way to obtain a linear map $F:A\otimes C\rightarrow E$ . In functional notation, the map $F$ can be written

The same can be expressed as a summation over matrix indices, relative to some chosen basis of each space. In mathematical notation, suppose $M=(m_{j,i})$ , $N=(n_{l,jk})$ , $P=(p_{m,l})$ , and $F=(f_{m,ik})$ , where $i,j,k,l,m$ range over basis vectors of the respective spaces. Then

In (1.2) and (1.3), the order of the factors in the multiplication is not relevant, as all the information is contained in the indices. Also note that, while the notation mentions the chosen bases, the result is of course basis independent. This is because indices occur in pairs of opposite variance (if on the same side of the equation) or equal variance (if on opposite sides of the equation). It was Penrose who first pointed out that the notation is valid in many situations where the indices are purely formal symbols, and the maps may not even be between vector spaces.

= \vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 3.01175pt\hbox{{\hbox{\kern-3.01175pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.00565pt\hbox{\xyscale@@{1.0}{1.0}\kern 0.0pt\kern 0.0pt}}}}}}}}}}=\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 2.93901pt\hbox{{\hbox{\kern-2.93901pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise-0.00047pt\hbox{\xyscale@@{1.0}{1.0}\kern 0.0pt\kern 0.0pt}}}}}}}}}} (1.4) Finally, since the indices no longer serve any purpose, one may omit them from the notation. Instead, it is more useful to label each wire with the name of the corresponding space.

= \vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 3.01175pt\hbox{{\hbox{\kern-3.01175pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise-0.00414pt\hbox{\xyscale@@{1.0}{1.0}\kern 0.0pt\kern 0.0pt}}}}}}}}}}=\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 2.93901pt\hbox{{\hbox{\kern-2.93901pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise-0.01405pt\hbox{\xyscale@@{1.0}{1.0}\kern 0.0pt\kern 0.0pt}}}}}}}}}} (1.5) In the notation of monoidal categories, (1.5) can be expressed as a commutative diagram

Thus, we have completed a full circle and arrived back at the notation (1.1) that we started with.

Organization of the paper.

In each of the remaining sections of this paper, we will consider a particular class of categories and its associated graphical language.

Acknowledgments.

I would like to thank Gheorghe Ştefănescu and Ross Street for their help in locating hard-to-obtain references, and for providing some background information. Thanks to Fabio Gadducci, Chris Heunen, and Micah McCurdy for useful comments on an earlier draft.

Coherence.

Note that the three defining axioms of categories (e.g., $\textrm{\rm id}_{B}\circ f=f$ ) are automatically satisfied “up isomorphism” in the graphical language. This property is known as soundness. A converse of this statement is also true: every equation that holds in the graphical language is a consequence of the axioms. This property is called completeness. We refer to a soundness and completeness theorem as a coherence theorem.

A well-formed equation between two morphism terms in the language of categories follows from the axioms of categories if and only if it holds in the graphical language up to isomorphism of diagrams.

Hopefully it is obvious what is meant by isomorphism of diagrams: two diagrams are isomorphic if the boxes and wires of the first are in bijective correspondence with the boxes and wires of the second, preserving the connections between boxes and wires.

Admittedly, the above coherence theorem for categories is a triviality, and is not usually stated in this way. However, we have included it for sake of uniformity, and for comparison with the less trivial coherence theorems for monoidal categories in the following sections. The proof is straightforward, since by the associativity and unit axioms, each morphism term is uniquely equivalent to a term of the form $((f_{n}\circ\ldots)\circ f_{2})\circ f_{1}$ for $n\geq 0$ , with corresponding diagram

We have equipped wires with a left-to-right arrow, and boxes with a marking in the upper left corner. These markings are of no use at the moment, but will become important as we extend the language in the following sections.

Technicalities

So far, we have not been very precise about what the wires and boxes of a diagram are labeled with. We have also glossed over what was meant by “a well-formed equation between morphism terms in the language of categories”. We now briefly explain these notions, without giving all the formal details. For a more precise mathematical treatment, see e.g. Joyal and Street .

The wires of a diagram are labeled with object variables, and the boxes are labeled with morphism variables. To understand what this means, consider the familiar language of arithmetic expressions. This language deals with terms, such as $(x+y+2)(x+3)$ , which are built up from variables, such as $x$ and $y$ , constants, such as $2$ and $3$ , by means of operations, such as addition and multiplication. Variables can be viewed in three different ways: first, they can be viewed as symbols that can be compared (e.g. the variable $x$ occurs twice in the given term, and is different from the variable $y$ ). They can also be viewed as placeholders for arbitrary numbers, for example $x=5$ and $y=15$ . Here $x$ and $y$ are allowed to represent different numbers or the same number; however, the two occurrences of $x$ must denote the same number. Finally, variables can be viewed as placeholders for arbitrary terms, such as $x=a+b$ and $y=z^{2}$ .

The formal language of category theory is similar, except that we require two sets of variables: object variables (for labeling wires) and morphism variables (for labeling boxes). We must also equip each morphism variable with a specified domain and codomain. The following definition makes this more precise.

A simple (categorical) signature $\Sigma$ consists of a set $\Sigma_{0}$ of object variables, a set $\Sigma_{1}$ of morphism variables, and a pair of functions $\mathop{\textrm{\rm dom}}\nolimits,\mathop{\textrm{\rm cod}}\nolimits:\Sigma_{1}\rightarrow\Sigma_{0}$ . Object variables are usually written $A,B,C,\ldots$ , morphism variables are usually written $f,g,h,\ldots$ , and we write $f:A\rightarrow B$ if $\mathop{\textrm{\rm dom}}\nolimits(f)=A$ and $\mathop{\textrm{\rm cod}}\nolimits(f)=B$ .

Given a simple signature, we can then build morphism terms, such as $f\circ(g\circ\textrm{\rm id}_{A})$ , which are built from morphism variables (such as $f$ and $g$ ) and morphism constants (such as $\textrm{\rm id}_{A}$ ), via operations (i.e., composition). Each term is recursively equipped with a domain and a codomain, and we must require compositions to respect the domain and codomain information. A term that obeys these rules is called well-formed. Finally, an equation between terms is called a well-formed equation if the left-hand side and right-hand side are well-formed terms that moreover have equal domains and equal codomains.

The graphical language is also relative to a given signature. The wires and boxes are labeled, respectively, with object variables and morphism variables from the signature, and the labeling must respect the domain and codomain information. This means that the wire entering (respectively, exiting) a box labeled $f$ must be labeled by the domain (respectively, codomain) of $f$ .

The above remark about the different roles of variables in arithmetic also holds for the diagrammatic language of categories. On the one hand, the labels can be viewed as formal symbols. This is the view used in the coherence theorem, where the formal labels are part of the definition of equivalence (in this case, isomorphism) of diagrams.

The labels can also be viewed as placeholders for specific objects and morphisms in an actual category. Such an assignment of objects and morphisms is called an interpretation of the given signature. More precisely, an interpretation $i$ of a signature $\Sigma$ in a category ${\bf C}$ consists of a function $i_{0}:\Sigma_{0}\rightarrow|{\bf C}|$ , and for any $f\in\Sigma_{1}$ a morphism $i_{1}(f):i_{0}(\mathop{\textrm{\rm dom}}\nolimits f)\rightarrow i_{0}(\mathop{\textrm{\rm cod}}\nolimits f)$ . By a slight abuse of notation, we write $i:\Sigma\rightarrow{\bf C}$ for such an interpretation.

Finally, a morphism variable can be viewed as a placeholder for an arbitrary (possibly composite) diagram. We occasionally use this latter view in schematic drawings, such as the schematic representation of $t\circ s$ in Table 1. We then label a box with a morphism term, rather than a formal variable, and understand the box as a short-hand notation for a possibly composite diagram corresponding to that term.

Functors and natural transformations.

Let ${\bf C}$ and ${\bf D}$ be categories. A functor $F:{\bf C}\rightarrow{\bf D}$ consists of a function $F:|{\bf C}|\rightarrow|{\bf D}|$ , and for each pair of objects $A,B\in|{\bf C}|$ , a function $F:\textrm{\rm hom}_{{\bf C}}(A,B)\rightarrow\textrm{\rm hom}_{{\bf D}}(FA,FB)$ , satisfying $F(g\circ f)=F(g)\circ F(f)$ and $F(\textrm{\rm id}_{A})=\textrm{\rm id}_{FA}$ .

Let ${\bf C}$ and ${\bf D}$ be categories, and let $F,G:{\bf C}\rightarrow{\bf D}$ be functors. A natural transformation $\tau:F\rightarrow G$ consists of a family of morphisms $\tau_{A}:FA\rightarrow GA$ , one for each object $A\in|{\bf C}|$ , such that the following diagram commutes for all $f:A\rightarrow B$ :

Coherence and free categories.

Most coherence theorems are proved by characterizing the free categories of a certain kind.

We say that a category ${\bf C}$ is free over a signature $\Sigma$ if it is equipped with an interpretation $i:\Sigma\rightarrow{\bf C}$ , such that for any category ${\bf D}$ and interpretation $j:\Sigma\rightarrow{\bf D}$ , there exists a unique functor $F:{\bf C}\rightarrow{\bf D}$ such that $j=F\circ i$ .

The graphical language of categories over a signature $\Sigma$ , with identities and composition as defined in Table 1, and up to isomorphism of diagrams, forms the free category over $\Sigma$ .

Theorem 2.1 is indeed a consequence of this theorem: by definition of freeness, an equation holds in all categories if and only if it holds in the free category. By the characterization of the free category, an equation holds in the free category if and only if it holds in the graphical language.

Monoidal categories

In this section, we consider various notions of monoidal categories. We sometimes refer to these notions as “progressive”, which means they have graphical languages where all arrows point left-to-right. This serves to distinguish them from “autonomous” notions, which will be discussed in Section 4, and “traced” notions, which will be discussed in Section 5.

A monoidal category (also sometimes called tensor category) is a category with an associative unital tensor product. More specifically:

A monoidal category is a category with the following additional structure:

a new operation $A\otimes B$ on objects and a new object constant $I$ ;

a new operation on morphisms: if $f:A\rightarrow C$ and $g:B\rightarrow D$ , then

$\otimes$ is a bifunctor, which means $\textrm{\rm id}_{A}\otimes\textrm{\rm id}_{B}=\textrm{\rm id}_{A\otimes B}$ and $(k\otimes h)\circ(g\otimes f)=(k\circ g)\otimes(h\circ f)$ ;

$\alpha$ , $\lambda$ , and $\rho$ are natural transformations, i.e., $(f\otimes(g\otimes h))\circ\alpha_{A,B,C}=\alpha_{A^{\prime},B^{\prime},C^{\prime}}\circ((f\otimes g)\otimes h)$ , $f\circ\lambda_{A}=\lambda_{A^{\prime}}\circ(\textrm{\rm id}_{I}\otimes f)$ , and $f\circ\rho_{A}=\rho_{A^{\prime}}\circ(f\otimes\textrm{\rm id}_{I})$ ;

plus the following two coherence axioms, called the “pentagon axiom” and the “triangle axiom”:

$\scriptstyle{\alpha_{A,B\otimes C,D}}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>A</mi><mo>⊗</mo><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>B</mi><mo>⊗</mo><mi>C</mi><mo stretchy="false">)</mo><mo>⊗</mo><mi>D</mi><mo stretchy="false">)</mo><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{A\otimes((B\otimes C)\otimes D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>A⊗((B⊗C)⊗D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{A\otimes\alpha_{B,C,D}}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mo stretchy="false">(</mo><mo stretchy="false">(</mo><mi>A</mi><mo>⊗</mo><mi>B</mi><mo stretchy="false">)</mo><mo>⊗</mo><mi>C</mi><mo stretchy="false">)</mo><mo>⊗</mo><mi>D</mi><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{((A\otimes B)\otimes C)\otimes D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>((A⊗B)⊗C)⊗D\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{\alpha_{A,B,C}\otimes D}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>α</mi><mrow><mi>A</mi><mo>⊗</mo><mi>B</mi><mo separator="true">,</mo><mi>C</mi><mo separator="true">,</mo><mi>D</mi></mrow></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{\alpha_{A\otimes B,C,D}}</annotation></semantics></math>αA⊗B,C,D\textstyle{A\otimes(B\otimes(C\otimes D))}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mo stretchy="false">(</mo><mi>A</mi><mo>⊗</mo><mi>B</mi><mo stretchy="false">)</mo><mo>⊗</mo><mo stretchy="false">(</mo><mi>C</mi><mo>⊗</mo><mi>D</mi><mo stretchy="false">)</mo><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{(A\otimes B)\otimes(C\otimes D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>(A⊗B)⊗(C⊗D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{\alpha_{A,B,C\otimes D}}$ $\textstyle{(A\otimes I)\otimes B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mrow><msub><mi>ρ</mi><mi>A</mi></msub><mo>⊗</mo><msub><mtext>id</mtext><mi>B</mi></msub></mrow></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{\rho_{A}\otimes\textrm{\rm id}_{B}}</annotation></semantics></math>ρA⊗idB\scriptstyle{\alpha_{A,I,B}}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>A</mi><mo>⊗</mo><mo stretchy="false">(</mo><mi>I</mi><mo>⊗</mo><mi>B</mi><mo stretchy="false">)</mo><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{A\otimes(I\otimes B)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>A⊗(I⊗B)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{\textrm{\rm id}_{A}\otimes\lambda_{B}}$ $\textstyle{A\otimes B}$ When we specifically want to emphasize that a monoidal category is not assumed to be braided, symmetric, etc., we sometimes also refer to it as a planar monoidal category.

Examples of monoidal categories include: the category Set (of sets and functions), together with the cartesian product $\times$ ; the category Set together with the disjoint union operation $+$ ; the category Rel with either $\times$ or $+$ ; the category Vect (of vectors spaces and linear functions) with either $\oplus$ or $\otimes$ ; the category Hilb of Hilbert spaces with either $\oplus$ or $\otimes$ ; the categories Top and Cob with disjoint union $+$ . Note that in each case, we need to specify a category and a tensor product (in general there are multiple choices). Technically, we should also specify associativity maps etc., but they are usually clear from the context.

We extend the graphical language of categories as follows. A tensor product of objects is represented by writing the corresponding wires in parallel. The unit object is represented by zero wires. A morphism variable $f:A_{1}\otimes\ldots\otimes A_{n}\rightarrow B_{1}\otimes\ldots\otimes B_{m}$ is represented as a box with $n$ input wires and $m$ output wires. A tensor product of morphisms is represented by stacking the corresponding diagrams. This is shown in Table 2.

Note that it is our convention to write tensor products in the bottom-to-top order. Similar conventions apply to objects as to morphisms: thus, a single wire is labeled by an object variable such as $A$ , while a more general object such as $A\otimes B$ or $I$ is represented by zero or more wires. For more details, see “Monoidal signatures” below.

Coherence.

It is easy to check that the graphical language for monoidal categories is sound, up to deformation of diagrams in the plane. As an example, consider the following law, which is a consequence of bifunctoriality:

Translated into the graphical language, this becomes

which obviously holds up to deformation of diagrams. We have the following coherence theorem:

A well-formed equation between morphism terms in the language of monoidal categories follows from the axioms of monoidal categories if and only if it holds, up to planar isotopy, in the graphical language.

Here, by “planar isotopy”, we mean that two diagrams, drawn in a rectangle in the plane with incoming and outgoing wires attached to the boundaries of the rectangle, are equivalent if it is possible to transform one to the other by continuously moving around boxes in the rectangle, without allowing boxes or wires to cross each other or to be detached from the boundary of the rectangle during the moving. To make these notions mathematically precise, it is usually easier to represent morphism as points, rather than boxes. For precise definitions and a proof of the coherence theorem, see Joyal and Street .

Technically, Joyal and Street’s proof in only applies to planar isotopies where each intermediate diagram during the deformation remains progressive, i.e., with all arrows oriented left-to-right. Joyal and Street call such an isotopy “recumbent”. We conjecture that the result remains true if one allows arbitrary planar deformations. Similar caveats also apply to the coherence theorems for braided and balanced monoidal categories below.

The following is an example of two diagrams that are not isomorphic in the planar embedded sense:

where $f:I\rightarrow A\otimes B$ , $g:A\otimes B\rightarrow I$ , and $h:I\rightarrow I$ . And indeed, the corresponding equation $g\circ((\rho_{A}\circ(\textrm{\rm id}_{A}\otimes h)\circ\rho^{-1}_{A})\otimes\textrm{\rm id}_{B})\circ f=g\circ((\lambda_{A}\circ(h\otimes\textrm{\rm id}_{A})\circ\lambda^{-1}_{A})\otimes\textrm{\rm id}_{B})\circ f$ does not follow from the axioms of monoidal categories. This is an easy consequence of soundness.

Note that because of the coherence theorem, it is not actually necessary to memorize the axioms of monoidal categories: indeed, one could use the coherence theorem as the definition of monoidal category! For practical purposes, reasoning in the graphical language is almost always easier than reasoning from the axioms. On the other hand, the graphical definition is not very useful when one has to check whether a given category is monoidal; in this case, checking finitely many axioms is easier.

Relationship to traditional coherence theorems.

Many category theorists are familiar with coherence theorems of the form “all diagrams of a certain type commute”. Mac Lane’s traditional coherence theorem for monoidal categories is of this form. It states that all diagrams built from only $\alpha$ , $\lambda$ , $\rho$ , id, $\circ$ , and $\otimes$ commute.

The coherence results in this paper are of a more general form (cf. Kelly [26, p. 107]). Here, the object is to characterize all formal equations that follow from a given set of axioms. We note that the traditional coherence theorem is an easy consequence of the general coherence result of Theorem 3.1: namely, if a given well-formed equation is built only from $\alpha$ , $\lambda$ , $\rho$ , id, $\circ$ , and $\otimes$ , then both the left-hand side and right-hand side denote identity diagrams in the graphical language. Therefore, by Theorem 3.1, the equation follows from the axioms of monoidal categories. Analogous remarks hold for all the coherence theorems of this article.

Technicalities

To be precise about the labels on diagrams of monoidal categories, and about the meaning of “well-formed equation” in the coherence theorem, we introduce the concept of a monoidal signature. This generalizes the simple signatures introduced in Section 2. Monoidal signatures were introduced under the name tensor schemes by Joyal and Street . We give a non-strict version of the definition.

Given a set $\Sigma_{0}$ of object variables, let $\mathop{\textrm{\rm Mon}}\nolimits(\Sigma_{0})$ denote the free $(\otimes,I)$ -algebra generated by $\Sigma_{0}$ , i.e., the set of object terms built from object variables and $I$ via the operation $\otimes$ . For example, if $A,B\in\Sigma_{0}$ , then the term $(A\otimes B)\otimes(I\otimes A)$ is an element of $\mathop{\textrm{\rm Mon}}\nolimits(\Sigma_{0})$ .

A monoidal signature consists of a set $\Sigma_{0}$ of object variables, a set $\Sigma_{1}$ of morphism variables, and a pair of functions $\mathop{\textrm{\rm dom}}\nolimits,\mathop{\textrm{\rm cod}}\nolimits:\Sigma_{1}\rightarrow\mathop{\textrm{\rm Mon}}\nolimits(\Sigma_{0})$ .

The concept of well-formed morphism terms and equations (in the language of monoidal categories) is defined relative to a given monoidal signature. In the graphical language, wires and boxes are labeled by object variables and morphism variables as before. An object term expands to zero or more parallel wires, by the rules of Table 2. As before, the labellings must respect the domain and codomain information, which now involves possibly multiple wires connected to a box. Just as we sometimes label a box by a morphism term in schematic drawings to denote a possibly composite diagram, we sometimes label a wire by an object term, such as $S$ and $T$ in Table 2. In this case, it is a short-hand notation for zero or more parallel wires.

Given a monoidal signature $\Sigma$ and a monoidal category ${\bf C}$ , an interpretation $i:\Sigma\rightarrow{\bf C}$ consists of an object function $i_{0}:\Sigma_{0}\rightarrow|{\bf C}|$ , which then extends in a unique way to $\hat{i}_{0}:\mathop{\textrm{\rm Mon}}\nolimits(\Sigma_{0})\rightarrow|{\bf C}|$ such that $\hat{i}_{0}(A\otimes B)=\hat{i}_{0}(A)\otimes\hat{i}_{0}(B)$ and $\hat{i}_{0}(I)=I$ , and for any $f\in\Sigma_{1}$ a morphism $i_{1}(f):i_{0}(\mathop{\textrm{\rm dom}}\nolimits f)\rightarrow i_{0}(\mathop{\textrm{\rm cod}}\nolimits f)$ .

The remaining graphical languages in this Section 3 are all given relative to a monoidal signature.

Monoidal functors and natural transformations.

A strong monoidal functor (also sometimes called a tensor functor) between monoidal categories ${\bf C}$ and ${\bf D}$ is a functor $F:{\bf C}\rightarrow{\bf D}$ , together with natural isomorphisms $\phi^{2}:FA\otimes FB\rightarrow F(A\otimes B)$ and $\phi^{0}:I\rightarrow FI$ , such that the following diagrams commute:

Let ${\bf C}$ and ${\bf D}$ be monoidal categories, and let $F,G:{\bf C}\rightarrow{\bf D}$ be strong monoidal functors. A natural transformation $\tau:F\rightarrow G$ is called monoidal (or a tensor transformation) if the following two diagrams commute for all $A,B$ :

Coherence and free monoidal categories.

Similarly to what we stated for categories, the coherence theorem for monoidal categories is a consequence of a characterization of the free monoidal category. However, due to the extra coherence conditions in the definition of a strong monoidal functor, the definition of freeness is slightly more complicated.

A monoidal category ${\bf C}$ is a free monoidal category over a monoidal signature $\Sigma$ if it is equipped with an interpretation $i:\Sigma\rightarrow{\bf C}$ such that for any monoidal category ${\bf D}$ and interpretation $j:\Sigma\rightarrow{\bf D}$ , there exists a strong monoidal functor $F:{\bf C}\rightarrow{\bf D}$ such that $j=F\circ i$ , and $F$ is unique up to a unique monoidal natural isomorphism.

As before, the coherence theorem can be re-formulated as a freeness theorem.

The graphical language of monoidal categories over a monoidal signature $\Sigma$ , with identities, composition, and tensor as defined in Tables 1 and 2, and up to planar isotopy of diagrams, forms a free monoidal category over $\Sigma$ .

Most of the coherence theorems (and conjectures) of this article can be similarly formulated in terms of freeness. An exception to this are the traced categories without braidings in Sections 5.1–5.4 and 7.5, as explained in Remark 5.4. From now on, we will only mention freeness when it is not entirely automatic, such as in Section 4.1.

2 Spacial monoidal categories

A monoidal category is spacial if it satisfies the additional axiom

In the graphical language, this means that

so in particular, it implies that the two terms in (3.1) are equal. The author does not know whether the concept of a spacial monoidal category appears in the literature, or if it does, under what name.

The graphical language for spacial monoidal categories is the same as that for monoidal categories, except that planarity is dropped from the notion of diagram equivalence, i.e., diagrams are considered up to isomorphism. Obviously the axioms are sound; we conjecture that they are also complete.

A well-formed equation between morphism terms in the language of spacial monoidal categories follows from the axioms of spacial monoidal categories if and only if it holds, up to isomorphism of diagrams, in the graphical language.

Note that, in the case of planar diagrams, the notion of isomorphism of diagrams coincides with ambient isotopy in 3 dimensions. This explains the term “spacial”.

3 Braided monoidal categories

A braiding on a monoidal category is a natural family of isomorphisms $c_{A,B}:A\otimes B\rightarrow B\otimes A$ , satisfying the following two “hexagon axioms”:

$\textstyle{(B\otimes A)\otimes C\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>α</mi><mrow><mi>B</mi><mo separator="true">,</mo><mi>A</mi><mo separator="true">,</mo><mi>C</mi></mrow></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{\alpha_{B,A,C}}</annotation></semantics></math>αB,A,C\textstyle{B\otimes(A\otimes C)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mrow><msub><mtext>id</mtext><mi>B</mi></msub><mo>⊗</mo><msubsup><mi>c</mi><mrow><mi>C</mi><mo separator="true">,</mo><mi>A</mi></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msubsup></mrow></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{\textrm{\rm id}_{B}\otimes c^{-1}_{C,A}}</annotation></semantics></math>idB⊗cC,A−1\textstyle{(A\otimes B)\otimes C\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mrow><msubsup><mi>c</mi><mrow><mi>B</mi><mo separator="true">,</mo><mi>A</mi></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mo>⊗</mo><msub><mtext>id</mtext><mi>C</mi></msub></mrow></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{c^{-1}_{B,A}\otimes\textrm{\rm id}_{C}}</annotation></semantics></math>cB,A−1⊗idC\scriptstyle{\alpha_{A,B,C}}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>B</mi><mo>⊗</mo><mo stretchy="false">(</mo><mi>C</mi><mo>⊗</mo><mi>A</mi><mo stretchy="false">)</mo><mi mathvariant="normal">.</mi></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{B\otimes(C\otimes A).}</annotation></semantics></math>B⊗(C⊗A).\textstyle{A\otimes(B\otimes C)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msubsup><mi>c</mi><mrow><mi>B</mi><mo>⊗</mo><mi>C</mi><mo separator="true">,</mo><mi>A</mi></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msubsup></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{c^{-1}_{B\otimes C,A}}</annotation></semantics></math>cB⊗C,A−1\textstyle{(B\otimes C)\otimes A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$ $\scriptstyle{\alpha_{B,C,A}}$ Note that every braided monoidal category is spacial; this follows from the naturality (in $I$ ) of $c_{A,I}:A\otimes I\rightarrow I\otimes A$ .

A braided monoidal functor between braided monoidal categories is a monoidal functor that is compatible with the braiding in the following sense:

One extends the graphical language of monoidal categories with the braiding:

In general, if $A$ and $B$ are composite object terms, the braiding $c_{A,B}$ is represented as the appropriate number of wires crossing each other.

Note that the braiding satisfies $c_{A,B}\circ c^{-1}_{A,B}=\textrm{\rm id}_{A\otimes B}$ , but not $c_{A,B}\circ c_{B,A}=\textrm{\rm id}_{A\otimes B}$ . Graphically:

The hexagon axiom translates into the following in the graphical language:

The Yang-Baxter equation is the following equation, which is a consequence of the hexagon axiom and naturality:

A well-formed equation between morphisms in the language of braided monoidal categories follows from the axioms of braided monoidal categories if and only if it holds in the graphical language up to isotopy in 3 dimensions.

Here, by “isotopy in 3 dimensions”, we mean that two diagrams, drawn in a 3-dimensional box with incoming and outgoing wires attached to the boundaries of the box, are isotopic if it is possible to transform one to the other by moving around nodes in the box, without allowing nodes or edges to cross each other or to be detached from the boundary during the moving. Also, the linear order of the edges entering and exiting each node must be respected. This is made more precise in Joyal and Street .

The proof by Joyal and Street is subject to some minor technical assumptions: graphs are assumed to be smooth, and the isotopies are progressive, with continuously changing tangent vectors.

4 Balanced monoidal categories

A twist on a braided monoidal category is a natural family of isomorphisms $\theta_{A}:A\rightarrow A$ , satisfying $\theta_{I}=\textrm{\rm id}_{I}$ and such that the following diagram commutes for all $A,B$ :

A balanced monoidal category is a braided monoidal category with twist.

A balanced monoidal functor between balanced monoidal categories is a braided monoidal functor that is also compatible with the twist, i.e., such that $F(\theta_{A})=\theta_{FA}$ for all $A$ .

The graphical language of balanced monoidal categories is similar to that of braided monoidal categories, except that morphisms are represented by flat ribbons, rather than 1-dimensional wires. A ribbon can be thought of as a pair of parallel wires that are infinitesimally close to each other, or as a wire that is equipped with a framing . For example, the braiding looks like this:

The twist map $\theta_{A}$ is represented as a 360-degree twist in a ribbon, or in several ribbons together, if $A$ is a composite object term. This is easiest seen in the following illustration.

The meaning of (3.3) should then be obvious.

A well-formed equation between morphisms in the language of balanced monoidal categories follows from the axioms of balanced monoidal categories if and only if it holds in the graphical language up to framed isotopy in 3 dimensions.

5 Symmetric monoidal categories

A symmetric monoidal category is a braided monoidal category where the braiding is self-inverse, i.e.:

In this case, the braiding is called a symmetry.

Because of equation (3.3), a symmetric monoidal category can be equivalently defined as a balanced monoidal category in which $\theta_{A}=\textrm{\rm id}_{A}$ for all $A$ .

The previous remark notwithstanding, there exist symmetric monoidal categories that possess a non-trivial twist (in addition to the trivial twist $\theta_{A}=\textrm{\rm id}_{A}$ ). Thus, in a balanced monoidal category, the symmetry condition $c_{A,B}=c^{-1}_{B,A}$ does not in general imply $\theta_{A}=\textrm{\rm id}_{A}$ . In other words, a balanced monoidal category that is symmetric as a braided monoidal category is not necessarily symmetric as a balanced monoidal category. An example is the category of finite dimensional vector spaces and linear bijections, with $\theta_{A}(x)=nx$ , where $n=\dim(A)$ .

On the monoidal category $(\textrm{\bf Set},\times)$ of sets with cartesian product, a symmetry is given by $c(x,y)=(y,x)$ . On the category $(\textrm{\bf Vect},\otimes)$ of vector spaces with tensor product, a symmetry is given by $c(x\otimes y)=y\otimes x$ .

The symmetry is graphically represented by a crossing:

A well-formed equation between morphisms in the language of symmetric monoidal categories follows from the axioms of symmetric monoidal categories if and only if it holds, up to isomorphism of diagrams, in the graphical language.

Note that the graphical language for symmetric monoidal categories is up to isomorphism of diagrams, without any reference to 2- or 3-dimensional structure. However, isomorphism of diagrams is equivalent to ambient isotopy in 4 dimensions, so we can still regard it as a geometric notion.

Autonomous categories

Autonomous categories are monoidal categories in which the objects have duals. In terms of graphical language, this means that some wires are allowed to run from right to left.

In a (without loss of generality strict) monoidal category, an exact pairing between two objects $A$ and $B$ is given by a pair of morphisms $\eta:I\rightarrow B\otimes A$ and $\epsilon:A\otimes B\rightarrow I$ , such that the following two adjunction triangles commute:

In such an exact pairing, $B$ is called the right dual of $A$ and $A$ is called the left dual of $B$ .

The maps $\eta$ and $\epsilon$ determine each other uniquely, and they are respectively called the unit and the counit of the adjunction. Moreover, the triple $(B,\eta,\epsilon)$ , if it exists, is uniquely determined by $A$ up to isomorphism. The existence of duals is therefore a property of a monoidal category, rather than an additional structure on it. Moreover, every strong monoidal functor automatically preserves existing duals.

A monoidal category is right autonomous if every object $A$ has a right dual, which we then denote $A^{*}$ . It is left autonomous if every object $A$ has a left dual, which we then denote ${}^{*}\!A$ . Finally, the category is autonomous if it is both right and left autonomous.

A [right, left, –] autonomous category is also called [right, left, –] rigid, see e.g. [32, p. 78]. Also, the term “autonomous” is sometimes used in the weaker sense of “monoidal closed”. Although this latter usage is no longer common, it still lives on in the terminology “*-autonomous category” (Barr , see also Section 9).

If we wish to emphasize that an autonomous category is not necessarily symmetric or braided, we sometimes call it a planar autonomous category.

If $A$ is an object variable, the objects $A^{*}$ and ${}^{*}\!A$ are both represented in the same way: by a wire labeled $A$ running from right to left. The unit and counit are represented as half turns:

More generally, if $A$ is a composite object represented by a number of wires, then $A^{*}$ and ${}^{*}\!A$ are represented by the same set of wires running backward (rotated by 180 degrees), and the units and counits are represented as multiple wires turning.

The two diagrams in (4.1), where $B=A^{*}$ , translate into the graphical language as follows:

For any morphism $f:A\rightarrow B$ , it is possible to define morphisms $f^{*}:B^{*}\rightarrow A^{*}$ and ${}^{*}\!f:{}^{*}\!B\rightarrow{}^{*}\!A$ , called the adjoint mates of $f$ , as follows:

With these definitions, $(-)^{*}$ and ${}^{*}\!(-)$ become contravariant functors.

A well-formed equation between morphisms in the language of autonomous categories follows from the axioms of autonomous categories if and only if it holds in the graphical language up to planar isotopy.

Here, the notion of planar isotopy is the same as before, except that the wires are of course no longer restricted to being oriented left-to-right during the deformation. However, the ability to turn wires upside down does not extend to boxes: the notion of isotopy for this theorem does not include the ability to rotate boxes. See Joyal and Street for a more precise statement.

The proof by Joyal and Street assumes that the diagrams are piecewise linear.

Note that the same theorem applies to left autonomous, right autonomous, or autonomous categories. Indeed, each individual term in the language of autonomous categories involves only finitely many duals, and thus may be translated into a term of (say) left autonomous categories by replacing each object variable $A$ by $A^{***\ldots*}$ , for a sufficiently large, even number of $*$ ’s. The resulting term maps to the same diagram.

The same coherence theorem also holds for categories that are only right (or left) autonomous. This is a consequence of the following proposition.

Each right (or left) autonomous category can be fully embedded in an autonomous category.

Let ${\bf C}$ be a right autonomous category, and consider the strong monoidal functor $F:{\bf C}\rightarrow{\bf C}$ given by $F(A)=A^{**}$ . This functor is full and faithful, and every object in the image of $F$ has a left dual. Now let $\hat{\bf C}$ be the colimit (in the large category of right autonomous categories and strong monoidal functors) of the sequence

Then $\hat{\bf C}$ is autonomous, and ${\bf C}$ is fully and faithfully embedded in $\hat{\bf C}$ . The proof for left autonomous categories is analogous. $\Box$

A well-formed equation between morphisms in the language of right (left) autonomous categories follows from the axioms of right (left) autonomous categories if and only if it holds in the graphical language up to planar isotopy.

It suffices to show that an equation (in the language of right autonomous categories) holds in all right autonomous categories if and only if it holds in all autonomous categories. The “only if” direction is trivial, since every autonomous category is right autonomous. For the opposite direction, suppose some equation holds in all autonomous categories, and let ${\bf C}$ be a right autonomous category. Then ${\bf C}$ can be faithfully embedded in an autonomous category $\hat{\bf C}$ . By assumption, the equation holds in $\hat{\bf C}$ , and therefore also in ${\bf C}$ , since the embedding is faithful. $\Box$

Technicalities

The diagrams of autonomous categories, and the concept of well-formed equation in the coherence theorem, are defined relative to the notion of an autonomous signature. These were called autonomous tensor schemes by Joyal and Street . We give a non-strict version of the definition.

[21, Def. 2.5] Given a set $\Sigma_{0}$ of object variables, let $\mathop{\textrm{\rm Aut}}\nolimits(\Sigma_{0})$ denote the free $(\otimes,I,{}^{*}\!(-),(-)^{*})$ -algebra generated by $\Sigma_{0}$ , i.e., the set of object terms built from object variables and $I$ via the operations $\otimes$ , ${}^{*}\!(-)$ , and $(-)^{*})$ . For example, if $A,B\in\Sigma_{0}$ , then the term $B^{*}\otimes({}^{**}I\otimes A)^{*}$ is an element of $\mathop{\textrm{\rm Aut}}\nolimits(\Sigma_{0})$ .

An autonomous signature consists of a set $\Sigma_{0}$ of object variables, a set $\Sigma_{1}$ of morphism variables, and a pair of functions $\mathop{\textrm{\rm dom}}\nolimits,\mathop{\textrm{\rm cod}}\nolimits:\Sigma_{1}\rightarrow\mathop{\textrm{\rm Aut}}\nolimits(\Sigma_{0})$ .

The concept of a right autonomous signature and left autonomous signature are defined analogously. The remaining graphical languages in this Section 4 are all given relative to an autonomous signature.

Functors and natural transformations of autonomous categories.

Any strong monoidal functor preserves exact pairings: if $\eta:I\rightarrow B\otimes A$ and $\epsilon:A\otimes B\rightarrow I$ define an exact pairing, then so do

In particular, if ${\bf C}$ and ${\bf D}$ are autonomous categories and $F:{\bf C}\rightarrow{\bf D}$ is a monoidal functor, by uniqueness of duals, there will be a unique induced natural isomorphism $F(A^{*})\cong(FA)^{*}$ such that

$\scriptstyle{\textrm{\rm id}\otimes{\cong}}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mrow><mover accent="true"><mi>F</mi><mo>^</mo></mover><msub><mi>ϵ</mi><mi>A</mi></msub></mrow></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{\hat{F}\epsilon_{A}}</annotation></semantics></math>F^ϵA\textstyle{I,}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>F</mi><mi>A</mi><mo>⊗</mo><mo stretchy="false">(</mo><mi>F</mi><mi>A</mi><msup><mo stretchy="false">)</mo><mo lspace="0em" rspace="0em">∗</mo></msup><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{FA\otimes(FA)^{*}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>FA⊗(FA)∗\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{\epsilon_{FA}}$ and similarly for $F({}^{*}\!A)\cong{}^{*}\!(FA)$ .

For natural transformations, we have the following lemma:

Suppose $\tau:F\rightarrow G$ is a monoidal natural transformation between strong monoidal functors $F,G:{\bf C}\rightarrow{\bf D}$ . If $A$ has a right dual $A^{*}$ in ${\bf C}$ , then $\tau_{A^{*}}$ and $(\tau_{A})^{*}$ are mutually inverse in ${\bf D}$ (up to the above canonical isomorphism), or more precisely:

In particular, if ${\bf C}$ is autonomous, then any such monoidal natural transformation is invertible.

Coherence and free autonomous categories.

The graphical language, as we have defined it above for autonomous categories, is sufficient for the purposes of Theorem 4.5. However, it does not characterize the free autonomous category over an autonomous signature as stated. For example, consider a signature with a single morphism variable $f:A\rightarrow A$ . The problem is that there are clearly some diagrams, such as

which are not translations of any well-formed term of autonomous categories. Indeed, for this diagram to correspond to a well-formed term, we would have to have e.g. $f:A^{**}\rightarrow A$ or $f:A\rightarrow{}^{**}A$ .

Joyal and Street characterize the free autonomous category by equipping each edge with a winding number. Effectively, the horizontal segments of edges are labeled with pairs $(A,n)$ , where $A$ is an object variables and $n$ is an integer winding number. Left-to-right segments have even winding numbers, right-to-left segments have odd winding numbers, and winding numbers increase by one on counterclockwise turns, and decrease by one on clockwise turns. The winding numbers on the input and output of each box, and on the global inputs and outputs, are restricted to be consistent with the domain and codomain information, where e.g. $A^{**}$ corresponds to $(A,2)$ , and ${}^{***}B$ to $(B,-3)$ . See for precise details. Here is an example of a well-formed diagram of type $I\rightarrow B^{**}\otimes A$ , where $g:I\rightarrow A\otimes B$ :

The graphical language (with winding numbers) of autonomous categories over an autonomous signature $\Sigma$ , up to planar isotopy of diagrams, forms a free autonomous category over $\Sigma$ .

We remark that if a diagram of planar autonomous categories can be labeled with winding numbers, then this labeling is necessarily unique. In particular, for the purposes of Theorem 4.5, there is no harm in dropping the winding numbers, because by hypothesis, the theorem only considers diagrams that are the translation of well-formed terms, whose winding numbers can therefore uniquely reconstructed.

2 (Planar) pivotal categories

A pivotal category is an autonomous category with a suitable isomorphism $A\cong A^{**}$ .

A pivotal category is a right autonomous category equipped with a monoidal natural isomorphism $i_{A}:A\rightarrow A^{**}$ .

Note that any pivotal category is immediately left autonomous, therefore autonomous. The requirement that $i_{A}$ is a monoidal natural transformation here means that $i_{I}$ is the canonical isomorphism $I\cong I^{**}$ , and that the following diagram commutes, where the horizontal arrow is the canonical isomorphism derived from the autonomous structure:

The following property, which is sometimes taken as part of the definition of pivotal categories [19, Def. 3.1.1], is a direct consequence of Saavedra Rivano’s Lemma (Lemma 4.9).

In any pivotal category, the following diagram commutes:

One can equivalently define a pivotal category as an autonomous category equipped with a monoidal natural isomorphism (of contravariant monoidal functors) $\phi:A^{*}\xrightarrow{\cong}{}^{*}\!A$ . This was done by Freyd and Yetter . Condition (S) of [16, Def. 4.1] is also a consequence of Saavedra Rivano’s Lemma, and is therefore redundant.

Freyd and Yetter also introduced the term sovereign category for a pivotal category.

A pivotal functor between pivotal categories is a monoidal functor that also satisfies

The graphical language for pivotal categories is the same as that for autonomous categories, where the isomorphism $i_{A}:A\rightarrow A^{**}$ is represented like an identity map. Of course, there are now additional diagrams that are the translation of well-formed terms. For example, when $f:A\rightarrow A$ , then (4.2) is a well-formed diagram of pivotal categories, but not of autonomous categories. Indeed, in the case of pivotal categories, the problem of winding numbers (discussed before Theorem 4.10) disappears, as winding numbers are taken modulo 2, and hence add nothing beyond orientation.

A well-formed equation between morphisms in the language of pivotal categories follows from the axioms of pivotal categories if and only if it holds in the graphical language up to planar isotopy, including rotation of boxes.

Only special cases of this theorem have been proved in the literature. Freyd and Yetter [16, Thm. 4.4] considered the case of the free pivotal category generated by a category. In our terminology, this means that they only considered diagrams for pivotal categories over simple signatures, rather than over autonomous signatures. In other words, they only considered boxes of the form

with exactly one input and one output. Joyal and Street’s draft report claims the general result but contains no proof.

The notion of planar isotopy for pivotal categories includes the ability to rotate boxes in the plane of the diagram. For example, the following two diagrams are isotopic in this sense:

This also explains why we have marked a corner of each box. With the ability to rotate boxes, we need to keep track of their “natural” orientation, so that the diagrams from (4.4) can also be represented like this:

$\textstyle{f}$ More generally, the adjoint mate of $f:A\rightarrow B$ can be represented by a rotated box:

Also note that is $f$ is a composite diagram, then the whole diagram may be rotated to obtain $f^{*}$ .

3 Spherical pivotal categories

A pivotal category is spherical if for all objects $A$ and morphisms $f:A\rightarrow A$ ,

The intuition behind the “spherical” axioms is that diagrams should be embedded in a 2-sphere, rather than the plane. It is then obvious that the left-hand side of (4.6) can be continuously transformed into the right-hand side, namely by moving the loop across the back of the 2-sphere.

The spherical axiom is not sound for the graphical language of diagrams embedded in the 2-sphere. The problem is that the notion of “diagram embedded in the 2-sphere” is not compatible with composition or tensor. The following is a consequence of the spherical axiom, but does not hold up to isotopy in the 2-sphere.

Note that this counterexample is similar to the spacial axiom (3.2), but does not quite imply it. If one adds the spacial axiom, as we are about to do, then any notion of isotopy is lost and equivalence of diagrams collapses to isomorphism.

4 Spacial pivotal categories

A pivotal category is spacial if it satisfies the spacial axiom (3.2) and the spherical axiom (4.6).

The graphical language for spacial pivotal categories is the same as that for planar pivotal categories, except that equivalence of diagrams is now taken up to isomorphism. Clearly, the axioms are sound for the graphical language. We conjecture that they are also complete.

A well-formed equation between morphisms in the language of spacial pivotal categories follows from the axioms of spacial pivotal categories if and only if it holds in the graphical language up to isomorphism.

5 Braided autonomous categories

An braided autonomous category is an autonomous category that is also braided (as a monoidal category). The notion of braided autonomous categories is not extremely natural, as the graphical language is only sound for a restricted form of isotopy called regular isotopy. Nevertheless, it is useful to collect some facts about braided autonomous categories.

A braided monoidal category is autonomous if and only if it is right autonomous.

If $\eta:I\rightarrow B\otimes A$ and $\epsilon:A\otimes B\rightarrow I$ form an exact pairing, then so do $c^{-1}_{A,B}\circ\eta:I\rightarrow A\otimes B$ and $\epsilon\circ c_{B,A}:B\otimes A\rightarrow I$ . Therefore any right dual of $A$ is also a left dual of $A$ . $\Box$

In any braided autonomous category ${\bf C}$ , we can define a natural isomorphism $b_{A}:A^{**}\rightarrow A$ . This follows from the proof of Lemma 4.17, using the fact that both $A$ and $A^{**}$ are right duals of $A^{*}$ . More concretely, $b_{A}$ and its inverse are defined by:

Here we have written, without loss of generality, as if ${\bf C}$ were strict monoidal. Graphically, $b_{A}$ and its inverse look like this:

The graphical language braided autonomous categories is obtained simply by adding braids to the graphical language of autonomous categories. However, the correct notion of equivalence of diagrams is neither planar isotopy (like for autonomous categories), nor 3-dimensional isotopy (like for braided monoidal categories), but an in-between notion called regular isotopy .

It is well-known that 3-dimensional isotopy of links and tangles is equivalent to planar isotopy of their (non-degenerate) projections onto a 2-dimensional plane, plus the three Reidemeister moves shown as (R1)–(R3) in Figure 3. To extend this to diagrams with nodes, one also has to add the moves ( $\Lambda$ 1) and ( $\Lambda$ 2).

Regular isotopy is defined to be the equivalence obtained by dropping Reidemeister move (R1). Note that regular isotopy is an equivalence on 2-dimensional representation of 3-dimensional diagrams (and not of 3-dimensional diagrams themselves).

A well-formed equation between morphisms in the language of braided autonomous categories follows from the axioms of braided autonomous categories if and only if it holds in the graphical language up to regular isotopy.

Only special cases of this theorem have been proved in the literature. Freyd and Yetter [16, Thm. 3.8] proved this only for diagrams over a simple signature.

6 Braided pivotal categories

Let ${\bf C}$ be a braided autonomous category. Then giving a twist $\theta_{A}:A\rightarrow A$ on ${\bf C}$ (making ${\bf C}$ into a balanced category) is equivalent to giving a pivotal structure $i_{A}:A\rightarrow A^{**}$ (making ${\bf C}$ into a pivotal category).

The lemma is remarkable because the concept of a braided autonomous category does not include any assumption relating the braided structure to the autonomous structure. Moreover, the axioms for a twist depend only on the braided structure, whereas the axioms for a pivotal structure depend only on the autonomous structure. Yet, they are equivalent if ${\bf C}$ is braided autonomous.

Proof of Lemma 4.20: Recall the natural isomorphism $b_{A}:A^{**}\rightarrow A$ that was defined in Section 4.5 for any braided autonomous category. Given a twist $\theta_{A}:A\rightarrow A$ , we define a pivotal structure by

Conversely, given a pivotal structure $i_{A}:A\rightarrow A^{**}$ , we define a twist by

The two constructions are clearly each other’s inverse. To verify their properties, it is obvious that $i_{A}$ is a natural isomorphism if and only if $\theta_{A}$ is a natural isomorphism. Moreover, $\theta_{I}=\textrm{\rm id}$ iff $i_{I}=b^{-1}_{I}$ , and $b^{-1}_{I}$ is the canonical isomorphism $I\cong I^{**}$ . What remains to be shown is that $\theta$ satisfies equation (3.3) if and only if $i$ satisfies equation (4.3). However, this is a direct consequence of the following fact about $b$ , which is easily verified:

$\scriptstyle{\cong}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>c</mi><mrow><mi>A</mi><mo separator="true">,</mo><mi>B</mi></mrow></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{c_{A,B}}</annotation></semantics></math>cA,B\textstyle{B^{**}\otimes A^{**}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mrow><msub><mi>b</mi><mi>B</mi></msub><mo>⊗</mo><msub><mi>b</mi><mi>A</mi></msub></mrow></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{b_{B}\otimes b_{A}}</annotation></semantics></math>bB⊗bA\textstyle{(A\otimes B)^{**}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><msub><mi>b</mi><mrow><mi>A</mi><mo>⊗</mo><mi>B</mi></mrow></msub></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{b_{A\otimes B}}</annotation></semantics></math>bA⊗B\textstyle{A\otimes B}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mrow><mi>B</mi><mo>⊗</mo><mi>A</mi><mi mathvariant="normal">.</mi><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle><mstyle mathcolor="#cc0000"><mtext>\ignorespaces</mtext></mstyle></mrow></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{B\otimes A.\ignorespaces\ignorespaces\ignorespaces\ignorespaces}</annotation></semantics></math>B⊗A.\ignorespaces\ignorespaces\ignorespaces\ignorespaces\scriptstyle{c_{B,A}}$ $\Box$

A braided pivotal category is the same thing as a balanced autonomous category. $\Box$

While Lemma 4.20 establishes a one-to-one correspondence between twists and pivotal structures, the correspondence is not canonical. Indeed, instead of (4.7) and (4.8), we could have equally well used

In fact, there are a countable number of such similar one-to-one correspondences, all induced by the existence of a monoidal natural transformation $b^{\prime}_{A}{}^{-1}\circ i_{A}\circ b_{A}\circ i_{A}:A\rightarrow A$ . They all coincide if and only if the category is tortile, as discussed in the next section.

The graphical language for braided pivotal categories is the same as the graphical language for pivotal categories, with the addition of braids. Equivalence of diagrams is up to regular isotopy, just as for braided autonomous categories (see Section 4.5).

A well-formed equation between morphisms in the language of braided pivotal categories follows from the axioms of braided pivotal categories if and only if it holds in the graphical language up to regular isotopy.

Only special cases of this theorem have been proved in the literature. Freyd and Yetter [16, Thm. 4.4] proved this only for diagrams over a simple signature.

holds up to regular isotopy, as it can be proved using only the Reidemeister moves (R2) and (R3). It is therefore valid in braided pivotal categories (or even braided autonomous categories). On the other hand, the equation

holds up to isotopy, but not up to regular isotopy (because regular isotopy preserves total curvature, as pointed out by Freyd and Yetter [15, p. 169]). It is therefore not valid in braided pivotal categories. The use of regular isotopy does not seem natural, and this is precisely the reason why Joyal and Street introduced tortile categories, which we discuss in the next section.

A braided pivotal category is not in general spherical (and therefore also not spacial). Indeed, instead of the spherical axiom (4.6), only the following holds up to regular isotopy:

Along with Remark 4.22, this is further evidence that braided pivotal categories (and braided autonomous categories) are not “natural” notions.

7 Tortile categories

Consider a braided pivotal category, which is equivalently balanced autonomous via (4.7) and (4.8). For any object $A$ the following are equivalent:

$(\epsilon_{A^{*}}\otimes\textrm{\rm id}_{A})\circ(\textrm{\rm id}_{A^{*}}\otimes c^{-1}_{A^{**},A})\circ(\eta_{A}\otimes\textrm{\rm id}_{A^{**}})\circ i_{A}\circ(\epsilon_{A^{*}}\otimes\textrm{\rm id}_{A})\circ(\textrm{\rm id}_{A^{*}}\otimes c_{A,A^{**}})\circ(\eta_{A}\otimes\textrm{\rm id}_{A^{**}})\circ i_{A}=\textrm{\rm id}_{A},$ or graphically:

The proof is a straightforward calculation, but it is best explained by the fact that the following hold in the graphical language:

Therefore, the equation (b) is equivalent to

The condition in Lemma 4.27(a) holds if and only if the two definitions of $\theta_{A}$ from (4.8) and (4.10) coincide.

A tortile category is a braided pivotal category satisfying the condition of Lemma 4.27(a). Equivalently, a tortile category is a balanced autonomous category satisfying the condition of Lemma 4.27(b).

A tortile category is also sometimes called a ribbon category, see e.g. .

The graphical language for tortile categories is like the graphical language for braided pivotal categories, except that morphisms are represented by ribbons, rather than wires. These ribbons are just like the ones for balanced categories from Section 3.4. Units and counits are represented in the obvious way, for example

The twist map $\theta_{A}:A\rightarrow A$ can be represented in several equivalent ways:

Note that these diagrams are equivalent up to framed 3-dimensional isotopy, and define the same morphism in a tortile category. (On the other hand, in a mere braided pivotal category, the latter two diagrams are not equal). Also note that the map $b_{A}$ from Section 4.5 is also represented in the graphical language as

but this is of type $b_{A}:A^{**}\rightarrow A$ , whereas $\theta_{A}:A\rightarrow A$ . They differ, of course, only by an invisible pivotal map $i_{A}:A\rightarrow A^{**}$ .

A well-formed equation between morphisms in the language of tortile categories follows from the axioms of tortile categories if and only if it holds in the graphical language up to framed 3-dimensional isotopy.

Only special cases of this theorem have been proved in the literature. Shum [34, Thm. 6.1] proved it for the case of the free tortile category generated by a category, i.e., for diagrams over a simple signature only.

8 Compact closed categories

A compact closed category is a tortile category that is symmetric (as a balanced monoidal category) in the sense of Section 3.5. Equivalently, because of Remark 3.10, a compact closed category is a tortile category in which $\theta_{A}=\textrm{\rm id}_{A}$ for all $A$ .

The definition can be simplified. Notice that a right autonomous symmetric monoidal category is automatically autonomous (by Lemma 4.17), balanced (with $\theta_{A}=\textrm{\rm id}_{A}$ ) and therefore pivotal (by Lemma 4.20). Moreover, it is tortile (because $\theta_{A^{*}}=(\theta_{A})^{*}=\textrm{\rm id}_{A^{*}}$ ). We can therefore define:

A compact closed category is a right autonomous symmetric monoidal category.

By analogy with Remark 3.11, it is possible for a compact closed category to possess a non-trivial twist (with the associated non-trivial pivotal structure), in addition to the trivial twist $\theta_{A}=\textrm{\rm id}_{A}$ , making it into a tortile category. In other words, for a given tortile category, the symmetry condition $c_{A,B}=c^{-1}_{B,A}$ does not in general imply $\theta_{A}=\textrm{\rm id}_{A}$ . However, it does imply $\theta_{A}^{2}=\textrm{\rm id}_{A}$ , as the following argument shows:

To construct an example where $\theta\neq\textrm{\rm id}$ , consider the category ${\bf C}$ of finite-dimensional real vector spaces and linear functions. Define an equivalence relation on objects by $A\sim B$ iff $\dim(A\otimes B)$ is a square. Then define a subcategory ${\bf C}_{\sim}$ by

where $p_{i}$ is the $i$ th prime number. Finally, define the twist map $\theta_{A}$ as multiplication by the scalar $\phi(\dim(A))$ , or as $\textrm{\rm id}_{A}$ if $A$ is 0-dimensional. With this twist, ${\bf C}_{\sim}$ is tortile. In fact, this shows that there exists a continuum of possible twists on ${\bf C}_{\sim}$ .

The monoidal category $(\textrm{\bf Rel},\times)$ is compact closed with $A^{*}=A$ . The category $(\textrm{\bf FdVect},\otimes)$ of finite dimensional vectors spaces is compact closed with $A^{*}$ the dual space of $A$ , and similarly for the category of finite dimensional Hilbert spaces $(\textrm{\bf FdHilb},\otimes)$ . The corresponding categories of possibly infinite dimensional spaces are not autonomous. $(\textrm{\bf Cob},+)$ is compact closed with $A^{*}$ equal to $A$ with reversed orientation.

The graphical language for compact closed categories is like that of tortile categories, except that we remove the framing and twist maps, and use symmetries instead of braidings.

A well-formed equation between morphisms in the language of compact closed categories follows from the axioms of compact closed categories if and only if it holds, up to isomorphism of diagrams, in the graphical language.

The special case of diagrams over a simple signature was proven by Kelly and Laplaza [27, Thm. 8.2]. The general case does not appear in the literature.

Traced categories

The graphical languages considered in Section 3 were progressive, which means that all wires were oriented left-to-right. By contrast, the graphical languages of autonomous categories in Section 4 allow wires to be oriented left-to-right or right-to-left. We now turn out attention to an intermediate notion, namely traced categories.

Like autonomous graphical languages, traced graphical languages permit loops, but with a restriction: all wires must be directed left-to-right at their endpoints. In other words, traced diagrams are like autonomous diagrams, but are taken relative to a monoidal signature (see Section 3.1), rather than an autonomous signature (see Section 4.1). Table 4 shows a typical example of a traced diagram, and a typical example of an autonomous diagram that is not a traced diagram.

Logically, we should have considered traced categories before pivotal categories, because traced categories have less structure than pivotal categories (i.e., every pivotal category is traced, and not the other way around). However, many of the coherence theorems of this section are consequences of the corresponding theorems for pivotal categories, and therefore it made sense to present the pivotal notions first.

Symmetric traced categories and their graphical language (in the strict monoidal case, and with one additional axiom) were first introduced in the 1980’s by Ştefănescu and Căzănescu under the name “biflow” . Joyal, Street, and Verity later rediscovered this notion independently, generalized it to balanced monoidal categories, and proved the fundamental embedding theorem relating balanced traced categories to tortile categories .

Joyal, Street, and Verity use the term traced monoidal category. However, I prefer traced category, usually prefixed by an adjective such as planar, spacial, balanced, symmetric. The word “monoidal” is redundant, because one cannot have a traced structure without a monoidal structure. Also, by putting the adjective before the word “traced”, rather than after it, we make it clear that the traced structure, and not just the underlying monoidal structure, if being modified.

A right trace on a monoidal category is a family of operations

satisfying the following four axioms. For notational convenience, we assume without loss of generality that the monoidal structure is strict.

Tightening (naturality in $A,B$ ): $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}((g\otimes\textrm{\rm id}_{X})\circ f\circ(h\otimes\textrm{\rm id}_{X}))=g\circ(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}f)\circ h$ ;

Sliding (dinaturality in $X$ ): $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{Y}(f\circ(\textrm{\rm id}_{A}\otimes g))=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}((\textrm{\rm id}_{B}\otimes g)\circ f)$ , where $f:A\otimes X\rightarrow B\otimes Y$ and $g:Y\rightarrow X$ ;

Vanishing: $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{I}f=f$ and $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X\otimes Y}f=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{Y}(f))$ ;

Strength. $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}(g\otimes f)=g\otimes\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}f$ .

A (planar) right traced category is a monoidal category equipped with a right trace.

These axioms are similar to those of Joyal, Street, and Verity , except that we have omitted the yanking axioms which does not apply in the planar case, and we have replaced the non-planar “superposing” axiom by the planar “strength” axiom. I do not know whether this set of planar axioms appears in the literature.

The right trace of a diagram $f:A\otimes X\rightarrow B\otimes X$ is graphically represented by drawing a loop from the output $X$ to the input $X$ , as follows:

Note that in the graphical language of right traced categories, parts of wires can be oriented right-to-left, but each wire must be oriented left-to-right near the endpoints. The four axioms of right traced categories are illustrated in the graphical language in Table 5.

The axioms of right traced categories are obviously sound for the graphical language, up to planar isotopy. We conjecture that they are also complete.

A well-formed equation between morphism terms in the language of right traced categories follows from the axioms of right traced categories if and only if it holds in the graphical language up planar isotopy.

This is a weak conjecture, in the sense that there is not much empirical evidence to support it, nor is there an obvious strategy for a proof. If this conjecture turns out to be false, the axioms for right traced categories should be amended until it becomes true.

The concept of a left trace is defined similarly as a family of operations

satisfying symmetric axioms. A left trace is graphically depicted as follows:

We say that a monoidal functor $F$ preserves right traces if $F(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}f)=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{FX}((\phi^{2})^{-1}\circ Ff\circ\phi^{2})$ , and similarly for left traces.

2 Planar traced categories

A planar traced category is a monoidal category equipped with a right trace and a left trace, such that the two traces satisfy three additional axioms:

Interchange: $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{Y}f)=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{Y}(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}f)$ , for all $f:Y\otimes A\otimes X\rightarrow Y\otimes B\otimes X$ ;

Left pivoting: $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{B}(\textrm{\rm id}_{B}\otimes f)=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{A}(f\otimes\textrm{\rm id}_{A})$ , for all $f:I\rightarrow A\otimes B$ ;

Right pivoting: $\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{B}(\textrm{\rm id}_{B}\otimes f)=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{A}(f\otimes\textrm{\rm id}_{A})$ , for all $f:A\otimes B\rightarrow I$ .

The graphical language of planar traced categories consists of diagrams using the left and right trace together, modulo planar isotopy. The axioms of interchange, left pivoting, and right pivoting are shown graphically in Table 6. Compare also equation (4.4) on page 4.4.

The axioms are clearly sound; we conjecture that they are also complete:

A well-formed equation between morphism terms in the language of planar traced categories follows from the axioms of planar traced categories if and only if it holds in the graphical language up planar isotopy.

As for right traced categories, this conjecture is weak. If it turns out to be false, then one should amend the axioms of planar traced categories accordingly.

Even if the conjecture is true, the graphical language does not in itself give an easy description of the free planar traced category. This is because there are diagrams, such as the following, that “look” planar traced, but are not actually the diagram of any planar traced term (not even up to planar isotopy).

It is not obvious how to characterize the “planar traced” diagrams intrinsically, or how to extend the notion of planar traced categories to encompass all such diagrams.

An autonomous category is not necessarily traced. However, every pivotal category is planar traced with the obvious definitions of left and right trace:

In the graphical language, this looks just like the diagrams (5.1) and (5.2). As a consequence, each diagram of planar traced categories can be regarded as a diagram of planar pivotal categories, but not the other way around.

3 Spherical traced categories

The concept of a spherical traced category is analogous to that of spherical pivotal categories from Section 4.3.

A planar traced category satisfies the spherical axiom if for all $f:A\rightarrow A$ ,

or equivalently, in the graphical language:

A spherical traced category is a planar traced category satisfying the spherical axiom.

Every spherical pivotal category is spherical traced.

Just like for spherical pivotal categories, the graphical language of spherical traced categories is not coherent for any geometrically useful notion of equivalence of diagrams.

4 Spacial traced categories

A spacial traced category is a planar traced category if it satisfies the spacial axiom (3.2) and the spherical axiom (5.3).

The graphical language for spacial traced categories is the same as that for planar traced categories, except that equivalence of diagrams is now taken up to isomorphism.

A well-formed equation between morphism terms in the language of spacial traced categories follows from the axioms of spacial traced categories if and only if it holds, up to isomorphism of diagrams, in the graphical language.

Every spacial pivotal category is clearly spacial traced. I do not know whether conversely every spacial traced category can be faithfully embedded in a spacial pivotal category. If this is true, then Conjecture 5.6 follows from Conjecture 4.16.

5 Braided traced categories

Braided traced categories, like braided pivotal categories, are a somewhat unnatural notion, because coherence is only satisfied up to regular isotopy. (If one considers full isotopy, one obtains the more natural notion of balanced traced categories, which we will consider in the next section). Nevertheless, we include this section on braided traced categories, not least because it is the first traced notion for which we can actually prove a coherence theorem (modulo Caveat 4.24).

A braided traced category is a planar traced category with a braiding (as a monoidal category), such that

The axiom (5.4) does not follow from the remaining axioms.

In the presence of the remaining axioms, (5.4) is equivalent to

In the presence of the remaining axioms of braided traced categories, the left and right pivoting axioms are redundant.

(a) To see this, consider morphism terms in the language of braided traced categories with one object generator and no morphism generators. Define the degree of a term to the be tensor product of all traced-out objects, i.e., $\deg(\textrm{\rm id})=I$ , $\deg(f\circ g)=\deg(f)\otimes\deg(g)$ , $\deg(\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{X}f)=X\otimes\deg(f)$ , etc. This is well-defined up to isomorphism. All the axioms of planar traced categories and braided categories respect degree; the only axioms where the left-hand side and right-hand side could potentially have different degree are sliding in Table 5 and pivoting in Table 6. However, in the absence of morphism generators, it is easy to show that all morphism terms are of the form $f:A\rightarrow B$ where $A\cong B$ . Therefore, neither sliding nor pivoting change the degree (the latter because it is vacuous). Therefore degree is an invariant. On the other hand, (5.4) is not degree-preserving; therefore it cannot follow from the other axioms.

(b) The following graphical proof sketch can be turned into an algebraic proof:

Each braided traced category possesses a balanced structure (as a braided monoidal category) given by $\theta_{A}=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{A}c^{-1}_{A,A}$ , with inverse $\theta^{-1}_{A}=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{A}c_{A,A}$ (cf. (5.4)). However, this twist is not canonical; for example, another twist can be defined by $\theta^{\prime}_{A}=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm R}}^{A}c_{A,A}$ with inverse $\theta^{\prime}_{A}{}^{-1}=\mathop{\textrm{\rm Tr}}\nolimits_{\textrm{\rm L}}^{A}c^{-1}_{A,A}$ (cf. (5.5)). In fact, there are countably many other possible twists. This is entirely analogous to Remark 4.22. The various twists coincide if and only if the yanking equation (5.6) holds, yielding a balanced traced category as discussed in Section 5.6 below.

We note that every braided pivotal category is braided traced, with the traced structure as given in Remark 5.5. Moreover, there is an embedding theorem giving a partial converse:

Every braided traced category ${\bf C}$ can by fully and faithfully embedded into a braided pivotal category $\mathop{\textrm{\rm Int}}({\bf C})$ , via a braided traced functor.

The proof exactly mimics the Int-construction of Joyal, Street, and Verity , except that we must replace the twist by , and be careful only to use the braided traced axioms. We omit the details, which are both lengthy and tedious. $\Box$

A braided traced category is not necessarily spherical (and therefore not spacial). This is analogous to Remark 4.26.

The graphical language for braided traced categories is obtained by adding braids to the graphical language of planar traced categories. Equivalence of diagrams is up to regular isotopy (see Section 4.5).

A well-formed equation between morphisms in the language of braided traced categories follows from the axioms of braided traced categories if and only if it holds in the graphical language up to regular isotopy.

Soundness is easy to check by inspection of the axioms. Completeness is a consequence of Theorems 4.23 and 5.10. Namely, consider an equation in the language of braided traced categories that holds in the graphical language up to regular isotopy. The diagrams corresponding to the left-hand side and right-hand side of the equation can also be regarded as diagrams of braided pivotal categories, and since they are regularly isotopic, the equation holds in all braided pivotal categories by Theorem 4.23. Since any braided traced category ${\bf C}$ can be faithfully embedded in a braided pivotal category $\mathop{\textrm{\rm Int}}({\bf C})$ by Theorem 5.10, an equation that holds in $\mathop{\textrm{\rm Int}}({\bf C})$ must also hold in ${\bf C}$ . It follows that the equation in question holds in all braided traced categories ${\bf C}$ , and therefore, it is a consequence of the axioms. $\Box$

Because of the dependence on Theorem 4.23, Caveat 4.24 also applies here.

6 Balanced traced categories

A balanced traced category is a balanced monoidal category equipped with a right trace $\mathop{\textrm{\rm Tr}}\nolimits$ , and satisfying the following yanking axioms:

The graphical language of balanced traced categories combines the ribbons and twists of balanced categories with the loops of traced categories. The trace is represented as expected:

Note that there is no need to postulate a left trace, because a left trace is definable from the right trace and braidings as follows:

The defined left trace automatically satisfies interchange and the pivoting axioms (Table 6), as well as the spherical axiom (5.3) and the braided traced axiom (5.4). The spacial axiom (3.2) is satisfied by any braided monoidal category. Therefore, any balanced traced category is spacial traced and braided traced.

The graphical validity of the yanking axiom is easily verified using a shoe string:

Every tortile category is balanced traced, with the traced structure as given in Remark 5.5. Moreover, there is an embedding theorem:

Every balanced traced category can be fully and faithfully embedded into a tortile category, via a balanced traced functor.

A well-formed equation between morphisms in the language of balanced traced categories follows from the axioms of balanced traced categories if and only if it holds in the graphical language up to framed isotopy in 3 dimensions.

This follows from Theorems 4.30 and 5.15, by the exact same argument that was used in the proof of Theorem 5.12. $\Box$

Because of the dependence on Theorem 4.30, Caveat 4.31 also applies here.

In any braided monoidal category with a right trace, the twist and its inverse are definable by equation (5.6). These maps are automatically natural and satisfy $\theta_{I}=\textrm{\rm id}_{I}$ and (3.3). However, they are not automatically inverse to each other. Therefore, a balanced traced category could be equivalently defined as a braided monoidal category with a right trace, satisfying

7 Symmetric traced categories

A symmetric traced category is a symmetric monoidal category with a right trace $\mathop{\textrm{\rm Tr}}\nolimits$ , satisfying the symmetric yanking axiom:

Because of Remark 3.10, a symmetric traced category can be equivalently defined as a balanced traced category in which $\theta_{A}=\textrm{\rm id}_{A}$ for all $A$ .

Obviously every compact closed category is symmetric traced with the structure from Remark 5.5. Here, too, we have an embedding theorem:

Every symmetric traced category can be fully and faithfully embedded into a compact closed category, via a symmetric traced functor.

Consider the category Rel of sets and relations, with biproducts given by disjoint union $A+B$ . Given a relation $R:A+X\rightarrow B+X$ , define its trace $\mathop{\textrm{\rm Tr}}\nolimits^{X}(R):A\rightarrow B$ by $(a,b)\in\mathop{\textrm{\rm Tr}}\nolimits^{X}(R)$ iff there exists $n\geq 0$ and $x_{1},\ldots,x_{n}\in X$ such that $a\,R\,x_{1}\,R\,x_{2}\,R\,\ldots\,R\,x_{n}\,R\,b$ . This defines a symmetric traced category which is not compact closed.

The graphical language is like that of planar traced categories, combined with the symmetry. A typical diagram looks like this:

The notion of equivalence of diagrams is isomorphism.

A well-formed equation between morphisms in the language of symmetric traced categories follows from the axioms of symmetric traced categories if and only if it holds in the graphical language up to isomorphism of diagrams.

A consequence of Theorems 4.33 and 5.20, as in Theorems 5.12 and 5.16.

Because of the dependence on Theorem 4.33, Caveat 4.34 also applies here.

Strict symmetric traced categories, with the additional axiom

first appear in the work of Ştefănescu under the name “biflow”. A precursor of the definition appears in , and the axioms were given their modern form by Căzănescu and Ştefănescu . The paper also contains a detailed proof sketch of coherence, namely, that the graphical language, modulo isomorphism and the equation (5.7), forms the free biflow over a monoidal signature. This proof sketch remains valid with respect to the modern definition, provided that one assumes coherence for symmetric monoidal categories.

Products, coproducts, and biproducts

In this section, we consider graphical languages for monoidal categories where the monoidal structure is given by a categorical product, coproduct, or biproduct. The main difference with the graphical languages of “purely” monoidal categories from Sections 3–5 is that equivalence of diagrams must now be defined up to diagrammatic equations.

In a category, a product of objects $A$ and $B$ is given by an object $A\times B$ , together with morphisms $\pi_{1}:A\times B\rightarrow A$ and $\pi_{2}:A\times B\rightarrow B$ , such that for all objects $C$ and pairs of morphisms $f:C\rightarrow A$ and $g:C\rightarrow B$ , there exists a unique morphism $h:C\rightarrow A\otimes B$ such that the following diagram commutes:

The unique morphism $h$ is often written as $h=\langle f,g\rangle$ . An object $I$ is terminal if for all objects $C$ , there exists a unique morphism $h:C\rightarrow I$ . A finite product category (or cartesian category) is a category with a chosen terminal object, and a chosen product for each pair of objects.

Equivalently, a finite product category can be described as a symmetric monoidal category, together with natural families of copy and erase maps

subject to a number of axioms, shown in Table 7.

We extend the graphical language of symmetric monoidal categories by adding the following representations of the copy and erase maps.

$\textstyle{A}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mo lspace="0em" rspace="0em">∙</mo></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{\bullet}</annotation></semantics></math>∙\textstyle{A}$ $\textstyle{A}$ Erase $\Diamond_{A}:A\rightarrow I$ $\textstyle{A}$ $\textstyle{\bullet}$ As usual, if $A$ is a composite object term, a wire labeled $A$ should be replaced by multiple parallel wires. Table 8 contains graphical representations of some of the axioms for finite product categories.

Note that the projections $\pi_{1}:A\times B\rightarrow A$ and $\pi_{2}:A\times B\rightarrow B$ , and the pairing $h:C\rightarrow A\otimes B$ of $f:C\rightarrow A$ and $g:C\rightarrow B$ , are represented graphically as follows:

Coherence.

As the equivalences in Table 8 demonstrate, coherence in the graphical language of finite product categories does not hold up to isomorphism or isotopy of diagrams. Rather, is holds up to manipulations of diagrams. So unlike the graphical languages considered in Sections 2–5, we now have to consider axioms on diagrams.

A well-formed equation between morphism terms in the language of finite product categories follows from the axioms of finite product categories if and only if it holds in the graphical language, up to isomorphism of diagrams and the diagrammatic manipulations shown in Table 8.

This theorem is a simple consequence of coherence for symmetric monoidal categories (Theorem 3.12), together with the fact that all the axioms of finite product categories, except those shown in Table 8, hold up to isomorphism of diagrams.

2 Coproducts

The definition of coproducts and initial objects is dual to that of products and terminal objects, i.e., it is obtained by reversing all the arrows in Section 6.1. Explicitly, an object is initial if for all objects $C$ , there exists a unique morphism $h:0\rightarrow C$ . A coproduct of objects $A,B$ is given by an object $A+B$ , together with morphisms $\iota_{1}:A\rightarrow A+B$ and $\iota_{2}:B\rightarrow A+B$ , such that for all objects $C$ and pairs of morphisms $f:A\rightarrow C$ and $g:B\rightarrow C$ , there exists a unique morphism $h:A+B\rightarrow C$ such that $h\circ\iota_{1}=f$ and $h\circ\iota_{2}=g$ . One often writes $h=[f,g]$ . A category with finite coproducts is also called a co-cartesian category.

Dualizing the presentation of Section 6.1, one can equivalently define a finite coproduct category as a symmetric monoidal category with natural families of merge and initial maps

satisfying the duals of the axioms in Table 7.

The graphical language of finite coproduct categories is obtained by dualizing that of finite product categories, with the duals of the axioms from Table 8.

3 Biproducts

An object is called a zero object if it is initial and terminal. If ${\bf 0}$ is a zero object, then there is a distinguished map $A\rightarrow{\bf 0}\rightarrow B$ between any two objects, denoted $0_{A,B}$ . A biproduct of objects $A_{1}$ and $A_{2}$ is given by an object $A_{1}\oplus A_{2}$ , together with morphisms $\iota_{i}:A_{i}\rightarrow A_{1}\oplus A_{2}$ and $\pi_{i}:A_{1}\oplus A_{2}\rightarrow A_{i}$ , for $i=1,2$ , such that $A\oplus B$ is a product with $\pi_{1},\pi_{2}$ , a coproduct with $\iota_{1},\iota_{2}$ and such that $\pi_{i}\circ\iota_{j}=\delta_{ij}$ . Here $\delta_{ii}=\textrm{\rm id}_{A_{i}}$ and $\delta_{ij}=0_{A_{j},A_{i}}$ when $i\neq j$ . We say that ${\bf C}$ is a biproduct category if it has a chosen zero object ${\bf 0}$ and a chosen biproduct for any pair of objects.

The axiom $\pi_{i}\circ\iota_{j}=\delta_{ij}$ is equivalent to the assertion that the symmetric monoidal structure defined by $\oplus$ “as a product” coincides with the symmetric monoidal structure defined by $\oplus$ “as a coproduct”. Therefore, a biproduct category is symmetric monoidal in a canonical way.

Equivalently, a biproduct category can be defined as a symmetric monoidal category, together with natural families of morphisms

satisfying the axioms in Table 7, as well as their duals.

The graphical language of biproducts is obtained by combining the graphical languages for products and coproducts. In this case, one has the equalities in Table 9, which are consequences of the naturality axioms in Table 8. Note that the axiom $\pi_{i}\circ\iota_{j}=\delta_{ij}$ holds automatically in the graphical language.

A well-formed equation between morphism terms in the language of biproduct categories follows from the axioms of biproduct categories if and only if it holds in the graphical language, up to isomorphism of diagrams, the diagrammatic manipulations shown in Table 8, and their duals.

This theorem is a simple consequence of coherence for symmetric monoidal categories, together with the fact that the axioms in Table 8 (and their duals) are exactly the graphical representations of the axioms in Table 7 (and their duals) that do not already hold up to graphical isomorphism.

4 Traced product, coproduct, and biproduct categories

It potentially makes sense to revisit each of the notions of Sections 3–5 and consider the case where the monoidal structure is given by a product, coproduct, or biproduct. Since products, coproducts, and biproducts are automatically symmetric, we do not need to consider the weaker notions (such as balanced, braided, etc).

Moreover, we do not need to consider any autonomous cases, because an autonomous category where the tensor is given by a product (or coproduct) is trivial. Indeed, for any objects $A,B$ , the morphisms $f:A\rightarrow B$ are in one-to-one correspondence with morphism $A\otimes B^{*}\rightarrow I$ . Since $I$ is terminal, there is exactly one such morphism, and therefore there is a unique morphism between any two objects. Such a category is equivalent to the one-object one-morphism category.

Therefore, the only new notion from Sections 3–5 that admits non-trivial examples in the context of products, coproducts, or biproducts is that of a symmetric traced category.

A traced product [coproduct, biproduct] category is a symmetric traced category where the tensor is given by a categorical product [coproduct, biproduct].

The symmetric traced category $(\textrm{\bf Rel},+)$ from Example 5.21 is a traced biproduct category.

Consider the category $\textrm{\bf Set}_{\bot}$ whose objects are sets, and whose morphisms are partial functions, regarded as a subcategory of Rel from Example 6.4. In this category, the empty set is a zero object, and the disjoint union operation $A+B$ defines a coproduct (but not a product). Trace is given as in Example 6.4. With these definitions, $\textrm{\bf Set}_{\bot}$ is a traced coproduct category.

As expected, the graphical language of traced product [coproduct, biproduct] categories is given by adding a trace (as in Section 5) to the graphical language of finite product [finite coproduct, biproduct] categories.

A well-formed equation between morphism terms in the language of traced product [coproduct, biproduct] categories follows from the respective axioms if and only if it holds in the graphical language, up to isomorphism of diagrams, and the diagrammatic manipulations shown in Table 8 and/or their duals (as appropriate).

In computer science, traces arise naturally in the context of data flow (as fixed points), and in the context of control flow (as iteration). The two situations correspond to traced product categories and traced coproduct categories, respectively. The duality between data flow and control flow was first described by Bainbridge . The following are typical examples of a data flow diagram (on the left) and a control flow diagram (on the right). The data flow diagram represents the fixed point expression $y=(3+x)(x+y)$ , parametric on an input $x$ . The control flow diagram represents a generic “while loop”. Note that data flow diagrams have a notion of “copying” data, whereas control flow diagrams have a dual notion of “merging” control paths.

In a category with finite coproducts, giving a trace is equivalent to giving an iteration operator. Here, an iteration operator is a family of operations

natural in $A$ and dinatural in $X$ , satisfying

Iteration: $\mathop{\textrm{\rm iter}}\nolimits(f)=[\textrm{\rm id}_{A},\mathop{\textrm{\rm iter}}\nolimits(f)]\circ f$ , for all $f:X\rightarrow A+X$ ;

Diagonal property: $\mathop{\textrm{\rm iter}}\nolimits(\mathop{\textrm{\rm iter}}\nolimits(f))=\mathop{\textrm{\rm iter}}\nolimits((\textrm{\rm id}_{A}+[\textrm{\rm id}_{X},\textrm{\rm id}_{X}])\circ f)$ , for all $f:X\rightarrow A+X+X$ .

Dually, on a finite product category, giving a trace is equivalent to a fixed point operator $\mathop{\textrm{\rm fix}}\nolimits^{X}:\textrm{\rm hom}(A\times X,X)\rightarrow\textrm{\rm hom}(A,X)$ .

This makes precise the intuitive idea that in the presence of coproducts, the while loop in Remark 6.7 is sufficient for constructing arbitrary traces.

In the presence of the other axioms, the diagonal property is equivalent to the so-called Bekič Lemma:

for all $f:X\rightarrow A+X+Y$ and $g:Y\rightarrow A+X+Y$ [36, Prop. B.1].

Iteration operators in the sense of Proposition 6.8 were first defined, using different but equivalent axioms, by Căzănescu and Ungureanu , under the name “algebraic theory with iterate”.

In a category with finite biproducts, giving a trace is equivalent to giving a repetition operation, i.e., a family of operators

Here, $f+g$ denotes the morphism $\nabla_{A}\circ(f\oplus g)\circ\Delta_{A}:A\rightarrow A$ , for $f,g:A\rightarrow A$ .

5 Uniformity and regular trees

Suppose we are given a traced category with a distinguished subclass of morphisms called the strict morphisms. Then the trace is called uniform if for all $f:A\otimes X\rightarrow B\otimes X$ , $g:A\otimes Y\rightarrow B\otimes Y$ , and strict $h:X\rightarrow Y$ , the following implication holds:

whenever $h$ is strict. Note that uniformity is not an equational property.

A traced coproduct category is uniformly traced if and only if for all $f:X\rightarrow A+X$ , $g:Y\rightarrow A+Y$ , and strict $h:X\rightarrow Y$ ,

Moreover, a traced biproduct category is uniformly traced if and only if for all $f:X\rightarrow X$ , $g:Y\rightarrow Y$ , and strict $h:X\rightarrow Y$ ,

In the particular case where the class of strict morphisms is taken to be the smallest co-cartesian subcategory containing all objects, Ştefănescu proved that the free uniformly traced coproduct category over a monoidal signature is given by the graphical language of traced coproduct categories, modulo a suitable notion of simulation equivalence on diagrams. This simulation equivalence is easiest to describe in the case where all morphism variables are of input arity 1. In this case, two diagrams are simulation equivalent if and only if they have the same infinite tree unwinding. There is also an analogous result for biproducts. We refer the reader to for full details.

The following is an example of an equation that holds up to infinite tree unwinding, but fails in general traced coproduct categories:

Ésik’s “iteration theories” are a direct equational axiomatization of such infinite tree unwindings. They include an iteration operator as in Proposition 6.8, but with an infinite family of additional properties, such as (6.1).

6 Cartesian center

Sometimes it is useful to consider notions that are weaker than product categories, yet still have copy and erase maps $\Delta_{A}:A\rightarrow A\otimes A$ and $\Diamond_{A}:A\rightarrow I$ . For example, it is common to drop the naturality axioms, while retaining the commutative comonoid and coherence axioms (see Tables 7 and 8). An equivalent way to describe such a category is as a symmetric monoidal category with (faithful) cartesian center , i.e., a symmetric monoidal category with a symmetric monoidal subcategory that contains all the objects and is cartesian. Similar ideas have occurred, with varying degrees of explicitness, in the literature on flowcharts, see e.g. .

Similarly, if one omits naturality from the axioms for coproducts, one obtains categories with a co-cartesian center. A weakened version of biproducts is obtained by combining the axioms of cartesian center and co-cartesian center. In this case, one requires the operations $\Delta$ , $\Diamond$ , $\nabla$ , $\Box$ to be natural with respect to one another, yielding the properties from Table 9. More generally, one may require any subset of the operations $\Delta$ , $\Diamond$ , $\nabla$ , $\Box$ to exist, and a further subset to be natural transformations. As the reader may imagine, this leads to a nearly endless number of categorical notions and corresponding graphical languages; see e.g. .

Dagger categories

The concept of a dagger category (also called involutive category or *-category in the literature) is motivated by the category of Hilbert spaces, where each morphism $f:A\rightarrow B$ has an adjoint $f^{\dagger}:B\rightarrow A$ .

A dagger category is a category ${\bf C}$ together with an involutive, identity-on-objects, contravariant functor $\dagger:{\bf C}\rightarrow{\bf C}$ .

Concretely, this means that to every morphism $f:A\rightarrow B$ , one associates a morphism $f^{\dagger}:B\rightarrow A$ , called the adjoint of $f$ , such that for all $f:A\rightarrow B$ and $g:B\rightarrow C$ :

The category Hilb of Hilbert spaces and bounded linear maps is a dagger category, where $f^{\dagger}:B\rightarrow A$ is given by the usual adjointness property of linear algebra, i.e., $\langle f^{\dagger}x\mathrel{|}y\rangle=\langle x\mathrel{|}fy\rangle$ for all $x\in B$ and $y\in A$ .

(Unitary map, self-adjoint map) In a dagger category, a morphism $f:A\rightarrow B$ is called unitary if it is an isomorphism and $f^{-1}=f^{\dagger}$ . A morphism $f:A\rightarrow A$ is called self-adjoint or hermitian if $f=f^{\dagger}$ .

A dagger functor between dagger categories is a functor that satisfies $F(f^{\dagger})=(Ff)^{\dagger}$ for all $f$ .

The graphical language of dagger categories extends that of categories. The adjoint of a morphism variable $f:A\rightarrow B$ is represented diagrammatically as follows:

More generally, the adjoint of any diagram is its mirror image. Note that the mirror image of a box is visually distinguishable because we have marked the upper left corner of each box representing a morphism variable. Also note that, while we have taken the mirror image of each box, we have reversed the location, but not the direction, of the wires. Contrast this with (4.5).

A well-formed equation between two morphism terms in the language of dagger categories follows from the axioms of dagger categories if and only if it holds in the graphical language up to isomorphism of diagrams.

This is a consequence of coherence for categories, from Theorem 2.1. As usual, soundness is easy to check. For completeness, notice that any morphism term $t$ of dagger categories can be transformed, via the axioms $(g\circ f)^{\dagger}=f^{\dagger}\circ g^{\dagger}$ , $\textrm{\rm id}^{\dagger}=\textrm{\rm id}$ , and $f^{\dagger\dagger}=f$ , into an equivalent term $t^{\prime}$ with the property that $\dagger$ is only applied to morphism variables in $t^{\prime}$ . Such a term can be regarded as a term in the language of categories, over the extended set of morphism variables $\{f,f^{\dagger},\ldots\}$ . Now if $t$ and $s$ are two terms that have isomorphic diagrams, then by soundness, $t^{\prime}$ and $s^{\prime}$ have isomorphic diagrams. By Theorem 2.1, $t^{\prime}$ and $s^{\prime}$ are provably equal from the axioms of categories. Therefore $t$ and $s$ are provably equal from the axioms of dagger categories. $\Box$

We now consider “dagger notions” for the various monoidal categories from Sections 3–5.

1 Dagger monoidal categories

A dagger monoidal category is a monoidal category that is a dagger category, such that the dagger structure is compatible with the monoidal structure in the following sense:

$(f\otimes g)^{\dagger}=f^{\dagger}\otimes g^{\dagger}$ , for all $f,g$ ;

the canonical isomorphisms of the monoidal structure, $\alpha_{A,B,C}:(A\otimes B)\otimes C\rightarrow A\otimes(B\otimes C)$ , $\lambda_{A}:I\otimes A\rightarrow A$ , and $\rho_{A}:A\otimes I\rightarrow A$ , are unitary.

The graphical language of dagger monoidal categories is like the graphical language of monoidal categories, with the adjoint of a diagram given by its mirror image. For example,

A well-formed equation between morphism terms in the language of dagger monoidal categories follows from the axioms of dagger monoidal categories if and only if it holds, up to planar isotopy, in the graphical language.

This is a consequence of coherence for planar monoidal categories, from Theorem 3.1. The proof is analogous to that of Theorem 7.2. Note that the axioms of dagger monoidal categories are precisely what is needed to ensure that all occurrences of $\dagger$ can be removed from a morphism term, except where applied directly to a morphism variable. $\Box$

2 Other progressive dagger monoidal notions

We can now “daggerize” the other progressive monoidal notions from Section 3:

A dagger monoidal category is spacial if it is spacial as a monoidal category.

A dagger braided monoidal category is a dagger monoidal category with a unitary braiding $c_{A,B}:A\otimes B\rightarrow B\otimes A$ .

A dagger balanced monoidal category is a dagger braided monoidal category with a unitary twist $\theta_{A}:A\rightarrow A$ .

A dagger symmetric monoidal category is a dagger braided monoidal category such that the unitary braiding is a symmetry.

In each case, the graphical language extends the corresponding language from Section 3, with the dagger of a diagram taken to be its mirror image. Each notion has a coherence theorem, proved by the same method as Theorems 7.2 and 7.3. The requirements that the braiding and twist are unitary ensures that the dagger can be removed from the corresponding terms. The respective caveats from Section 3 also apply to the dagger cases.

The category Hilb of Hilbert spaces is dagger symmetric monoidal, with the usual tensor product and symmetry.

3 Dagger pivotal categories

In defining dagger variants of the notions of Section 4, we find that the notion of a dagger autonomous category and a dagger pivotal category coincide. This is because the presence of a dagger structure on an autonomous category already induces a canonical isomorphism $A\cong A^{**}$ , which automatically satisfies the pivotal axioms under mild assumptions.

To be more precise, consider a dagger monoidal category that is also right autonomous (as a monoidal category). Because $\eta_{A}:I\rightarrow A^{*}\otimes A$ has an adjoint $\eta^{\dagger}_{A}:A^{*}\otimes A\rightarrow I$ , we can define a family of isomorphisms

We can represent this schematically as follows (but bearing in mind that we do not yet have a formal graphical language to work with):

The following are equivalent in a right autonomous, dagger monoidal category:

the family of isomorphisms $i_{A}:A\rightarrow A^{**}$ , as defined above, determines a pivotal structure;

for all $A,B$ , the canonical isomorphisms $(A\otimes B)^{*}\cong B^{*}\otimes A^{*}$ and $I^{*}\cong I$ (determined by the right autonomous structure) are unitary, and for all $f:A\rightarrow B$ , the equation $f^{*\dagger}=f^{\dagger*}$ holds.

By a direct calculation from the definitions, one can check three separate and independent facts:

For any given $f:A\rightarrow B$ , the diagram

commutes if and only if $f^{*\dagger}=f^{\dagger*}$ . In particular, the family $i_{A}$ is a natural transformation if and only if this condition holds for all $f$ .

commutes if and only if the canonical isomorphism $(A\otimes B)^{*}\cong B^{*}\otimes A^{*}$ is unitary.

The morphism $i_{I}:I\rightarrow I^{**}$ is equal to the canonical isomorphism (from the right autonomous structure) if and only if the canonical isomorphism $I\rightarrow I^{*}$ is unitary.

Since the three conditions are the defining conditions for a pivotal structure, the lemma follows. $\Box$

Under the equivalent conditions of Lemma 7.5, the following hold:

$i_{A}=A\xrightarrow{\cong}A\otimes I\xrightarrow{\textrm{\rm id}_{A}\otimes\epsilon^{\dagger}_{A^{*}}}A\otimes A^{*}\otimes A^{**}\xrightarrow{\epsilon_{A}\otimes\textrm{\rm id}_{A^{**}}}I\otimes A^{**}\xrightarrow{\cong}A^{**}$ :

$\eta^{\dagger}_{A}=\epsilon_{A^{*}}\circ(\textrm{\rm id}_{A^{*}}\otimes i_{A})$ :

$\epsilon^{\dagger}_{A}=(i^{-1}_{A}\otimes\textrm{\rm id}_{A^{*}})\circ\eta_{A^{*}}$ :

But this is just the definition of $i_{A^{*}}$ , therefore $(i_{A})^{\dagger*}=i_{A^{*}}$ . By definition, $i_{A}$ is unitary iff $(i_{A})^{\dagger}=i_{A}^{-1}$ , iff $(i_{A})^{\dagger*}=(i_{A}^{-1})^{*}$ , iff $i_{A^{*}}=(i_{A}^{-1})^{*}=(i_{A}^{*})^{-1}$ . Since $i$ is a monoidal natural transformation, this holds by Saavedra Rivano’s Lemma (Lemma 4.9).

To prove (b), note that the right-hand side is the inverse of $(i_{A})^{\dagger}$ . Therefore, (b) is equivalent to (a).

Finally, equations (c) and (d) are restatements of the definition of $i_{A}$ from (7.1). $\Box$

The equivalence between (a) and (b) in Lemma 7.6 holds only if $i_{A}$ is defined as in (7.1). It does not hold for an arbitrary pivotal structure on a right autonomous dagger monoidal category.

Armed with these results, we finally state the two equivalent definitions of a dagger pivotal category:

A dagger pivotal category is defined in one of the following equivalent ways:

as a dagger monoidal, right autonomous category such that the natural isomorphisms $(A\otimes B)^{*}\cong B^{*}\otimes A^{*}$ and $I^{*}\cong I$ (from the right autonomous structure) are unitary, and such that $f^{*\dagger}=f^{\dagger*}$ holds for all morphisms $f$ ; or

as a pivotal, dagger monoidal category satisfying the condition in Lemma 7.6(c) (or equivalently, (d)).

The first form of this definition is much easier to check in practice. The second form is more suitable for the proof of the coherence theorem below.

In a dagger pivotal category, the operation $(-)^{*}$ arises from an adjunction (in the categorical sense) of objects, with associated unit, counit, and adjoint mates. On the other hand, the operation $(-)^{\dagger}$ arises from an adjunction (in the linear algebra sense) of morphisms. The two concepts should not be confused with each other.

The graphical language of dagger pivotal categories is like that of pivotal categories, where the adjoint of a diagram is given, as usual, by its mirror image. For example:

Note that in the graphical language, adjoint mates $f^{*}:B^{*}\rightarrow A^{*}$ are represented by rotation and adjoints $f^{\dagger}:B\rightarrow A$ by mirror image. Therefore, each morphism variable $f:A\rightarrow B$ induces four kinds of boxes:

Also note that, unlike the informal notation used above, the graphical language does not explicitly display the isomorphism $i_{A}:A\rightarrow A^{**}$ , and it does not explicitly distinguish $\eta_{A}:I\rightarrow A^{*}\otimes A$ from $\epsilon^{\dagger}_{A^{*}}:I\rightarrow A^{*}\otimes A^{**}$ . This is justified by the following coherence theorem.

A well-formed equation between morphisms in the language of dagger pivotal categories follows from the axioms of dagger pivotal categories if and only if it holds in the graphical language up to planar isotopy, including rotation of boxes (by multiples of 180 degrees).

This follows from coherence of pivotal categories (Theorem 4.14), by the same argument used in the proof of Theorem 7.3. The equations from Lemma 7.6(c) and (d), and the fact that $i_{A}$ is unitary, can be used to replace $\eta^{\dagger}_{A}$ , $\epsilon^{\dagger}_{A}$ , and $i^{\dagger}_{A}$ by equivalent terms not containing $\dagger$ . $\Box$

4 Other dagger pivotal notions

It is possible to define dagger variants of the remaining pivotal notions from Section 4:

A dagger pivotal category is spherical (respectively spacial) if it is spherical (respectively spacial) as a pivotal category.

A dagger braided pivotal category is a dagger pivotal category with a unitary braiding $c_{A,B}:A\otimes B\rightarrow B\otimes A$ .

Like any braided pivotal category, a dagger braided pivotal category is balanced by Lemma 4.20. However, in general the resulting twist $\theta_{A}:A\rightarrow A$ is not unitary. In fact, $\theta_{A}$ is unitary in this situation if and only if $\theta_{A^{*}}=(\theta_{A})^{*}$ , i.e., if and only if the category is tortile.

A dagger tortile category is defined in one of the following equivalent ways:

as a dagger braided pivotal category in which the canonical twist $\theta_{A}$ , defined as in Lemma 4.20, is unitary;

as a tortile, dagger monoidal category such that the braiding is unitary, and such that $\epsilon_{A}$ and $\eta_{A}$ satisfy the (equivalent) conditions of Lemma 7.6(c) and (d); or

as a dagger balanced monoidal category that is right autonomous and satisfies

A dagger compact closed category is a dagger tortile category such that $\theta_{A}=\textrm{\rm id}_{A}$ for all $A$ . Equivalently, it is a dagger symmetric monoidal category that is right autonomous and satisfies

The equivalence of the two definition is immediate from the third form of the definition of dagger tortile categories. Note that (7.2) is equivalent to (7.3) in the symmetric case. Further, these conditions are equivalent to the condition in Lemma 7.6(d).

The category FdHilb of finite dimensional Hilbert spaces is dagger compact closed, with $A^{*}$ the usual dual space of linear functions from $A$ to $I$ , and with $f^{\dagger}$ the usual linear algebra adjoint.

Each of the notions defined in this section (except the spherical notion) has a graphical language, extending the corresponding graphical language from Section 4, with the dagger of a diagram taken to be its mirror image. Each notion has a coherence theorem, proved by the same method as Theorems 7.2 and 7.3. As expected, equivalence of diagrams is up to isomorphism (for spacial dagger pivotal categories); up to regular isotopy (for dagger braided pivotal categories); up to framed 3-dimensional isotopy (for dagger tortile categories); and up to isomorphism (for dagger compact closed categories).

5 Dagger traced categories

There is no difficulty in defining dagger variants of each of the traced notions of Section 5. A (left or right) trace on a dagger monoidal category is called a dagger trace if it satisfies

For example: a dagger right traced category is a right traced dagger monoidal category satisfying (7.4). A balanced traced category is dagger balanced traced if it is dagger balanced and satisfies (7.4). And similarly for the other notions. The representation theorems of Section 5 extend to these dagger variants:

Every dagger braided [balanced, symmetric] traced category can be fully and faithfully embedded in a dagger braided pivotal [dagger tortile, dagger compact closed] category, via a dagger braided [balanced, symmetric] traced functor. $\Box$

The proof, in each case, is by Joyal, Street, and Verity’s Int-construction , which respects the dagger structure.

The graphical language of each class of traced categories extends to the corresponding dagger traced categories, in a way suggested by equation (7.4). As usual, the dagger of a diagram is its mirror image, thus for example

The coherence theorems of Section 5 extend to this setting.

6 Dagger biproducts

In a dagger category, if $A\oplus B$ is a categorical product (with projections $\pi_{1}:A\oplus B\rightarrow A$ and $\pi_{2}:A\oplus B\rightarrow B$ ), then it is automatically a coproduct (with injections $\pi^{\dagger}_{1}:A\rightarrow A\oplus B$ and $\pi^{\dagger}_{2}:B\rightarrow A\oplus B$ ). It therefore makes sense to define a notion of dagger biproduct.

A dagger biproduct category is a biproduct category carrying a dagger structure, such that $\pi^{\dagger}_{i}=\iota_{i}:A_{i}\rightarrow A_{1}\oplus A_{2}$ for $i=1,2$ .

As in Section 6.3, we can equivalently define a dagger biproduct category as a dagger symmetric monoidal category, together with natural families of morphisms

such that $\Delta^{\dagger}_{A}=\nabla_{A}$ and $\Diamond^{\dagger}_{A}=\Box_{A}$ , satisfying the axioms in Table 7.

The graphical language of dagger biproduct categories is like that of biproduct categories, where the dagger of a diagram is taken to be its mirror image. For example,

A well-formed equation between morphism terms in the language of dagger biproduct categories follows from the axioms of dagger biproduct categories if and only if it holds in the graphical language, up to isomorphism of diagrams, the diagrammatic manipulations shown in Table 8, and their duals.

By reduction to biproduct categories, as in the proofs of Theorems 7.2 and 7.3. The axioms $\Delta^{\dagger}_{A}=\nabla_{A}$ and $\Diamond^{\dagger}_{A}=\Box_{A}$ allow $\dagger$ to be removed from anywhere but a morphism variable. $\Box$

Finally, there is an obvious notion of dagger traced biproduct category (which is really a dagger traced dagger biproduct category), with graphical language derived from traced biproduct categories.

Bicategories

A bicategory is a generalization of a monoidal category. In addition to objects $A,B,\ldots$ and morphisms $f,g,\ldots$ , one now also considers 0-cells $\alpha,\beta,\ldots$ , which we can visualize as colors. For example, consider the following diagram. It is a standard diagram for monoidal categories, except that the areas between the wires have been colored.

As usual, we have objects $A,B,C,D,E,F$ and morphisms $f:A\rightarrow C\otimes D$ and $g:B\otimes C\rightarrow F\otimes E$ . But now there are also 0-cells called green, red, yellow, and blue. In such diagrams, each object has a source, which is the 0-cell just above it, and a target, which is the 0-cell just below it. For example, we have $A:\mbox{green}\rightarrow\mbox{yellow}$ , $B:\mbox{yellow}\rightarrow\mbox{blue}$ , and so on. It is now clear that, to be consistently colored, such diagrams have to satisfy some coloring constraints. The constraints are:

The tensor $B\otimes A$ of two objects may only be formed if the target of $A$ is equal to the source of $B$ . In symbols, for any 0-cells $\alpha,\beta,\gamma$ , if $A:\alpha\rightarrow\beta$ and $B:\beta\rightarrow\gamma$ , then $B\otimes A:\alpha\rightarrow\gamma$ .

If $f:A\rightarrow B$ is a morphism, then $A$ and $B$ must have a common source and a common target. In symbols, if $f:A\rightarrow B$ and $A:\alpha\rightarrow\beta$ , then $B:\alpha\rightarrow\beta$ .

One also requires a unit object $I_{\alpha}:\alpha\rightarrow\alpha$ for every color $\alpha$ .

As an illustration of the second property, consider $f:A\rightarrow C\otimes D$ in the above example, where $A:\mbox{green}\rightarrow\mbox{yellow}$ and $C\otimes D:\mbox{green}\rightarrow\mbox{yellow}$ . Subject to the above coloring constraints, a bicategory is then required to satisfy exactly the same axioms as a monoidal category. Notice, for example, that if $f:A\rightarrow B$ and $g:B\rightarrow C$ and $f,g$ are well-colored, then so is $g\circ f:A\rightarrow C$ . Also, the identity maps $\textrm{\rm id}_{A}:A\rightarrow A$ , the associativity map $\alpha_{A,B,C}:(A\otimes B)\otimes C\xrightarrow{\cong}A\otimes(B\otimes C)$ , and the other structural maps are well-colored. In particular, a monoidal category is the same thing as a one-object bicategory.

To give a detailed account of bicategories and their graphical languages is beyond the scope of this paper. We have already discussed over 30 different flavors of monoidal categories, and the reader can well imagine how many possible variations of bicategories there are, with 2-, 3-, and 4-dimensional graphical languages, once one considers bicategorical versions of braids, twists, adjoints, and traces. There are even more variations if one considers tricategories and beyond. We refer the reader to for the definition and basic properties of bicategories, and to , [2, Sec. 7] for a taste of their graphical languages.

Beyond a single tensor product

All the categorical notions that we have considered in this paper have just a single tensor product, which we represented as juxtaposition in the graphical languages. For notions of categories with more than one tensor product, the graphical languages get much more complicated. The details are beyond the scope of this paper, so we just outline the basics and give some references.

Examples of categories with more than one tensor are linearly distributive categories and *-autonomous categories . Both of these notions are models of multiplicative linear logic . These categories have two tensors, often called “tensor” and “par”, and written

The two tensors are related by some morphisms, such as $A\otimes(B\llamp C)\rightarrow(A\otimes B)\llamp C$ , while other similar morphisms, such as $(A\otimes B)\llamp C\rightarrow A\otimes(B\llamp C)$ , are not present.

To make a graphical language for more than one tensor product, one must label the wires by morphism terms, rather than morphism variables. One must also introduce special tensor and par nodes as shown here:

$\scriptstyle{A\otimes B}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mo lspace="0em" rspace="0em">⊗</mo></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{\otimes}</annotation></semantics></math>⊗\scriptstyle{B}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>A</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{A}</annotation></semantics></math>A\textstyle{\otimes}$ $\scriptstyle{A\otimes B}$ $\scriptstyle{A\llamp B}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="1" displaystyle="false"><mi>B</mi></mstyle></mrow><annotation encoding="application/x-tex">\scriptstyle{B}</annotation></semantics></math>B\scriptstyle{A}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mstyle scriptlevel="0" displaystyle="false"><mo lspace="0em" rspace="0em">⊗</mo></mstyle></mrow><annotation encoding="application/x-tex">\textstyle{\otimes}</annotation></semantics></math>⊗\scriptstyle{A\otimes B}$ The resulting theory is called the theory of proof nets, and was first given by Girard for unit-free multiplicative linear logic . It was later extended to include the tensor units by Blute et al. .

Summary

Table 10 summarizes the graphical languages from Sections 2–6. The name of each class of categories is shown along with a typical diagram or equation. The arrows indicate forgetful functors. We have omitted spherical categories, because they do not possess a graphical language modulo a natural notion of isotopy.

The letter $d$ indicates the dimension of the diagrams, and the letter $i$ indicates the dimension of the ambient space for isotopy. If $i>d$ , then isotopy coincides with isomorphism of diagrams. Special cases are “3f” for framed diagrams and framed isotopy in 3 dimensions; “2+” for two-dimensional diagram with crossings (i.e., isotopy is taken on 2-dimensional projections, rather than on 3-dimensional diagrams); “reg” for regular isotopy; and “rot” to indicate that isotopy includes rotation of boxes. Finally, “eqn” indicates that equivalence of diagrams is taken modulo equational axioms.

The letter $c$ indicates the status of a coherence theorem. This is usually a reference to a proof of the theorem, or “conj” if the result is conjectured. A checkmark “ $\surd$ ” indicates a result that is folklore or whose proof is trivial. “int” indicates that the coherence theorem follows from a version of Joyal, Street, and Verity’s Int-construction, and the corresponding coherence theorem for pivotal categories. An asterisk “ $*$ ” indicates that the result has only been proved for simple signatures.

Dagger variants can be defined of all of the notions shown in Table 10, except the planar autonomous and braided autonomous notions. Finally, bicategories require their own (presumably much larger) table and are not included here.

Introduction

Organization of the paper.

Acknowledgments.

Categories

Coherence.

Technicalities

Functors and natural transformations.

Coherence and free categories.

Monoidal categories

Coherence.

Relationship to traditional coherence theorems.

Technicalities

Monoidal functors and natural transformations.

Coherence and free monoidal categories.

2 Spacial monoidal categories

3 Braided monoidal categories

4 Balanced monoidal categories

5 Symmetric monoidal categories

Autonomous categories

Technicalities

Functors and natural transformations of autonomous categories.

Coherence and free autonomous categories.

2 (Planar) pivotal categories

3 Spherical pivotal categories

4 Spacial pivotal categories

5 Braided autonomous categories

6 Braided pivotal categories

7 Tortile categories

8 Compact closed categories

Traced categories

2 Planar traced categories

3 Spherical traced categories

4 Spacial traced categories

5 Braided traced categories

6 Balanced traced categories

7 Symmetric traced categories

Products, coproducts, and biproducts

Coherence.

2 Coproducts

3 Biproducts

4 Traced product, coproduct, and biproduct categories

5 Uniformity and regular trees

6 Cartesian center

Dagger categories

1 Dagger monoidal categories

2 Other progressive dagger monoidal notions

3 Dagger pivotal categories

4 Other dagger pivotal notions

5 Dagger traced categories

6 Dagger biproducts

Bicategories

Beyond a single tensor product

Summary

References