The n-Category Café

Suppose you wanted to “freely” generate a symmetric monoidal category from some combinatorial data. What could that data be? In other words (for a category theorist at least), what sort of category $C$ appears in an adjunction $C \rightleftarrows SMC$? (By the way, all monoidal categories in this post will be strict, so I’m going to drop that adjective for conciseness.)

Perhaps the simplest choice is the same data that naturally generates a plain category, namely a directed graph. However, this is pretty limited in terms of what symmetric monoidal categories it can generate, since the generating morphisms will always only have single generating objects as their domain and codomain.

Another natural choice is the same data that naturally generates a multicategory, which might be called a “multigraph”: a set of objects together with, for every tuple of objects $x_1,\dots,x_n$ and single object $y$, a set of arrows from $(x_1,\dots,x_n)$ to $y$. In the generated symmetric monoidal category, such an arrow gives rise to a morphism $x_1\otimes\cdots\otimes x_n \to y$; thus we can now have multiple generating objects in the domains of generating morphisms, but not the codomains.

Of course, this suggests an even better solution: a set of objects, together with a set of arrows for every pair of tuples $(x_1,\dots,x_m)$ and $(y_1,\dots,y_n)$. I’d be tempted to call this a “polygraph”, since it also naturally generates a polycategory. But other folks got there first and called it a “tensor scheme” and also a “pre-net”. In the latter case, the objects are called “places” and the morphisms “transitions”. But whatever we call it, it allows us to generate free symmetric monoidal categories in which the domains and codomains of generating morphisms can both be arbitrary tensor products of generating objects. For those who like fancy higher-categorical machinery, it’s the notion of computad obtained from the monad for symmetric monoidal categories.

However, pre-nets are not without flaws. One of the most glaring, for people who actually want to compute with freely generated symmetric monoidal categories, is that there aren’t enough morphisms between them. For instance, suppose one pre-net $N$ has three places $x,y,z$ and a transition $f:(x,x,y) \to z$, while a second pre-net $N'$ has three places $x',y',z'$ and a transition $f':(x',y',x') \to z'$. Once we generate a symmetric monoidal category, then $f$ can be composed with a symmetry $x\otimes y \otimes x \cong x\otimes x\otimes y$ and similarly for $f'$; so the symmetric monoidal categories generated by $N$ and $N'$ are isomorphic. But there isn’t even a single map of pre-nets from $N$ to $N'$ or vice versa, because a map of pre-nets has to preserve the ordering on the inputs and outputs. This is weird and annoying for combinatorial data that’s supposed to present a symmetric monoidal category.

Another way of making essentially the same point is that just as the adjunction between SMCs and directed graphs factors through categories, and the adjunction between SMCs and multigraphs factors through multicategories, the adjunction between SMCs and pre-nets factors through non-symmetric monoidal categories. In other words, a pre-net is really better viewed as data for generating a non-symmetric monoidal category, which we can then freely add symmetries to.

By contrast, in the objects that we call “Petri nets”, the domain and codomain of each generating morphism are elements of the free commutative monoid on the set of places — as opposed to elements of the free monoid, which is what they are for a pre-net. Thus, the domain of $f$ and $f'$ above would be $x+x+y$ and $x+y+x$ respectively, which in a commutative monoid are equal (both are $2x+y$). So the corresponding Petri nets of $N$ and $N'$ are indeed isomorphic. However, once we squash everything down in this way, we lose the ability to functorially generate a symmetric monoidal category; all we can generate is a commutative monoidal category where all the symmetries are identities.

At this point we’ve described the upper row and the left- and right-hand columns in John’s diagram:

What’s missing is a kind of net in the middle that corresponds to symmetric monoidal categories. To motivate the definition of $\Sigma$-net, consider how to solve the problem above of the “missing morphisms”. We want to send $f:(x,x,y) \to z$ to a “permuted version” of $f':(x',y',x') \to z'$. For this to be implemented by an actual set-map, we need this “permuted version” to be present in the data of $N'$ somehow. This suggests that the transitions should come with a permutation action like that of, say, a symmetric multicategory. Then inside $N'$ we can actually act on $f'$ by the transposition $\tau = (2,3) \in S_3$, yielding a new morphism $\tau(f') : (x',x',y')\to z'$ which we can take to be the image of $f$. Of course, we can also act on $f'$ by other permutations, and likewise on $f$; but since these permutation actions are part of the structure they must be preserved by the morphism, so sending $f$ to $\tau(f')$ uniquely determines where we have to send all these permutation images.

Now you can go back and look again at John’s definition of $\Sigma$-net: a set $S$, a groupoid $T$, and a discrete opfibration $T \to P S \times P S ^{op}$, where $P$ denotes the free-symmetric-strict-monoidal-category functor $Set \to Cat$. Such a discrete opfibration is the same as a functor $N:P S \times P S ^{op} \to Set$, and the objects of $P S$ are the finite sequences of elements of $S$ while its morphisms are permutations; thus this is precisely a pre-net (the action of the functor $N$ on objects) with permutation actions as described above. I won’t get into the details of constructing the adjunction relating $\Sigma$-nets to symmetric monoidal categories; you can read the paper, or maybe I’ll blog about it later.

However, in solving the “missing morphisms” problem, we’ve introduced a new possibility. Suppose we act on $f:(x,x,y) \to z$ by the transposition $\sigma = (1,2) \in S_3$ that switches the first two entries. We get another transition $(x,x,y)\to z$ with the same domain and codomain as $f$; so it might equal $f$, or it might not! In other words, transitions in a $\Sigma$-net can have isotropy. If $\sigma(f)=f$, then when we generate a free symmetric monoidal category from our $\Sigma$-net, the corresponding morphism $f:x\otimes x \otimes y \to z$ will have the property that when we compose it with the symmetry morphism $x\otimes x\otimes y \cong x\otimes x\otimes y$ we get back $f$ again. No symmetric monoidal category generated by a pre-net has this property; it’s more like the behavior of the commutative monoidal category generated by a Petri net, except that in the latter case the symmetry $x\otimes x\otimes y \cong x\otimes x\otimes y$ itself is the identity, rather than just acting by the identity on $f$.

This suggests that $\Sigma$-nets can either “behave like pre-nets” or “behave like Petri nets”. This is made precise by the bottom row of adjunctions in the diagram. On one hand, we can map a pre-net to a $\Sigma$-net by freely generating the action of all permutations. This has a right adjoint that just forgets the permutation action (which actually has a further right adjoint, although that’s a bit weird). On the other hand, we can map a Petri net to a $\Sigma$-net by making all the permutations act as trivially as possible; this has a left adjoint that identifies each transition with all its permutation images. And these adjunctions commute with the three “free monoidal category” adjunctions in reasonable ways (see the paper for details).

The right adjoint mapping Petri nets into $\Sigma$-nets is fully faithful, so we really can say that $\Sigma$-nets “include” Petri nets. The left adjoint mapping pre-nets to $\Sigma$-nets is not fully faithful — it can’t possibly be, since the whole point of introducing $\Sigma$-nets was that pre-nets don’t have enough morphisms! But the full image of this functor is equivalent to a fourth kind of net: Kock’s whole-grain Petri nets. Kock’s approach to solving the problem of pre-nets is somewhat different, more analogous to the notion of “fat” symmetric monoidal category: he takes the domain and codomain of each transition to be a family of places indexed by a finite set. But his category turns out to be equivalent to the category of $\Sigma$-nets that are freely generated by some pre-net. (Kock actually proved this himself, as well as sketching the adjunction between $\Sigma$-nets and symmetric monoidal categories. He called $\Sigma$-nets “digraphical species”.)

So $\Sigma$-nets “include” both Petri nets and pre-nets, in an appropriate sense. The pre-nets (or, more precisely, whole-grain nets) are the $\Sigma$-nets with free permutation actions (trivial isotropy), while the Petri nets are the $\Sigma$-nets with trivial permutation actions (maximal isotropy). In Petri-net-ese, these correspond to the “individual token philosophy” and the “collective token philosophy”, respectively. (This makes it tempting to refer to the functors from $\Sigma$-nets to pre-nets and Petri nets as individuation and collectivization respectively.) But $\Sigma$-nets also allow us to mix and match the two philosophies, having some transitions with trivial isotropy, others with maximal isotropy, and still others with intermediate isotropy.

I like to think of $\Sigma$-nets as a Petri net analogue of orbifolds. Commutative-monoid-based Petri nets are like “coarse moduli spaces”, where we’ve quotiented by all symmetries but destroyed all the isotropy information; while whole-grain Petri nets are like manifolds, where we have no singularities but can only quotient by free actions. Pre-nets can then be thought of a “presentation” of a manifold, such as by a particular way of gluing coordinate patches together: useful in concrete examples, but not the “invariant” object we really want to study mathematically.