traced monoidal category


Monoidal categories



The concept of traced monoidal category axiomatizes the structure on a monoidal category for it to have a sensible notion of trace the way it exists canonically in compact closed categories.


The original definition due to (Joyal-Street-Verity 96) is stated in the general setting of balanced monoidal categories. Here we give just the slightly simpler formulation for the case of symmetric monoidal categories (Hasegawa 1997).

A symmetric monoidal category (C,,1,b)(C,\otimes,1,b) (where bb is the symmetry) is said to be traced if it is equipped with a natural family of functions

Tr A,B X:C(AX,BX)C(A,B)Tr_{A,B}^X : C(A \otimes X, B\otimes X) \to C(A,B)

satisfying three axioms:

  • Vanishing: Tr A,B 1(f)=fTr_{A,B}^1(f) = f (for all f:ABf : A \to B) and Tr A,B XY(f)=Tr A,B X(Tr AX,BX Y(f))Tr_{A,B}^{X\otimes Y}(f) = Tr_{A,B}^X(Tr_{A\otimes X,B\otimes X}^Y(f)) (for all f:AXYBXYf : A \otimes X \otimes Y \to B \otimes X \otimes Y)

  • Superposing: Tr CA,CB X(id Cf)=id CTr A,B X(f)Tr_{C\otimes A,C\otimes B}^X(id_C \otimes f) = id_C \otimes Tr_{A,B}^X(f) (for all f:AXBXf : A \otimes X \to B \otimes X)

  • Yanking: Tr X,X X(b X,X)=id XTr_{X,X}^X(b_{X,X}) = id_X

In string diagrams, the trace Tr(f):ABTr(f) : A \to B of a morphism f:AXBXf : A \otimes X \to B \otimes X is visualized by wrapping the outgoing wire representing XX to the incoming wire representing XX, thus “tying a loop” in the diagram of ff. The three axioms above (as well as the naturality conditions) then all have natural graphical interpretations (see Joyal-Street-Verity 96 or Hasegawa 1997).


Relation to compact closed categories

Given a traced monoidal category 𝒞\mathcal{C}, there is a free construction completion of it to a compact closed category Int(𝒞)Int(\mathcal{C}) (Joyal-Street-Verity 96):

the objects of Int(𝒞)Int(\mathcal{C}) are pairs (A +,A )(A^+, A^-) of objects of 𝒞\mathcal{C}, a morphism (A +,A )(B +,B )(A^+ , A^-) \to (B^+ , B^-) in Int(𝒞)Int(\mathcal{C}) is given by a morphism of the form A +B A B +A^+\otimes B^- \longrightarrow A^- \otimes B^+ in 𝒞\mathcal{C}, and composition of two such morphisms (A +,A )(B +,B )(A^+ , A^-) \to (B^+ , B^-) and (B +,B )(C +,C )(B^+ , B^-) \to (C^+ , C^-) is given by tracing out B +B^+ and B B^- in the evident way.

In cartesian monoidal categories

For a cartesian monoidal category, the existence of a trace operator is equivalent to the existence of a “parameterized” fixed point operator satisfying certain properties (Hasegawa 1997).

Categorical semantics

Traced monoidal categories serve as an “operational” categorical semantics for linear logic, known as Geometry of Interactions. See there for more.

In this context the free compact closure Int(𝒞)Int(\mathcal{C}) from above is sometimes called the Geometry of Interaction construction and denoted 𝒢(𝒞)\mathcal{G}(\mathcal{C}) (Abramsky-Haghverdi-Scott 02, def. 2.6).


The concept was introduced in

A characterization of trace structures on cartesian monoidal categories is given in

  • Masahito Hasegawa, Recursion from Cyclic Sharing: Traced Monoidal Categories and Models of Cyclic Lambda Calculi, Proc. 3rd International Conference on Typed Lambda Calculi and Applications (TLCA 1997). Springer LNCS1210, 1997 (citeseer)

The equivalence between traces and parameterized fixed point operators appears as Theorem 3.1 (the author notes that this theorem was also proved independently by Martin Hyland).

Comprehensive discussion as a source for categorical semantics of the Geometry of Interactions is in

Revised on July 10, 2015 04:50:09 by Robin Kaarsgaard? (