Categorifying Eigenvalues

In a previous blog post I showed that there is an embedding

\mathsf{Mat_R} \hookrightarrow \mathsf{RProf}

from the category of matrices valued in a commutative quantale R and the category of R-enriched profunctors. This suggests that profunctors generalize matrices and indeed they do. We may then ask what techniques of linear algebra generalize to arbitrary profunctors? In this post we generalize the definition of eigenvalue and eigenvector to arbitrary profunctors. We will use ordinary \mathsf{Set}-profunctors, i.e. functors

P:C \times D^{op} \to \mathsf{Set}.

It will be hard to transfer intuition from linear algebra when C and D are too infinite so we consider only the case when C and D have a finite set of objects. These profunctors live in the following category.

Definition: Let \mathsf{FinProf} be the category where

  • objects are categories C,D,.. with a finite set of objects,
  • morphisms are profunctors P:  C \times D^{op} \to \mathsf{Set}, and
  • the composition of a profunctor P: C \times D^{op} \to \mathsf{Set} with a profunctor Q: D \times E^{op} \to \mathsf{Set} is given by the coend formula

P ; Q (c,e) = \int^{d \in D} P(c,d) \times Q(d,e)

where ; denotes the forward order composition (as opposed to \circ which is used for reverse order composition).

I get my intuition about this coend formula from the case of R-enriched profunctors (which gives ordinary matrix multiplication). In either case, the composition sums the values over all intermediate indices. For the coend above, we must also quotient this sum so that the actions of C and D agree.

We can always decategorify a profunctor P : C \times D^{op} \to \mathsf{Set} to a \mathbb{N} valued matrix

|P| : Ob C \times Ob D \to \mathbb{N}

given by

|P|(c,d)= | P(c,d)|

where the second absolute value indicates the magnitude of a set. Whatever categorification of eigenvalue and eigenvector that we choose, it better correspond to the usual thing when decategorified.

For an ordinary matrix M: X \to Y, a number \lambda is an eigenvalue with eigenvector v if

M v = \lambda v.

To generalize this to arbitrary profunctors first we need to generalize vectors, scalar multiplication, and equality.

categorifying vectors and their multiplication

An n-dimensional vector is a matrix v :  n \to 1 where n is your favorite n element set and 1 is your favorite 1 element set. Similarly, a categorified vector will be a profunctor

\mathbf{v} : \mathbf{n} \to \mathbf{1}

where \mathbf{n} is a category with n objects and \mathbf{1} is a category one object. I am leaving the definitions of \mathbf{n} and \mathbf{1} vague on purpose. They are allowed to have any set of morphisms you like; as long as \mathbf{n} has n objects and \mathbf{1} has one object, \mathbf{v} will decategorify to a nx1 vector. To multiply a categorified matrix with a categorified vector we use profunctor composition. For a category \mathbf{m} with m objects, a profunctor M : \mathbf{m} \to \mathbf{n} composes with \mathbf{v} to obtain a categorifed vector

M ; v : \mathbf{m} \to \mathbf{1}

given by

(M ; v) (x,*) = \int^{y \in \mathbf{n}} M(x,y) \times v(y,*)

where * is the unique object of \mathbf{1}. This decategorifies to the right thing because

|(M ; v)(x,*) | = | \int^{y \in \mathbf{n}} M(x,y) \times v(y,*) |

= \sum_{y \in Ob \mathbf{n}} | M(x,y) \times v(y,*)|

=\sum_{y \in Ob \mathbf{n}} | M(x,y) |\times | v(y,*)|.

In other words it is the matrix multiplication | M | | v| of their decategorifications.

categorifying scalar multiplication

A scalar is a 1×1 matrix so we define a categorified scalar to be a profunctor

\alpha : \mathbf{1} \times \mathbf{1}^{op} \to \mathsf{Set}.

where \mathbf{1} is any category with one object. The product of \alpha with a profunctor M : \mathbf{m} \times \mathbf{n}^{op} \to \mathsf{Set} is the profunctor

\alpha M : \mathbf{m} \times \mathbf{n}^{op} \to \mathsf{Set}

given by

\alpha M (x,y) = \alpha(*,*) \times M(x,y).

This decategorifies to |\alpha | \cdot |M(x,y)| because

| \alpha(*,*) \times M(x,y) | = |\alpha(*,*)| \cdot |M(x,y)|.

categorifying equality of matrices

A general maxim of categorification is that when you categorify equalities must be replaced with isomorphisms. We need to do this for the eigenvalue equation but what category should the isomorphisms live in? We will use the following.

Definition: Let \mathsf{Prof}(C,D) be the category where

  • objects are profunctors P : C \times D^{op} \to \mathsf{Set}, and
  • morphisms are natural transformations \beta : P \Rightarrow Q with components

\beta_{c,d} : P(c,d) \to Q(c,d).

An isomorphism in this category is a natural isomorphism of the above type.

categorifying the eigenvalue equation

We are now ready to state the definition of categorified eigenvalues and categorified eigenvectors.

Definition: A profunctor \lambda : \mathbf{1} \times \mathbf{1}^{op} \to \mathsf{Set} is a categorified eigenvalue of a profunctor M :  \mathbf{n} \times \mathbf{n}^{op} \to \mathsf{Set} with categorified eigenvector \mathbf{v}: \mathbf{n} \times \mathbf{1}^{op} \to \mathsf{Set} if they are equipped with an isomorphism

\beta : M ; \mathbf{v} \xrightarrow{\sim} \alpha ; v

in the category \mathsf{Prof}(\mathbf{n}, \mathbf{1}) of profunctors between \mathbf{n} and \mathbf{1}.

So that’s neat. There are tons of useful things you can do with eigenvalues. You could spend many hours getting lost in the rabbit holes on their wikipedia page. Can we categorify these facts to obtain interesting things about profunctors? Probably, but I will leave this for the next installment.

Nets within nets from the Grothendieck construction

This blog post is regarding (elementary) object systems. Object systems were first introduced in

  • Rüdiger Valk, Object Petri nets, In Advanced Course on Petri Nets, pp. 819-848, 2003.

An object system is a very meta thing, it is a Petri net, whose tokens are marked Petri nets. Here is an example from Valk’s paper

meant to represent three people simultaneously putting out a fire. The lower Petri net in this picture represents the global Petri net. In the top half of the image, squares with local Petri nets in them are depicted pointing to the tokens which they are represented by. When, for example, the first <approachFire> transition in the global Petri net fires, two things occur:

  1. The token in place A is moved to place B and,
  2. This Petri net represented by this token fires its own <approachFire> transition, putting a token in the place q.1.

So in general, a firing of an elementary object system is either a firing of a global net or a local net. If the global net fires, then the corresponding transitions in the local net must be fired as well. As you may imagine, this type of net is great for modelling hierarchical concurrent systems where there are multiple agents who interact in a concurrent way.

In this blog post I’ll show you how to construct a category of object systems and their generalizations using the Grothendieck construction! It starts with an idea that has been central to my research so far, that the space of all firing sequences of Petri can be represented as a symmetric monoidal category. Indeed for a Petri net P, there is a symmetric monoidal category F(P) where

  • objects are sums of species, i.e. markings of P,
  • morphisms are arbitrary sums and composites of transitions i.e. firing sequences and,
  • monoidal product is sum, which represents parallel composition on a pair of firing sequences.

Furthermore this process of forming firing sequences forms a left adjoint functor

F: \mathsf{Petri} \to \mathsf{CMC}

where \mathsf{CMC} is the category of strictly commutative symmetric monoidal categories (the type of symmetric monoidal category that Petri nets happen to generate). Commutative monoidal categories are in particular categories so there is a forgetful functor

R: \mathsf{CMC} \to \mathsf{Cat}

which does nothing to the objects and morphisms. We can compose R with our left adjoint from before to get a functor

R \circ F : \mathsf{Petri} \to \mathsf{Cat}.

At this point you should pause and guess what I do next, it’s something I do over and over on this blog

The answer is the Grothendieck construction. For a review of the Grothendieck construction check out my blog:

If we take the Grothendieck construction of the functor R \circ L, then we obtain a category \int R \circ F where

  • objects are pairs (P, m) where P is a Petri net and m is a marking of P and,
  • morphisms are pairs (f,t): (P,m) \to (Q,n) where f is a morphism of Petri nets and t is a firing sequence from f(m) \to n.

I actually talked about this category in a previous blog post:

Which contains a more in-depth discussion of the construction we have just performed. \int R \circ F is a category whose objects are marked Petri nets and whose morphisms represent changing the structure of your Petri net and firing your initial marking. Because \int G \circ F has marked Petri nets as objects, let’s call it \mathsf{MkPetri}. \mathsf{MkPetri} is symmetric monoidal with monoidal product given by

(P,m) \oplus (Q,n) = (P+Q,m+n)

Here P+Q is the coproduct of Petri nets and m+n is the marking of P+Q which agrees with m on the P-component and agrees with n on the Q component. In other words, m+n is the formal sum of m and n. The main claim of this blog post is that the following is a reasonable definition:

Definition: An object system is a symmetric monoidal functor

E : (FP,+) \to (\mathsf{MkPetri},\oplus)

where FP is the free commutative monoidal category on a Petri net P.

The idea is that P is the global Petri net and the functor E assigns the local Petri nets and their transformation rules. Explicitly, for a place p, the marked Petri net E(p) is the local Petri net which is assigned to p. This determines the action of E on objects up to isomorphism because FP is free. For a transition \tau with source $a +b$ and target $c+d$,

E(\tau) : E(a) \oplus E(b) \to E(c) \oplus E(d)

is a pair (f,s) where

  • f is a morphism from disjoint union local Petri nets in the source to the disjoint union of the local Petri nets in the target (this determines how the transition $\tau$ mutates the structure of each local Petri net in the source and target) and,
  • s is firing sequence, (this determines how \tau alters the markings of the local Petri nets).
  • Because FP is free, this case determines the action of E on all firing sequences.

This definition describes object systems using Lawvere’s idea of functorial semantics. The global Petri net P provides a syntax and the functor equips that syntax with a semantics based in marked Petri nets.

Beware that this definition does not match exactly the definition introduced by Valk. In those object systems, transitions in the global net are not allowed to mutate the local Petri nets. I see this as a feature not a bug, object systems by our definition are more general than the object systems defined by Valk. The ability to mutate the local nets means that these object systems are more expressive.

The second thing about this definition which doesn’t match Valk’s is that our global nets don’t come equipped with an initial marking. However, you can equip them with an initial marking using the same construction that we used to obtain marked Petri nets. I won’t go into too many details here, but the idea is that object systems also have a “category of firing sequences functor”

\mathsf{ObSys} \to \mathsf{CMC}

which we can take the Grothendieck construction to obtain a category of marked object systems. At this point we would be two Grothendieck constructions in, which I find to be very confusing as well as fun; it’s kind of like a double integral.

Thank you for reading and please let me know if you would like me to clarify something.

A clarification.

Some people have asked me to clarify the meaning of my previous blog post, the Lie of “it’s just math”. I sort of regret that my post suggested a strict rule for dealing with military funding. I said that I don’t intend on collaborating with DoD funded mathematicians and I meant it. However, there is a lot of room for interpretation in the meaning of “collaborate” and the meaning of “DoD funded”. For example, are short conversations at a conference considered collaborations? If a mathematician has ten funding sources for their research group and one of them is the department of defense are they DoD funded? These are questions that I would like to decide on an individual basis and not based on a hard and fast rule.

There are lots of considerations I have to make personally. I am looking for a job and taking the strictest interpretation will significantly reduce my options. To be honest this topic gives me a lot of anxiety, based on the worry that I’ll be ostracized from the applied category theory community completely. I suppose that I need to offer some clarification.

I am not interested in “canceling” anyone or cutting anyone off. However, I do not want to work on DoD funded projects or contribute to projects funded by the DoD when I can help it. If a mathematician is employed by the DoD entirely then I probably don’t want to collaborate with them on much. If a mathematician has DoD funding as one of many sources, then I am happy to help with their non-DoD funded projects, as long as there isn’t overlap with a DoD funded one.

If I was a senior mathematician in charge of a large DoD grant, I’m not sure what I would do and I don’t think I have all the answers. Quitting a DoD funded project might mean laying some people off and many contracts cannot be broken without significant penalty. These senior mathematicians have hard choices to make and I don’t want to make light of them. I am still starting out, so I believe that I have the ability to not be in their position if I reject DoD funding from the very beginning. I am not advocating that these senior mathematicians do anything drastic. However I do hope to convince them to move away from these grants in the future.

I consider myself to be a conscientious objector, i.e. an “individual who has claimed the right to refuse to perform military service on the grounds of freedom of thought, conscience, or religion”. Like many other conscientious objectors, my choice is motivated by conscience and religion. As a proud Jew I believe in tikkun olam, and I don’t think I can be at peace with myself unless I work to make peace in the world. I also see in the military industrial complex the same ideologies and behaviors which almost led to the extinction of the Jewish people. Even if we all are just cogs in a large bureaucracy, we can’t be absolved of responsibility.

The Lie of “It’s Just Math”

In 2020 the Defense Advance Research Projects Agency (DARPA) funded over 220 million dollars in Math and Computer Science Research (DARPA Budget). In my field (Applied Category Theory) the best funded research programs are funded by either DARPA or the Air Force. At first this seems kind of baffling. Why does the Air Force care about using homotopy theory to find an alternative foundation for mathematics? Why does DARPA care about the properties of colored operads? Many mathematicians give them the benefit of the doubt. If the military is interested in funding projects which seem to just enrich mathematics as a whole, then maybe their intentions aren’t so bad. This is a convenient explanation, made more convenient by the high paying jobs and hefty grants that the Department of Defense (DoD) offers. Unfortunately, my personal experience has shown me that there is no truth in it.

The DoD’s real goal is not just the math you produce, they want to gain access to your mathematical community. Maybe you would never work on missile guidance systems. That’s okay, the people you work with at the DoD will gain expertise in your mathematical specialty. They will present at conferences and find new collaborators who will have more flexible morals than you.

Your math is not too abstract to be useful. The DoD wants to build themselves into these mathematical communities from the very beginning so that when it does eventually become practical they will be poised to take advantage. If it takes a longer time to become practical then that means the DoD will have enough time to become entrenched into the foundations of the subject.

The DoD wants to normalize themselves in your non-mathematical communities. Since 2001, over 800,000 people have been *directly* killed and more than 37 million made refugees in the US post 9-11 wars (https://watson.brown.edu/costsofwar/). The DoD wants US Citizens to be okay with that and the best way to gain an ally is to go in business together. The DoD wants to demonstrate that they can put food on your table and advance your interests so that you will turn a blind eye to the violence they commit abroad.

The DoD will lie to you. A friend of mine worked for a project whose public goal was to provide technology for search and rescue operations. However, in more private conversations the terminology slipped from “search and rescue” to “search and destroy”. None of the researchers in this project or their collaboraters were made aware of this. The DoD is under no obligation to tell you the true motivations behind your grant or job. Sometimes these motivations are classified.

As conditions in US worsen, I think one of the best things we can do to heal the world is to stop doing things that make it worse. I personally do not plan on collaborating with DoD funded mathematicians and I hope you will join me. If Grothendieck knew what his math was being used for he would roll in his grave.

Euler’s Method as a Free Category

In this blog post I will show how the numerical solutions to a differential equation using Euler’s method can be represented as a free category on a graph. Given a vector field

v: \mathbb{R}^n \to \mathbb{R}^n

and a step size h>0, you can form a graph whose vertices are elements of \mathbb{R}^n and whose edges advance Euler’s method by one time step. The free category on this graph then contains all runs of Euler’s method on v for all possible lengths of time.

what is Euler’s method?

Let v: \mathbb{R}^n \to \mathbb{R}^n be a vector field i.e. a smooth function. Euler’s method computes an approximate solution to the differential equation

\frac{d\mathbf{x}}{dt} = v(\mathbf{x})

where \mathbf{x} is a vector in \mathbb{R}^n. The core of Euler’s method is the equation

\mathbf{x}(t+h) = \mathbf{x}(t) + h v(\mathbf{x}(t))

where h is a positive real number. Given an initial condition \mathbf{x}(0) = \mathbf{x_0} an approximate solution can be computed by repeatedly applying the above equation.

the categories in question

Let \mathsf{Span(V,V)} be the category where

  • objects are spans V \leftarrow A \to V and,
  • a morphism from V\leftarrow A \to V to V \leftarrow B \to V is a function f: A \to B commuting with the functions in each span

Note that \mathsf{Span(V,V)} is a category where objects are graphs with vertex set V.

Let \mathsf{Cat(V)} be the category where

  • objects are categories whose objects are elements of V and,
  • morphisms are functors between such categories.

the free category construction

There is a forgetful functor

U : \mathsf{Cat(V)} \to \mathsf{Span(V,V)}

which sends a category to it’s underlying graph and a functor to its underlying morphism of graphs. Then U has a left adjoint

F : \mathsf{Span(V,V)} \to \mathsf{Cat(V)}

generating for each graph a category whose morphisms contain all possible composites of edges. The idea is that given a graph

we can put another copy next to it and take the pullback

Explicitly, this pullback is the set

E \times_V E = \{ (a,b) \in E \times E \, | \, t(a) = s(b) \}

i.e. the set of composable pairs of edges. This pullback can be iterated. In general for a natural number n, the n-th pullback is the set

E^n = \{ (a_1,a_2, \ldots, a_n) \, | \, t(a_1)=s(a_2), t(a_2)= s(a_3) \ldots t(a_{n-1}) = s(a_n) \}

i.e. the n-tuples of composable edges. To get all composable edges of any length we need to combine all these sets. Indeed, the free category has morphisms given by the infinite coproduct

\sum_{n=0}^{\infty} E^n

where the 0-th pullback is defined to be the vertex set V. This free category has composition given by concatenation of tuples.

putting the ingredients together and baking the cake

The key is to consider the span

A=\mathbb{R}^n \xleftarrow{1} \mathbb{R}^n \xrightarrow{1 + h v}  \mathbb{R}^n

where 1 is the identity function and 1 + hv (\mathbf{x}) = \mathbf{x} + h v(\mathbf{x}). The k-th pullback of this span with itself is the set

\{ (x_1,x_2,\ldots, x_k) \in \mathbb{R}^{n \times k}\, | \, x_2 = x_1 + h v(x_1),\ldots, x_{k} = x_{k-1} + hv(x_{k-1}) \}

i.e. k time steps of Euler’s method applied to v(x). The free category on this span has morphisms given by the coproduct of all these sets so we have that:

F(A) is a category where

  • objects are elements \mathbf{x} \in \mathbb{R}^n and,
  • a morphism from \mathbf{x} to \mathbf{y} is tuple (x=x_1, \ldots, y=x_k) which is an approximate solution to \frac{d\mathbf{x}}{dt} = v(\mathbf{x}) using Euler’s method with step size h.

Thank you for reading!

Matrices Are Enriched Profunctors

Let (R,+,*) be a ring equipped with a poset structure that is nice enough to enrich in. For concreteness say that R is a quantale. A quantale is a monoidal closed poset with all colimits (the coproduct is the + and the monoidal product is the *)

This post will sketch a proof that there is an embedding of categories

i : \mathsf{Mat_R} \hookrightarrow \mathsf{RProf}

The category \mathsf{Mat_R} has

  • natural numbers n,m \in \mathbb{N} as objects,
  • a morphism M: n \to m is an m \times n matrix valued in R and,
  • composition is given by matrix multiplication.

The category \mathsf{RProf} has

  • R-enriched categories C,D as objects,
  • a morphism D : C  \to D is a R-enriched profunctor C \times D^{op} \to R and,
  • composition is given by profunctor composition.

The embedding i definitely isn’t new. I am guessing that it was mentioned as an offhand remark by someone like Lawvere. Simon Wilerton wrote a blog post talking about it. Regardless, it is one of my favorite category theoretic facts, which isn’t the most well-known, so I thought I would make a blog post fleshing out some of the details I haven’t seen elsewhere.

the definition of i

A natural number n is sent to the discrete R-category on n elements i(n). This is the R-category whose objects are given by your favorite n-element set and whose hom objects are all given by 0 (the zero element of your ring).

A matrix M: n \to m is sent to a an R-profunctor

i(M) : i(n) \times i(m) \to R

Note that because i(n) and i(m) are discrete, every function of this type on objects extends to a unique R-enriched functor. Also note that the opposite of a discrete R-category is itself, so there no need for an “op” in this profunctor. The values i(M)(x,y) are given by the matrix components M_{xy}.

proof that i is a functor

The composite of a matrix M : n \to m with a matrix N: m \to l has components given by

(N \circ M)_{ij} = \sum_{k \leq m} N_{ik} * M_{kj}

The composite of a R-profunctor A: X \to Y with an R-profunctor B: Y \to Z has values given by the coend formula

A \circ B (x,y) = \int_{k \in Y} A(x,k) * B(k,y)

Because R is a poset, the coend turns into coproduct and

i(N) \circ i(M) (x,y) = \sum_{k \leq  m} i(M)(x,k) * i(N)(k,y) = \sum_{k \leq m} N_{xk}*M_{ky}

so i preserves composition. The identity matrix I: n \to n gets sent to the R-profunctor with values i(I)(x,y) given by 1 if x=y and 0 otherwise. For a profunctor A: i(n) \to C we have that

A \circ i(I) (x,y) = \sum_{k \leq n} A_{xk} * i(I)_{ky} = A_{xy}

because all of the other entries in the sum are 0. Therefore i respects identities on the right and a similar argument holds for composition on the left.

proof that i is an embedding

By embedding I mean that i is fully faithful and injective on objects.

  • i is injective on objects: if i(n)=i(m) then n must have equaled m in the first place.
  • i is faithful: if M : n \to m and M': n \to m are matrices with i(M)=i(M') then they have the same components, and must have been equal to begin with.

It remains to show that i is full. If D: i(n) \times i(m) \to R is an R-profunctor, then because i(n) and i(m) are discrete, D is uniquely determined by its value on objects i.e. by an underlying R-matrix.

Thank you for reading.

Marked Petri Nets via the Grothendieck Construction

I started this blog with the goal of applying the Grothendieck construction to everything in sight. The idea was that more often than not, if you can take a functor and interpret it as a functor into \mathsf{Cat}, then the Grothendieck construction of that functor is an interesting category worthy of time and consideration.

With this in mind it seems obscene that I haven’t yet turned this blog onto my PhD research. This post intends to fix that omission. In this post I will take the Grothendieck construction of the operational semantics functor

F : \mathsf{Petri} \to \mathsf{CMC}

where \mathsf{CMC} is the category of commutative monoidal categories. The Grothendieck construction \int F is a category whose objects are marked Petri nets, a popular and practical variant of Petri nets.


Categorical Operational Semantics of Petri Nets

The operation of a Petri net is shown in the following gif:

Animated_Petri_net_commons

The circles are called places and the rectangles are called transitions. Specific instances of each place are called tokens and denoted by the black dots. The transitions can fire, and output a token for every arrow going out of it and consume a token for every arrow going into it. The operational semantics of a Petri net aims to formalize and reason about the sequences of firings which can occur within a Petri net.

The idea introduced by Messeguer and Montanari in Petri Nets are Monoids was that these firings can be modeled by categories. For a Petri net P, its categorical operational semantics is a category FP whose objects represent configurations of tokens (markings) and whose morphisms represent sequences of firings. Nailing down the details of this category is a matter of debate, and there are different constructions suited for different purposes. However, in this post we will use an operational semantics which is very mathematically natural, with the understanding that marked Petri nets can also be obtained with the Grothendieck construction if another form of categorical operational semantics is chosen. This operational semantics can be defined inductively.


Definition: For a Petri net P= s,t :T \to \mathbb{N}[S], its categorical operational semantics is a category FP where

  • objects are multisets of places i.e. elements of the free commutative monoid \mathbb{N}[S] and,
  • morphisms are generated inductively by the following rules:
    • Every transition \tau \in T becomes a morphism \tau : s(\tau) \to t(\tau).
    • Every marking m \in \mathbb{N}[S] is equipped with an identity morphism 1_m: m \to m.
    • For every pair of morphisms f : x \to y and g : y \to z there is a formal composite g \circ f : x \to z.
    • For every pair of morphisms f : x \to y and f' : x' \to y' there is a formal sum f +f' : x +x' \to y+y'.
  • These morphisms are quotiented to:
    • satisfy the axioms of a category on \circ (unitality, associativity),
    • the axioms of a commutative monoid on + (associativity, commutativity, unitality) and,
    • axioms expressing compatability between these two operations. + must be a functor and the functions of composition, source, target, and identity assignment must be monoid homomorphisms.

This construction is extended to a functor

F : \mathsf{Petri} \to \mathsf{CMC}

where \mathsf{CMC} is the category of commutative monoidal categories i.e. commutative monoid objects in the category of categories.  For a morphism of Petri nets (f,g) : P \to Q, the functor F(f,g) : FP \to FQ is given by \mathbb{N}[g] on objects and by the unique functorial and strict monoidal extension of f to formal composites and sums of transitions.


This functor is a left adjoint, justifying the statement that Petri nets are the generating data for commutative monoidal categories. To see a more in depth discussion of this left adjoint see Section 2 of Open Petri Nets To learn more about this left adjoint and get a deeper sense about how it works, check out my paper Generalized Petri Nets.


Let’s Grothendieck It

F : \mathsf{Petri} \to \mathsf{CMC} can be regarded as a functor into \mathsf{Cat} by forgetting that each commutative monoidal category has the structure of a commutative monoid. In other words, there is a forgetful functor G: \mathsf{CMC} \to \mathsf{Cat} which does nothing except regard commutative monoidal categories as ordinary categories and commutative monoidal functors as ordinary functors. Composition gives a functor \mathbf{F}: = G \circ F that we can Grothendieck.

The Grothendieck construction \int \mathbf{F} has

  • objects given by pairs (P, m) where P is a Petri net and m \in \mathrm{Ob }FP is a marking of P.
  • A morphism from (P,m) to (Q,n) is a pair ((f,g),\tau) where
    • (f,g) : P \to Q is a morphism of Petri nets and,
    • \tau : \mathbb{N}[g](m) \to n is a firing sequence in Q i.e. a morphism in FQ.
  • For morphism ((f,g),\tau): (P,m)  \to (Q,n) and ((h,k),\rho): (Q,n) \to (R,l) their composite is given by

((h \circ f, k\circ g), \rho \circ F(h,k) (\tau)): (P,m) \to (R,l).

In words, composition in \int \mathbf{F} composes the morphisms of Petri nets and maps \tau into the category FR so it can be composed with the firing sequence \rho.

An object in this category is exactly a marked Petri net. Usually a morphism from a marked Petri net (P,m) to a marked Petri net (Q,n) is defined to be a morphism of Petri nets (f,g) : P \to Q which preserves the marking on the nose i.e. \mathbb{N}[g](m) = n (see for example Definition 10 of Petri Nets are Monoids). In this Grothendieck construction, morphisms are allowed a bit more flexibility. Now a morphism of marked Petri nets is a morphism of the underlying Petri nets (f,g) along with a transition which allows the image of m under \mathbb{N}[g] to evolve into n.

In particular for a morphism ((f,g),\tau) : (P,m) \to (Q,n),

  • restricting (f,g) to be the identity gives morphisms which are firing sequences of your Petri net.
  • Restricting \tau to be the identity gives morphisms which only change the structure of your Petri net.
  • Allowing both (f,g) and \tau to be non-trivial allows for morphisms which do both of these things at once.

Some remarks:

  • The full Grothendieck construction gives an opfibration

\int \mathbf{F} \to \mathsf{Petri}

which sends a marked Petri net to its underlying Petri net. This is comforting as it is a functor you would expect to exist.

  • In Low- and High-Level Petri Nets with Individual Tokens, the authors discuss how transformation rules of marked Petri nets can allow for reasoning about systems in an adaptive way. A transformation rule for marked Petri nets gives a rule which changes the structure and behavior of a Petri net at the same time. In this way, the structure of Petri net can be altered in order to produce a desired firing sequence in the modified net.  The existence of a sound rewriting system for marked Petri nets and relies on the category of marked Petri nets being nice enough (for a very technical definition of nice). The linked paper shows that marked Petri nets are in general not nice enough unless an operational semantics is chosen which keeps track of the identities of tokens. It seems plausible to me with a different choice of operational semantics than the one given here, we could recreate this category of nice marked Petri nets using the Grothendieck construction. If you know about this stuff and would like to talk about it let me know.

Thanks for reading! Next time we will use the the monoidal Grothendieck construction to construct various tensor products of marked Petri nets.

 

 

 

 

 

Let’s Grothendieck Dynamical Systems

In week 3 we described the fundamental groupoid functor

\pi_1 \colon \mathsf{Top} \to \mathsf{Grpd}

which sends a topological space X to the groupoid where objects are points in X and morphisms are equivalence classes of paths.

There is a similar story for directed topological spaces; spaces equipped with a set of paths closed under concatenation, subpaths, and constant paths. Each directed topological space generates a fundamental category where the objects are the points of your directed topological space and the morphisms are given by the set of paths. In particular, every dynamical system gives a directed topological space. I won’t describe the fundamental category functor in full generality but instead describe it as a functor from the category of dynamical systems.

Last time we constructed the category \mathsf{Dynam} of dynamical systems as the \mathsf{Diff}-enriched functor category

\mathsf{Diff}^{\mathbb{R}}

where \mathsf{Diff} is the category of diffeological spaces and \mathbb{R} is the \mathsf{Diff} enriched category with one object denoted by \mathbf{\cdot} and every real number as a morphism. If you’re scared by the enrichment it might help to note that \mathsf{Diff}-functors are standard functors except that the morphisms are mapped in a smooth way and \mathsf{Diff}-natural transformations are just ordinary natural transformations.

\uparrow \Pi_1 \colon \mathsf{Dynam} \to \mathsf{Cat}

is the functor which sends a dynamical system \phi \colon \mathbb{R} \to \mathsf{Diff} to the category where

  • objects are given by the points of \phi(\mathbf{\cdot}) i.e. the points of the manifold which the dynamical systems lives and,
  • there is a morphism t\colon x \to y if the flow of \phi sends x to y after time t. That is there exists some t \in \mathbb{R} such that \phi(t)(x) = y.
  • Composition is given by concatenation. For a morphism t \colon x \to y and a morphism t' \colon y \to z there is a morphism t' \circ t \colon x \to z because \phi(t+t')(x) = \phi(t')(\phi(t,x)) = \phi(t', y) = z.
  • The identity morphism for x is given by 0 \colon x \to x because \phi(0,x) = x.

For a morphism of dynamical systems i.e. a natural transformation \alpha \colon \phi \Rightarrow \psi there is a functor

\uparrow \Pi_1 (\alpha) \colon \uparrow \Pi_1 (\phi) \to \uparrow \Pi_1 (\psi)

which sends

  • an object x \in \uparrow \Pi_1 (\phi) to the object \alpha_{\mathbf{\cdot}} (x) \in \uparrow \Pi_1 (\psi) and,
  • a morphism t \colon x \to y \in \uparrow \Pi_1 (\phi) to the morphism t \colon \alpha_{\mathbf{\cdot}} (x) \to \alpha_{\mathbf{\cdot}} (y). This is well defined because \alpha is a natural transformation.

You may notice that this is more than a category, it’s a groupoid because every morphism t \colon x \to y has an inverse -t \colon y \to x. It may seem odd to you to call this the fundamental category functor. The reason for this is that it is a restriction of a more general functor which maps directed topological spaces to categories with not-neccesarily invertible morphisms.

What happens next is in the title.

The Grothendieck construction of \uparrow \Pi_1  \colon \mathsf{Dynam} \to \mathsf{Cat} is a category \int \uparrow \Pi_1 where

  • objects are pairs (\phi, x) where \phi \colon \mathbb{R} \to \mathsf{Diff} is a dynamical system and x is a point in its manifold.
  • A morphism from (\phi, x) to (\psi, y) is a tuple (\alpha \colon \phi \Rightarrow \psi, t \colon \alpha_{\cdot} (x) \to y) where \alpha is a morhpism of dynamical systems and t is a morphism in \uparrow \Pi_1 (\psi). In words, a morphism from (\phi,x) to (\psi,y) is a morphism of dynamical systems along with a flow t from the image of x to y.

There are two interesting interpretations of this category. In week 3 we performed a similar Grothendieck construction of the fundamental groupoid functor. This gave a category where the objects are pointed topological spaces and the morphisms are continuous maps which preserve the basepoint up to an invertible path.  The category \int \uparrow \Pi_1 has a similar interpretation as pointed dynamical systems. The morphisms in \int \uparrow \Pi_1 are morphisms of dynamical systems which preserve the basepoint up to a flow.

The second interpretation is as the category of solutions to an intial value problems. An object (\phi,x) \in \int \uparrow \Pi_1 is a dynamical system equipped with an initial condition. The flow of \phi starting from this intial condition gives the solution to your differential equation with initial condition x. A morphism (\alpha, t) can be interpreted physically as well.  This is a smooth map between the underlying manifolds such that flow of \phi starting at x matches the flow of \psi starting at y after some time t.

 

Dynamical Systems with Category Theory? Yes!

Sadly, this post is not about the Grothendieck construction. However, it will lay the groundwork for a Grothendieck construction in the future. This post is about understanding dynamical systems from the point of view of category theory.

Topologists love convenient categories. But you may have not know that dynamical systemists (?) often desire convenience as well. In Convienent Categories of Smooth Spaces Baez and Hoffnung tweak the definition of smooth manifold to make the category \mathsf{Diff} of diffeological spaces. The key difference between manifolds and diffeological spaces is that manifolds have charts which go from your manifold to an open subset of \mathbb{R}^n and diffeological spaces have plots which go in the opposite direction; from an open subset of \mathbb{R}^n to your diffeological space. This category has lots of conveniences but the one that I’m most interested in is the existence of an internal “hom”. This means the following fact:

For two diffeological spaces M and M', the set of smooth maps \mathsf{Diff} ( M , M') is naturally equipped with the structure of a diffeological space.

I don’t plan to go into the details of diffeological spaces but for the purposes of this post you can think of them as smooth manifolds which can possibly have infinite dimension. Indeed there is a nice fully faithful embedding of the category of smooth manifolds into \mathsf{Diff}.

Okay now let’s get moving with dynamical systems (sorry).

A dynamical system is roughly the solution to a system of ordinary differential equations. A slick definition is the following:

Definition: A dynamical system or flow on a manifold M is a group homomorphism

\phi : (\mathbb{R}, + ) \to \mathrm{Aut}(M)

where \mathrm{Aut}(M) is the group of diffeomorphisms from M to itself.  The idea is that your system of ordinary differential equations is given by some vector field on M. For a given time t, \phi(t) calculates a new position, on all points of your manifold at once, in the direction of your vector field after t elapses. You want the flow to have several nice properties.

  • For every t, \phi(t) should be a diffeomorphism
  • Advancing for time t and then advancing for time t' should be the same as advancing for time t+t'. This means,

\phi(t +t') = \phi(t') \circ \phi(t)

  • Advancing for no amount of time should be the identity function on M. This means

\phi(0) = 1_M

These conditions can be succinctly described by the definition above!

If you’re a sneaky category theorist you may have heard of the following fact:

Proposition: Let M be an object in a category C and let \mathrm{Aut} (M) be the group of isomorphisms of M. Then a group homomorphism \phi : G \to \mathrm{Aut} (M) specifies a unique functor

\phi : G \to C

where G is regarded as one object category with the group elements as morphisms and \phi sends the unique object of G to M.

Proving this is a fun exercise if you haven’t seen it before. The idea is that the homomorphism property means that the assignment given by \phi preserves composition. Because homomorphisms preserve identities and composition the morphisms in the image of \phi must all be isomorphisms.

So far we have that a functor \phi : \mathbb{R} \to \mathsf{Diff} characterizes the data of a dynamical system…except for the requirement that \phi is smooth. To capture this we can use enrichment.

Proposition: A dynamical system is a \mathsf{Diff}-enriched functor

\phi : \mathbb{R} \to \mathsf{Diff}

Proof: Like most proofs in category theory, this proof relies on unpacking the definitions and seeing that the claim is true. First we need to understand how \mathbb{R} and \mathsf{Diff} are \mathsf{Diff}-enriched categories. There is only one hom-set in \mathbb{R} and it’s given by the real numbers. This is one of nicest examples of diffeological spaces. Because the set of smooth maps between diffeological spaces is again diffeological space, \mathsf{Diff} is enriched in itself.

A \mathsf{Diff}-enriched functor F : C \to  D consists of a smooth map \mathrm{Hom} (x,y) \to \mathrm{Hom} (Fx, Fy) for every pair of objects x and y in C. Because there is only one pair of objects in \mathbb{R} we get just one smooth map. The axiom requiring that \phi respects composition and the axiom requiring that \phi preserves identities (found here) are equivalent to \phi being a group homomorphism.

Dynamical system theorists are interested in comparing dynamical systems. For this they invented the idea of topological conjugacy.

Definition: Let \phi and \phi' be dynamical systems on manifolds M and M' respectively. Then a topological conjugacy from \phi to \phi' is continuous map

f : M \to M'

such that the following diagram commutes

nat2

The idea is that topological conjugacies should “send flows to flows”. The commutative diagram says that if you advance \phi' for time t and then change the manifold you’re interested in, this is the same as first changing the manifold you’re interested in and then advancing \phi' forward by time t.

Thinking of \phi : \mathbb{R} \to \mathsf{Diff} and \phi : \mathbb{R} \to \mathsf{Diff} as \mathsf{Diff}-functors the above diagram gives that f is the unique component of a natural transformation between \phi and \phi'. This motivates the following definition:

Definition: Let \mathsf{Dynam} be the category

\mathsf{Diff}^{\mathbb{R}}

i.e. the category where

  • objects are functors \phi : \mathbb{R} \to \mathsf{Diff} and
  • morphisms are natural transformations f : \phi(\cdot) \to \phi'(\cdot).

Because \mathsf{Dynam} is a functor category and \mathsf{Diff} is nice we get lots of things for free.

Corollary: (yes to a definition) \mathsf{Dynam} has finite colimits, finite limits, and is cartesian closed.

\mathsf{Dynam} inherits all the niceness from \mathsf{Diff} as described in this nLab article. A fun (?) exercise is to see what the limits and colimits in \mathsf{Dynam} are like by computing some examples.

 

Let’s Grothendieck Everything In Sight (Week 5)

Last time I talked about how to get some notion of a topological space pointed by an n-dimensional hole. However, this construction wasn’t entirely satisfactory to me because the category was too connected.

Here’s what I mean by that:

Consider the disjoint union S^1 +S^1, the identity function \mathrm{id}: S^1 + S^1 \to S^1 +S^1, and let the the generators of H_1(S^1+S^1) be labeled by a and b.  Then, there is a map from (id, b-a): (S^1+S^1, a) \to (S^1+S^1,b) even though they live in different path components. This doesn’t match my intuition about what pointing a space should mean. A pointed space should specify a subset of your topological space which you care about and morphisms between these pointed spaces should preserve that subset. This is not the case for the morphism (id, b-a) because the continuous map id sends the subspace corresponding to a to a instead of b which lives in a different path component.

To fix this problem we will have to do homology the “right”* way; using simplicial sets. This is something I learned recently in John Baez’s class. You can find notes from this class here. Emily Riehl also has a nice introduction to the subject.

Definition: Let \Delta be the category of  non-empty finite ordinals and order preserving maps. This is called the simplex category and its objects can be thought of as  the following sequence of shapes: dot, line segment, triangle, tetrahedron, etc. These are called simplices.

A simplicial set is a functor F: \Delta^{op} \to \mathsf{Set}. The order preserving functions in \Delta^{op} describe which simplices are faces of each other. So a simplicial set assigns to each basic shape a set of things which have that shape and to each face map a function encoding which of these things are faces of each other. The sum of this data is meant to describe a topological space which is pieced together using simplices. Compositionality is all the rage right now and a nice way to think of simplical sets is as a compositional approach to topology; topological spaces are built from simpler, better understood spaces. Elegantly, morphisms between simplicial sets are natural transformations. The category where objects are simplicial sets and and morphisms are natural transformations is denoted \mathsf{sSet}.

Simplicial sets are functors…but I’d like them to be categories. If only there were some way to turn a functor into a category?

For a simplicial set F: \Delta^{op} \to \mathsf{Set}, it’s Grothendieck construction \int F is a category with the following data:

  • Objects are tuples ([n], K) where n is a finite ordinal and K is an element of F([n]) i.e. an n-dimensional simplex
  • A morphism f: ([n], K) \to ([m],L) is a morphism f \in \Delta^{op} such that F(f)(K) =L. Note that because F is a functor into \mathsf{Set} the morphism components don’t have any contribution from the fibres.

We can think of the Grothendieck construction as a way to pack up a simplicial set into one category where the objects are specific instances of simplices and the morphisms encode specific instances of their boundary. This category is a way to get the actual space that your simplicial set is describing rather than presenting it in pieces.

Given a topological space we can always turn it into a simplical set. Every object [n] \in \Delta^{op} can be realized as a topological space: [1] gives a point called \Delta_1, [2] gives an interval called \Delta_2, [3] gives a triangle called \Delta_3 and so on ad infinitum. We can use these geometric realizations to probe a topological space in the following way.

For a topological space X, we can form a simplicial set S(X) : \Delta^{op} \to \mathsf{Set} called the singular simplicial set of X. S(X) sends a non-empty ordinal [n] to the set \mathrm{Hom}_{\mathsf{Top}} (\Delta_n, X). and morphism f: [n] \to [m] in \Delta^{op} to the function

S(X)(f) : \mathrm{Hom}_{\mathsf{Top}} (\Delta_n, X) \to \mathrm{Hom}_{\mathsf{Top}} (\Delta_m, X)

given by pre-composition with f. Normally this map would go in the other direction because it is built using the contravariant hom-functor. However, because we are using \Delta^{op} rather than \Delta we get a map defined covariantly. S extends to a functor

S: \mathsf{Top} \to \mathsf{sSet}

which sends a continous map

f: X \to Y

to the natural transformation between simplicial sets given by post-composition. For an ordinal [n] we have a map S(f)_n: \mathrm{Hom}_{\mathsf{Top}} (\Delta_n, X) \to \mathrm{Hom}_{\mathsf{Top}} (\Delta_n, Y) which sends a map a: \Delta_n \to X to the composite f \circ a: \Delta_n \to Y. These maps are the components of a natural transformation S(f): S(X) \to S(Y).

We can compose S with \int to get a functor

\mathbb{S} = \int \circ S : \mathsf{Top} \to \mathsf{Cat}

Now let’s integrate this! A meta-Grothendieck construction if you will.

\int \mathbb{S} is a category where

  • an object is a pair (X, K) where X is a topological space and K an n-dimensional simplex in the singular simplical set of X. Recall that these elements are maps \Delta_n \to X so we can think of K as the realization of some n-dimensional simplex inside of X.
  • A morphism (f, d): (X,K) \to (Y,L) is a continuous function f: X \to Y and a map d: \int \circ S (f) (K) \to L in \int \circ S (Y). Let’s unpack this. f induces a map from\int \circ S(X) \to \int \circ S (Y) given by composition and the morphisms in \int \circ S (Y) encode the boundaries and gluings of our simplices.  So first we turn the simplex K into a simplex of Y using f and then include it in another simplex or take a boundary to get the simplex L.

Now objects in \int \mathbb{S} have the property I want from pointed objects. If K is a singular simplex of X and f maps K to a simplex K' of Y then L must either be the boundary of K' or vice versa in order to get a map (X, K) to (Y,L) in \int \mathbb{S}. You can think of morphisms in this category as continuous maps which preserve a simplex up to a boundary or inclusion.

Another reason why \int \mathbb{S} is better than last week’s is that includes n-dimensional data for every n whereas the previous category only knew about a fixed dimension n. Simplicial sets (with some extra properties) give models of (\infty, 1)-groupoids called quasi-categories. With this in mind, the category \int F may help you get a notion of pointed (\infty,1)-groupoids – whatever that means – maybe one of you can help me figure that out.

Open ended question: In the category of pointed topological spaces, there is a nice coproduct called the wedge sum, which takes the disjoint union of two topological spaces and identifies their points together. Define a similar construction in \int F which identifies entire n-simplices together. Is this a coproduct?

*Here “right” is defined to mean “using category theory”