Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 14, 2021

Shulman’s Practical Type Theory for Symmetric Monoidal Categories

Posted by Emily Riehl

guest post by Nuiok Dicaire and Paul Lessard

Many well-known type theories, Martin-Löf dependent type theory or linear type theory for example, were developed as syntactic treatments of particular forms of reasoning. Constructive mathematical reasoning in the case of Martin-Löf type theory and resource dependent computation in the case of linear type theory. It is after the fact that these type theories provide convenient means to reason about locally Cartesian closed categories or \star-autonomous ones. In this post, a long overdue part of the Applied Category Theory Adjoint School (2020!?), we will discuss a then recent paper by Mike Shulman, A Practical Type Theory for Symmetric Monoidal Categories, where the author reverses this approach. Shulman starts with symmetric monoidal categories as the intended semantics and then (reverse)-engineers a syntax in which it is practical to reason about such categories.

Which properties of a type theory (for symmetric monoidal categories) make it practical? Shulman, synthesizing various observations, settles on a few basic tenets to guide the invention of the syntax and its interpretation into symmetric monoidal categories. We reduce these further to the conditions that the type theory be: (1) intuitive, (2) concise, and (3) complete.

Intuitive. First, a practical type theory should permit us to leverage our intuition for reasoning about “sets with elements”. What this means in practice is that we require a “natural deduction style” type theory, in which contexts look and feel like choosing elements, and typing judgements look and feel like functions of sets. Moreover, we also require an internal-language/term-model relationship with symmetric monoidal categories which provide correspondences:

(1)Category TypeTheory objects contexts morphisms typingjudgments commutingdiagrams equalityjudgments \array{ \arrayopts{ \frame{none} \rowalign{bottom} \rowlines{none} } \mathbf{Category} \quad & & \quad \mathbf{Type} \;\mathbf{Theory} \\ \mathrm{objects} \quad & \leftrightarrow & \quad \mathrm{contexts} \\ \mathrm{morphisms} \quad & \leftrightarrow & \quad \mathrm{typing} \; \mathrm{judgments} \\ \mathrm{commuting}\;\mathrm{diagrams} \quad & \leftrightarrow & \quad \mathrm{equality} \; \mathrm{judgments} }

Concise. When stripped of the philosophical premises of what terms, types, judgements etc. are >, the rules of a type theory can be seen to generate its derivable judgments. It is therefore desirable that the translation between symmetric monoidal categories and the rules of their associated type theories proceed by way of the most concise combinatorial description of symmetric monoidal categories possible.

Complete. Lastly we ask that, given a presentation for a symmetric monoidal category, the type theory we get therefrom should be complete. By this, we mean that a proposition should hold in a particular symmetric monoidal category if and only if it is derivable as a judgment in the associated type theory.

Symmetric Monoidal Categories and Presentations of PROP\mathsf{PROP}s

While it is well-known that every symmetric monoidal category is equivalent to a symmetric strict monoidal category, it is probably less well-known that every symmetric strict monoidal category is equivalent to a PROP\mathsf{PROP}.

Definition. A PROP\mathsf{PROP}, 𝔓=(𝔓,P)\mathfrak{P}=\left(\mathfrak{P},\mathbf{P}\right), consists of a set P\mathbf{P} of generating objects and a symmetric strict monoidal category 𝔓\mathfrak{P} whose underlying monoid of objects is the free monoid on the set P\mathbf{P}.

This is not however too hard to see: the equivalence between PROP\mathsf{PROP}s and symmetric monoidal categories simply replaces every equality of objects AB=CA\otimes B = C with an isomorphism ABCA \otimes B \overset{\sim}{\longrightarrow} C, thereby rendering the monoidal product to be free. We will develop what we mean by presentation over the course of a few examples. In doing so we hope to give the reader a better sense for PROP\mathsf{PROP}s.

Example. Given a set X\mathbf{X}, let Σ X\Sigma_{\mathbf{X}} be the free permutative category on X\mathbf{X}. This is a symmetric monoidal category whose monoid of objects is the monoid of lists drawn from the set X\mathbf{X} and whose morphisms are given by the expression

(2)Σ X(X,Y)={σS n|X σ=Y} \Sigma_{\mathbf{X}}\left(\overrightarrow{X},\overrightarrow{Y}\right) = \left\{ \sigma \in S_{n} \Big| \overrightarrow{X_\sigma}=\overrightarrow{Y} \right\}

(where by X σ\overrightarrow{X_\sigma} we mean the reorganization of the list X\overrightarrow{X} according to the permutation σ\sigma). For every set X\mathbf{X}, Σ X\Sigma_{\mathbf{X}} is a PROP\mathsf{PROP}.

Example. For a more complicated example, let X 0\mathbf{X}_0 be a set and let

(3)X 1={(f i,X i,Y i)} iI \mathbf{X}_1 = \left\{ (f_i,\overrightarrow{X}_i,\overrightarrow{Y}_i) \right\}_{i\in I}

be a set of triples comprised of names f if_i and pairs of lists (X i,Y i)\left(\overrightarrow{X}_i,\overrightarrow{Y}_i\right) valued in X 0\mathbf{X}_0. Let F(X 1,X 0)F\left(\mathbf{X}_1,\mathbf{X}_0\right) denote the free symmetric monoidal category generated by Σ X 0\Sigma_{\mathbf{X}_0} together with additional arrows f i:X iY if_{i}:\overrightarrow{X}_i \longrightarrow \overrightarrow{Y}_i for each iIi\in I. Then F(X 1,X 0)F\left(\mathbf{X}_1,\mathbf{X}_0\right) is also a PROP\mathsf{PROP}.

Importantly, this second example is very nearly general - every PROP\mathsf{PROP} admits a bijective-on-objects and full, but not in general faithful, functor from some PROP\mathsf{PROP} of the form F(X 1,X 0)F\left(\mathbf{X}_1,\mathbf{X}_0\right).

Example. Let X 0\mathbf{X}_0 and X 1\mathbf{X}_1 be as in the previous example and let

(4)R={(s j,t j)Mor(F(X 1,X 0)) 2|jJ} \mathbf{R}=\Big\{ (s_j,t_j) \in \mathsf{Mor}\big(F\left(\mathbf{X}_1,\mathbf{X}_0\right)\big)^2 \Big| j \in J \Big\}

be a set of pairs of morphisms in the PROP\mathsf{PROP} F(X 1,X 0)F\left(\mathbf{X}_1,\mathbf{X}_0\right). Let F(R,X 1,X 0)F\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right) be the quotient of the symmetric monoidal category F(X 1,X 0)F\left(\mathbf{X}_1,\mathbf{X}_0\right) by the congruence generated by RMor(F(X 1,X 0))×Mor(F(X 1,X 0))R \subset \mathsf{Mor}\big(F(\mathbf{X}_1,\mathbf{X}_0)\big) \times \mathsf{Mor}\big(F\left(\mathbf{X}_1,\mathbf{X}_0\right)\big).

This last example is fully general. Every PROP\mathsf{PROP}, hence every symmetric monoidal category, is equivalent to a PROP\mathsf{PROP} of the form F(R,X 1,X 0)F\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right).

Remark. If (generalized) computads are familiar, you may notice that our three examples here are free PROP\mathsf{PROP}s on 00, 11, and 22-computads.

From Presentations to Type Theories

It is from these presentations (R,X 1,X 0)\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right) of PROP\mathsf{PROP}s that we will build type theories PTT (R,X 1,X 0)\mathsf{PTT}_{\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right)} for the symmetric monoidal categories F(R,X 1,X 0)F\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right). Indeed, reading \rightsquigarrow as “gives rise to”, we will see:

(5)Generators Judgements X 0 contexts X 1 typingjudgments R equalityjudgment \array{ \arrayopts{ \frame{none} \rowalign{bottom} \rowlines{none} } \mathbf{Generators} \quad & & \quad \mathbf{Judgements} \\ \mathbf{X}_0 \quad & \rightsquigarrow & \quad \mathrm{contexts} \\ \mathbf{X}_1 \quad & \rightsquigarrow & \quad \mathrm{typing} \; \mathrm{judgments} \\ \mathbf{R} \quad & \rightsquigarrow & \quad \mathrm{equality} \; \mathrm{judgment} }


The contexts (usually denoted Γ,Δ\Gamma,\;\Delta, etc.) of the type theory PTT (R,X 1,X 0)\mathsf{PTT}_{(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0)} are lists

(6)x 1:A 1,,x n:A n x_{1}:A_{1},\dots,x_{n}:A_{n}

of typed variables, where the A iA_i are elements of the set X 0\mathbf{X}_{0}. It’s not hard to see that, up to the names of variables, contexts are in bijection with List(X 0)\mathsf{List}\left(\mathbf{X}_0\right).

Typing Judgments

As promised, typing judgments correspond to morphisms in F(R,X 1,X 0)F\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right). Here are some examples of morphisms and their corresponding judgements:

(7)Morphisms TypingJudgements f:(A)(B) x:Af(x):B h:(A)(B 1,B 2) x:A(h (1)(x),h (2)(x)):B z:()() (|z a):() \array{ \arrayopts{ \frame{none} \rowalign{bottom} \rowlines{none} \colalign{right left} } \mathbf{Morphisms} \quad & & \quad \mathbf{Typing} \;\mathbf{Judgements} \\ f:(A) \rightarrow (B) \quad & \leftrightarrow & \quad x:A\vdash f(x):B \\ h:(A)\rightarrow (B_{1},B_{2}) \quad & \leftrightarrow & \quad x:A\vdash\left(h_{(1)}(x),h_{(2)}(x)\right):B \\ z:() \rightarrow () \quad & \leftrightarrow & \quad \vdash \left(|z^{a}\right):() }

The rules from which these judgments may be derived correspond, roughly speaking, to applying a tensor product of generating morphisms in X 1\mathbf{X}_1 composed with a braiding - something along the lines of:

(8)Γ(m,,n|z):(A,,B) (f:AF)X 1(g:BG)X 1(σ:(F,,G))Σ X 0 Γ(σ(f(m),,g(n))): \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{none solid} \colalign{center} } \Gamma \dashv \left( \overrightarrow{m}, \dots ,\overrightarrow{n} | \overrightarrow{z}\right) : \left( \overrightarrow{A}, \dots, \overrightarrow{B}\right) \\ \left(f:\overrightarrow{A} \rightarrow \overrightarrow{F}\right) \in \mathbf{X}_1 \cdots \; \left(g:\overrightarrow{B} \rightarrow \overrightarrow{G}\right) \in \mathbf{X}_1 \quad \left( \sigma : \left(\overrightarrow{F},\dots, \overrightarrow{G}\right) \rightarrow \bigtriangleup \right) \in \Sigma_{\mathbf{X}_0} \\ \Gamma \dashv \left( \sigma \left( \overrightarrow{f}\left(\overrightarrow{m}\right),\dots,\overrightarrow{g}\left( \overrightarrow{n}\right) \right) \right) : \bigtriangleup }

in which:

  • Γ\Gamma is a context, and Δ\Delta is a (list of) type(s);
  • m,,n\overrightarrow{m}, \dots ,\overrightarrow{n} are terms of types A,,B\overrightarrow{A}, \dots , \overrightarrow{B} respectively;
  • the ff through gg are generating arrows in the set X 1\mathbf{X}_1; and
  • σ\sigma is the avatar in Σ X 0\Sigma_{\mathbf{X}_0} of some permutation.

Now, it is rather clear that we are hiding something - the gory details of the rules from which the typing judgments are derived (the so-called identity and generator rules in Shulman’s paper). However, the reader should rest assured that not only are the details not that onerous, but the more naive structural rules corresponding to tensoring, composition, and braiding are admissible. In practical terms, this means that one is simply free to work with these more intuitive rules.

Equality Judgments

Equality judgments, for example something of the form x:Ah(x)=f(g(x)):C,x:A\vdash h (x)=f\big(g(x)\big):C, which in categorical terms corresponds to a commuting diagram

are similarly derived from rules coming from the set R\mathbf{R}. We will be more explicit later on within the context of an example.

How do Symmetric Monoidal Categories fit into all this?

Until this point it is not actually terribly clear what makes this type theory specifically adapted to symmetric monoidal categories as opposed to Cartesian monoidal categories. After all, we have written contexts as lists precisely as we would write contexts in a Cartesian type theory.

Although we may not always think about it, we write contexts in Cartesian type theories as lists of typed variables because of the universal property of the product - a universal property characterized in terms of projection maps. Indeed, in a Cartesian type theory, a list of typed terms can be recovered from the list of their projections. This is not the case for arbitrary symmetric monoidal products; in general there are no projection maps. And, even when there are maps with the correct domain and codomain, there is no guarantee that they have a similar computation rule (the type theoretic avatar of a universal property).

To illustrate this in a mathematical context, consider a pair of vector spaces U 1U_1 and U 2U_2. Any element zU 1×U 2z\in U_1 \times U_2 of the Cartesian product of U 1U_1 and U 2U_2 is uniquely specified by the pair of elements pr 1(z)U 1\mathsf{pr}_{1}(z) \in U_1 and pr 2(z)U 2\mathsf{pr}_{2}(z)\in U_2 - z=(pr 1(z),pr 2(z))z=\left(\mathsf{pr}_1(z),\mathsf{pr}_2(z)\right). However, elements of the tensor product U 1U 2U_1 \otimes U_2 need not be simple tensors of the form xyx \otimes y and instead are generally linear combinations i=1 kx 1,ix 2,i\sum_{i=1}^{k}x_{1,i} \otimes x_{2,i} of simple tensors.

Provided we are careful however - meaning we do not perform any “illegal moves” in a sense we will make clear - we can still use lists. This is what Shulman does in adapting Sweedler’s notation. Consider a general element

(9) i=1 kx 1,ix 2,iU 1U 2 \sum_{i=1}^{k}x_{1,i}\otimes x_{2,i} \in U_1 \otimes U_2

In Sweedler’s notation this is written as (x (1),x (2))\left(x_{(1)}, x_{(2)}\right) with the summation, indices, and tensor symbols all dropped. Provided we make sure that any expression in which (x,y)(x,y) appears is linear in both variables, this seeming recklessness introduces no errors.

To see how this plays out, suppose that we have a morphism ff with domain AA and co-domain being the tensor product (B 1,...,B n)\left(B_1,...,B_n\right). In Shulman’s adaptation of Sweedler’s notation this corresponds to the judgment:

(10)a:A(f (1)(a),,f (n)(a)):(B 1,,B n) a:A \vdash \left( f_{\left(1\right)} \left( a \right), \dots,f_{\left(n\right)} \left( a \right) \right) : \left( B_{1},\dots,B_{n} \right)

Importantly, our typing rules will never derive the judgment a:Af (k):B ka:A\dashv f_{(k)}:B_k and we will only be able to derive a:Apr k(f (1)(a),,f (n)(a)):B ka:A \dashv \mathsf{pr}_k \left(f_{\left(1\right)}\left(a\right),\dots,f_{\left(n\right)}\left(a\right)\right):B_k if we have pr k:(B 1,,B n)B k\mathsf{pr}_k:\left(B_1,\dots,B_n\right) \rightarrow B_k in X 1\mathbf{X}_1 and more, unless R\mathbf{R} specifies that pr k\mathsf{pr}_k acts like a projection, pr\mathsf{pr} is but a name.

Since this type theory allows us to pretend, in a sense, that types are “sets with elements”, the symmetric monoidal aspect of the type theory can be moralized as:

  • terms of product types are not-necessarily-decomposable tuples;

whereas in a Cartesian “sets with elements” style type theory:

  • terms of product types are decomposable tuples.

Remark. Taking a hint from the bicategorical playbook can give us a more geometric picture of the difference between an indecomposable tuple and a decomposable one. Since every symmetric monoidal category is also a bicategory with a single object, a typed term, usually a 11-cell, also corresponds to 22-cells between (directed) loops. In this vein we may think of an indecomposable tuple (x (1),x (2),,x (n)):A\left(x_{(1)},x_{(2)},\dots,x_{(n)}\right):\overrightarrow{A} as an nn-sphere in A\overrightarrow{A} whereas a decomposable one, say (x,y,,z):A(x,y,\dots,z):\overrightarrow{A}, corresponds to a torus (of some dimension) in A\overrightarrow{A}.

Example: The Free Dual Pair

Having sketched the basics of Shulman’s PTT\mathsf{PTT} and how a presentation for a PROP\mathsf{PROP} specifies the rules of PTT\mathsf{PTT} for that PROP\mathsf{PROP}, we may now attend to an important and illuminating example. We will develop the practical type theory of the free dual pair.

Recall that a dual pair in a symmetric monoidal category abstracts the relationship

(11)Hom(AV,B)Hom(A,V B) \mathsf{Hom}(A\otimes V,B)\overset{\sim}{\longrightarrow} \mathsf{Hom}(A,V^{\star}\otimes B)

between a vector space VV and its dual, V V^{\star}.

Definition. A dual pair (D,D ,coev,ev)(D,D^{\star},\mathsf{coev},\mathsf{ev}) in a symmetric monoidal category (,(,),())\big(\mathfrak{C},(- ,-),()\big) is comprised of:

  • a pair of objects DD and D *D^{*} of \mathfrak{C};
  • a morphism coev:1DD *\mathsf{coev}:\mathbf{1}\longrightarrow D\otimes D^{*}; and
  • a morphism ev:D *D1\mathsf{ev}:D^{*}\otimes D\longrightarrow\mathbf{1}

satisfying the triangle identities:

This data suggests a presentation (R,X 1,X 0)(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0) for a PROP\mathsf{PROP}, in particular the free dual pair. We set:

  • X 0={D,D }\mathbf{X}_0 = \{D,D^\star\};
  • X 1={coev:()(D,D ),ev:(D ,D)()}\mathbf{X}_1 = \{ \mathsf{coev}:() \longrightarrow (D,D^{\star}), \mathsf{ev}:(D^{\star},D)\longrightarrow () \}; and
  • R={((D,ev)(coev,D),id D),((ev,D )(D ,coev),id D )}\mathbf{R} = \Big\{ \big( (D,\mathsf{ev}) \circ (\mathsf{coev},D) , \mathrm{id}_{D} \big), \ \big( (\mathsf{ev},D^{\star})\circ(D^{\star},\mathsf{coev}) , \mathrm{id}_{D^{\star}} \big) \Big\}

The type theory of the free dual pair

We will now develop the rules of the type theory for the free dual pair from the data this presentation (R,X 1,X 0)\left(\mathbf{R},\mathbf{X}_1,\mathbf{X}_0\right). While we have not bothered with them until now, Shulman’s practical type theory does include rules for term formation. In the case of the practical type theory for the free dual pair, the rules for the term judgment are few. We present a streamlined version of them:

(12)(x:A)Γ Γxterm1k2 coev (k)termΓmtermΓnterm Γev(m,n)term \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } (x:A) \in\Gamma \\ \Gamma\vdash x \; \mathsf{term} } \qquad \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } 1\leq k \leq 2 \\ \mathsf{coev}_{(k)}\; \mathsf{term} } \qquad \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } \Gamma\vdash m \;\mathsf{term} \quad \Gamma\vdash n \;\mathsf{term}\\ \Gamma\vdash\mathsf{ev}(m,n)\; \mathsf{term} }

The first rule is the usual variable rule which gives us the terms in which we may derive the typing judgments corresponding to identities. The second one gives us terms in which we may derive co-evaluation as a typing judgment. Finally, the last one gives us the terms in which we may derive evaluation as a typing judgment.

For the typing judgments, we have two (again slightly streamlined) rules:

  • the so-called generator rule
    (13)Γ(p,,q,r|z):(C,,D,E) h:C()X 1k:D()X 1 σ:(F,,G,E)Σ X 0τShuffle(h,,k;z) Γ(σ(f(m),,g(n),r)|τ(h(p),,k(p),z)): \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{none none solid} \colalign{center} } \Gamma \in \left( \overrightarrow{p},\dots,\overrightarrow{q},\overrightarrow{r}\left|\overrightarrow{z}\right. \right) : \left( \overrightarrow{C},\dots,\overrightarrow{D},\overrightarrow{E} \right)\\ h:\overrightarrow{C} \rightarrow () \in \mathbf{X}_1 \quad \dots \quad k:\overrightarrow{D} \rightarrow () \in \mathbf{X}_1\\ \sigma : \left(\overrightarrow{F},\dots,\overrightarrow{G},\overrightarrow{E}\right) \overset{\sim}{\longrightarrow} \bigtriangleup\in \Sigma_{\mathbf{X}_0} \tau \in \mathsf{Shuffle} \left( h,\dots,k; \overrightarrow{z} \right)\\ \Gamma \vdash \left( \left. \sigma \left( \overrightarrow{f} \left( \overrightarrow{m} \right) , \dots,\overrightarrow{g} \left( \overrightarrow{n} \right) , \overrightarrow{r} \right) \right| \tau \left( h \left( \overrightarrow{p} \right) ,\dots, k \left( \overrightarrow{p} \right) , \overrightarrow{z} \right) \right) : \bigtriangleup }
    corresponds to applying a tensor product followed by a braiding σ\sigma and a shuffling of scalars. The tensor product is taken between generating scalar-valued functions h,,kh,\dots,k (which can only be some number of copies of ev\mathsf{ev} in our case) and the identity on some object, here E\overrightarrow{E}. And,
  • the so-called identity rule
    (14)f:()BX 1g:()CX 1 σ:(A,B,,C)Σ X 0 x:A(σ(x,f,,g)|h,,k): \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{none solid} \colalign{center} } f:() \rightarrow \overrightarrow{B} \in \mathbf{X}_1 \quad \dots \quad g:() \rightarrow \overrightarrow{C} \in \mathbf{X}_1 \\ \sigma:\left( \overrightarrow{A}, \overrightarrow{B}, \dots, \overrightarrow{C} \right) \overset{\sim}{\longrightarrow} \bigtriangleup \in \Sigma_{\mathbf{X}_0} \\ \overrightarrow{x}:\overrightarrow{A} \dashv \left( \left. \sigma \left( \overrightarrow{x},\overrightarrow{f},\dots,\overrightarrow{g} \right) \right| h,\dots,k \right):\bigtriangleup}
    which corresponds to applying a braiding σ\sigma to the tensoring of some number of generating constants, here f,,gf,\dots,g (which can only be some number of copies of coev\mathsf{coev}), and the identity on some object A\overrightarrow{A}.

Remark. Here we are ignoring the notion consideration of “activeness”, a technical device introduced to rigidify the type theory into one with unique derivations of judgments by providing a canonical form for 1-cells. We also ignored the syntactic sugar of labels, which act like formal variables for the unit type.

Lastly, for the equality judgment we have axioms

(15)((D,ev)(coev,D),id D)R m:D(coev (1)|ev(coev (2),M))=m:D \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } \left( (D,\mathsf{ev}) \circ \left( \mathsf{coev},D \right) , \mathrm{id}_{D} \right) \in \mathbf{R} \\ m:D \vdash \left(\mathsf{coev}_{(1)} \left| \mathsf{ev}\left(\mathsf{coev}_{(2)},M\right) \right.\right) = m:D }


(16)((ev,D )(D ,coev),id D )R n:D (coev (2)|ev(N,coev (1)))=n:D \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } \left( ( \mathsf{ev} , D^{\star}) \circ \left( D^{\star},\mathsf{coev} \right) , \mathrm{id}_{D^{\star}} \right) \in \mathbf{R} \\ n:D^{\star} \vdash \left( \mathsf{coev}_{(2)} \; \left| \; \mathsf{ev} \left( N,\mathsf{coev}_{(1)} \right) \right. \right) = n:D^{\star} }

together with enough rules so that == acts as a congruence relative to all of the other rules.

Example. Consider the composition

(17)(D)(coev,D)(D,D *,D)(D,ev)(D) (D)\xrightarrow{\left(\mathsf{coev},D\right)} \left(D,D^{*},D\right) \xrightarrow{\left(D,\mathsf{ev}\right)} (D)

which corresponds to the typing judgement

(18)x:D(coev (1)|ev(coev (2),x)):D x:D\vdash \left(\mathsf{coev}_{(1)}|\mathsf{ev} \left(\mathsf{coev}_{(2)},x\right)\right):D

This typing judgement admits the following derivation

(19)coev:()(D,D )X 1 (132):(D,D,D )(D,D ,D) x:D(coev (1),coev (2),x):D ev:(D *,D)()X 1 x:D(coev (1)|ev(coev (2),x)):D \array{ \arrayopts{ \frame{none} \rowalign{bottom} \rowlines{solid} } \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{solid} \colalign{center} } \mathsf{coev}:() \rightarrow (D,D^{\star}) \in \mathbf{X}_1 & (132): \left( D,D,D^{\star} \right) \overset{\sim}{\longrightarrow} \left( D,D^{\star},D \right) \\ \cellopts{\colspan{2}} x:D\vdash \left( \mathsf{coev}_{(1)},\mathsf{coev}_{(2)},x \right):D } & \mathsf{ev}: \left(D^*,D\right) \rightarrow () \in \mathbf{X}_1 \\ \cellopts{\colspan{2}} x:D\vdash \left( \left. \mathsf{coev}_{(1)} \right| \mathsf{ev} \left( \mathsf{coev}_{(2)},x \right) \right):D }


  • the first rule is an instance of the identity rule with premised generators coev\mathsf{coev} and the braiding (132)(132); and
  • the second rule is an instance of the identity rule with the typing judgement x:D(coev (1),coev (2),x):Dx:D\vdash \left(\mathsf{coev}_{(1)},\mathsf{coev}_{(2)},x\right):D the consequent of the first rule and the additional hypothesis being the generator ev\mathsf{ev}.

“Elements” of dual objects

We have now developed a type theory for the free dual pair which endows the dual objects DD and D D^{\star} with a universal notion of element (that of DD-typed term and D D^{\star}-typed term respectively). Since the notion of dual pair abstracted the instance of a pair of dual vector spaces, which in particular have actual elements, it behooves us to ask:

“to what extent is term of type DD like a vector (in DD)?”

The answer is both practical and electrifying (though perhaps the authors of this post are too easily electrified).

It’s easy enough to believe that the evaluation map

(20)ev:(D,D )() \mathsf{ev}:\left(D,D^{\star}\right)\longrightarrow ( )

endows the terms of type DD, or D D^{\star} for that matter, with a structure of scalar valued functions on the other. The triangle identities impose the unique determination of terms of type DD or D D^{\star} in terms of their values as given by ev\mathsf{ev}. Indeed consider that, for a finite dimensional vector space VV over a field kk, a basis {e i} i=1 n\{ \mathbf{e}_{i}\}_{i=1}^{n} for VV and a dual basis {e i } i=1 n\{ \mathbf{e}_{i}^{\star}\}_{i=1}^{n} for V V^{\star} give us an elegant way to write coev\mathsf{coev} and the first triangle identity. We write

(21)k coevVV x i=1 ne ie i \begin{aligned} k & \overset{\mathsf{coev}}{\rightarrow} V\otimes V^{\star}\\ x & \mapsto \sum_{i=1}^{n}\mathbf{e}_{i}\otimes\mathbf{e}_{i}^{\star} \end{aligned}

and see that

The observation for dual vector spaces

(22)VandV =Hom Vect k(V,k) V \mathrm{ and } V^{\star}=\mathsf{Hom}_{\mathsf{Vect}_k}(V,k )

that the triangle identities hold is just the observation that a vector is precisely determined by its values: every vector v\mathbf{v} is equal to the un-named vector

(23) i=1 ne i (v)e i \sum_{i=1}^{n}\mathbf{e}_i^{\star}( \mathbf{v})\cdot \mathbf{e}_i

which is defined by taking the values e i (v)\mathbf{e}^\star_{i}( \mathbf{v} ) at the dual vectors e i \mathbf{e}_i^{\star}. As part of the definition of a dual pair in an arbitrary symmetric strict monoidal category then, the triangle identities imposes this as a relationship between ev\mathsf{ev} and coev\mathsf{coev}. But within type theory, this sort of relationship between an un-named function and its values is familiar, indeed it is something very much like β\beta-reduction.

To see this more clearly, let us make a pair of notational changes. In place of writing

(24)(x,y):(D ,D)ev(x,y):() (x,y) : \left( D^{\star},D \right) \vdash \mathsf{ev}(x,y):()

we will denote ev\mathsf{ev} infix by \triangleleft and write

(25)(x,y):(D ,D)xy:() (x,y) : \left( D^{\star},D \right) \vdash x\triangleleft y:()

Similarly, in place of writing

(26)(coev (1),coev (2)):(D,D ) \vdash \left( \mathsf{coev}_{(1)},\mathsf{coev}_{(2)} \right):\left(D,D^{\star}\right)

we will denote coev\mathsf{coev} by the pair (u,λ Du)\left(u,\lambda^{D}u\right) and write

(27)(u,λ Du):(D,D ) \vdash\left(u,\lambda^{D}u\right):\left(D,D^{\star}\right)

With this choice of notation then, the equality judgment which corresponds to the first triangle identity is

(28)x:D(u|λ Dux)=x:D x:D\vdash\left( u \; \left| \; \lambda^{D}u\triangleleft x\right.\right)=x:D

Then, since == is a congruence with respect to substitution (recall that we promised that the rules for the equality judgement were precisely those required for generating a congruence from a set of primitive relations), if we have, for some term mm, the term λ Dum\lambda^{D}u\triangleleft m appearing in the scalars of a list of terms, then we may replace all instances of uu in the rest of the term with mm. While a mouthful, this is a sort of “β\beta-reduction for duality” allowing us to treat coev\mathsf{coev} as a sort of λ\lambda-abstraction, as we suggested by the change in notation. Conceptually interesting in its own right, this observation also yields a one line proof for a familiar theorem, namely the cyclicity of the trace.

Example. Consider two dual pairs

(29)(A,A *,(u,λ Au),) (B,B *,(v,λ Bv),) \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{none} } \left(A,A^{*},\left(u,\lambda^{A}u\right),-\triangleleft -\right) &\qquad \qquad& \left(B,B^{*},\left(v,\lambda^{B}v\right),- \triangleleft -\right) }

in a symmetric strict monoidal category (,(,),())\big(\mathfrak{C},(-, -),()\big) and a pair of maps f:ABf:A\longrightarrow B

(30)()(v,λ Bv)(B,B )fg(B,B )(12)(B ,B)() ()\overset{(v,\lambda^{B}v)}{\longrightarrow} \left(B,B^{\star}\right)\overset{f\circ g}{\longrightarrow} \left(B,B^{\star}\right)\overset{(12)}{\longrightarrow} \left(B^{\star},B\right)\overset{ - \triangleleft -}{\longrightarrow} ()

where (12)(12) denotes the permutation of entries of the list. Likewise the trace tr(gf)\mathsf{tr}\left(g\circ f\right) is the composition.

(31)()(v,λ Av)(A,A )gf(A,A )(12)(A ,A)() ()\overset{(v,\lambda^{A}v)}{\longrightarrow} \left(A,A^{\star}\right)\overset{g\circ f}{\longrightarrow} \left(A,A^{\star}\right)\overset{(12)}{\longrightarrow} \left(A^{\star},A\right)\overset{ - \triangleleft -}{\longrightarrow} ()

Using the notation introduced above it follows that tr(fg)=tr(gf)\mathsf{tr}\left(f\circ g\right)=\mathsf{tr}\left(g\circ f\right) as:

(32)tr(fg) =def (|λ u Bf(g(u))) = (|λ u Bf(v),λ v Ag(u)) = (|λ v Ag(f(v))) =def tr(gf) \array {\arrayopts{ \frame{none} \rowalign{top} \rowlines{none} \colalign{right left left } } \mathsf{tr}(f\circ g) & \overset{\mathsf{def}}{=} & \left( \left| \lambda_{u}^{B}\triangleleft f\big( g(u) \big) \right. \right) \\ & = & \left( \left| \lambda_{u}^{B}\triangleleft f(v),\lambda_{v}^{A}\triangleleft g(u) \right. \right) \\ & = & \left( \left| \lambda_{v}^{A}\triangleleft g\big(f(v)\big) \right. \right) \\ & \overset{\mathsf{def}}{=} & \mathsf{tr}(g\circ f) }

Where the judged equalities are applications of “β\beta-reduction for a duality”.

Posted at September 14, 2021 4:57 PM UTC

TrackBack URL for this Entry:

3 Comments & 0 Trackbacks

Re: Shulman’s Practical Type Theory for Symmetric Monoidal Categories

Interesting, thanks. I see in Mike’s paper he makes comparison with other notations (Sec. 1.10 and elsewhere), writing

There is no reason to expect any one notation for symmetric monoidal categories to be the best in all situations: each has applications to which it is better-suited and others to which it is not as well suited. The new type theory presented here makes no claim to supplant string diagrams or intuitionistic linear logic; rather it is an alternative that may be more convenient in some applications. Only time and experience can render a final verdict on the usefulness of a notation, as well as its generalizations and limitations…

Do you have a sense of when this type theory will display its advantages?

Posted by: David Corfield on September 15, 2021 8:03 AM | Permalink | Reply to this

Re: Shulman’s Practical Type Theory for Symmetric Monoidal Categories

I don’t think I’m expert enough either in string calculi or in linear type theory to make too strong a claim, but I do have some suspicions. I think that Mike’s practical type theory lends itself towards higher- dimensional/homotopical generalization better than those other two systems/logics/notations. I say this largely because of early successes we - the ACT group from 2020 - have had in developing a bi-categorical variant of this type theory (an ongoing project).

Posted by: Paul Lessard on September 18, 2021 1:15 AM | Permalink | Reply to this

Re: Shulman’s Practical Type Theory for Symmetric Monoidal Categories

I look forward to reading about it.

Posted by: David Corfield on September 18, 2021 12:31 PM | Permalink | Reply to this

Post a New Comment