The Monoidal Grothendieck Construction

24 April, 2020

My student Joe Moeller gave a talk at the MIT Categories Seminar today! People discussed his talk at the Category Theory Community Server, and if you join that you can see the discussion here:

https://categorytheory.zulipchat.com/#narrow/stream/229457-MIT-Categories.20Seminar/topic/April.2023.20-.20Joe.20Moeller’s.20talk

You can see his slides here, and watch a video of his talk here:

The monoidal Grothendieck construction

Abstract. The Grothendieck construction gives an equivalence between fibrations and indexed categories. We will begin with a review of the classical story. We will then lift this correspondence to two monoidal variants, a global version and a fibre-wise version. Under certain conditions these are equivalent, so one can transfer fibre-wise monoidal structures to the total category. We will give some examples demonstrating the utility of this construction in applied category theory and categorical algebra.

The talk is based on this paper:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

This, in turn, had its roots in our work on network models, a setup for the compositional design of networked systems:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models.

Star-Autonomous Envelopes

21 April, 2020

In the fourth talk of the ACT@UCR seminar, Michael Shulman told us how to create nice string diagams for any closed symmetric monoidal category.

Mike had to teach right after his talk, but he rejoined us for discussions later at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2022nd.3A.20Michael.20Shulman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video of his talk here, or watch the video here:

• April 22, Michael Shulman, Star-autonomous envelopes.

Abstract. Symmetric monoidal categories with duals, a.k.a. compact monoidal categories, have a pleasing string diagram calculus. In particular, any compact monoidal category is closed with [A,B] = (A* ⊗ B), and the transpose of A ⊗ B → C to A → [B,C] is represented by simply bending a string. Unfortunately, a closed symmetric monoidal category cannot even be embedded fully-faithfully into a compact one unless it is traced; and while string diagram calculi for closed monoidal categories have been proposed, they are more complicated, e.g. with “clasps” and “bubbles”. In this talk we obtain a string diagram calculus for closed symmetric monoidal categories that looks almost like the compact case, by fully embedding any such category in a star-autonomous one (via a functor that preserves the closed structure) and using the known string diagram calculus for star-autonomous categories. No knowledge of star-autonomous categories will be assumed.

His talk is based on this paper:

• Michael Shulman, Star-autonomous envelopes.

This subject is especially interesting to me since Mike Stay and I introduced string diagrams for closed monoidal categories in a somewhat ad hoc way in our Rosetta Stone paper—but the resulting diagrams required clasps and bubbles:

This is the string diagram for beta reduction in the cartesian closed category coming from the lambda calculus.

Structured Cospans and Petri Nets

6 April, 2020

$\;$

This talk on structured cospans and Petri nets is the second of a two-part series, but it should be understandable on its own. The first part is on structured cospans and double categories.

I gave this second talk at the MIT Categories Seminar. People discussed the talk at the Category Theory Community Server.

You can see the slides here and watch a video here:

Structured cospans and Petri nets

Abstract. “Structured cospans” are a general way to study networks with inputs and outputs. Here we illustrate this using a type of network popular in theoretical computer science: Petri nets. An “open” Petri net is one with certain places designated as inputs and outputs. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Using the formalism of structured cospans, open Petri nets can be treated as morphisms of a symmetric monoidal category—or better, a symmetric monoidal double category. We explain two forms of semantics for open Petri nets using symmetric monoidal double functors out of this double category. The first, an operational semantics, gives for each open Petri net a category whose morphisms are the processes that this net can carry out. The second, a “reachability” semantics, simply says what these processes can accomplish. This is joint work with Kenny Courser and Jade Master.

The talk is based on these papers:

• John Baez and Kenny Courser, Structured cospans.

• John Baez and Jade Master, Open Petri nets.

• Jade Master, Generalized Petri nets.

I’ve blogged about open Petri nets before, and these articles might be a good way to start learning about them:

Part 1: the double category of open Petri nets.

Part 2: the reachability semantics for open Petri nets.

Part 3: the free symmetric monoidal category on a Petri net.

Structured Cospans and Double Categories

31 March, 2020

$\; \phantom{a}$

This talk on structured cospans and double categories is the first of a two-part series; the second part is about structured cospans and Petri nets.

I gave the first talk at the ACT@UCR seminar, on Wednesday April 1st. Afterwards we discussed it on the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.201st.3A.20John.20Baez

You can view or join the conversation there if you sign in.

You can see my slides here, or download a video here, or watch the video here:

Abstract. One goal of applied category theory is to better understand networks appearing throughout science and engineering. Here we introduce “structured cospans” as a way to study networks with inputs and outputs. Given a functor L: A → X, a structured cospan is a diagram in X of the form

If A and X have finite colimits and L is a left adjoint, we obtain a symmetric monoidal category whose objects are those of A and whose morphisms are certain equivalence classes of structured cospans. However, this arises from a more fundamental structure: a symmetric monoidal double category where the horizontal 1-cells are structured cospans, not equivalence classes thereof. We explain the mathematics and illustrate it with an example from epidemiology.

This talk was based on work with Kenny Courser and Christina Vasilakopoulou, some of which appears here:

• John Baez and Kenny Courser, Structured cospans.

• Kenny Courser, Open Systems: a Double Categorical Perspective.

Yesterday Rongmin Lu told me something amazing: structured cospans were invented in 2007 by José Luiz Fiadeiro and Vincent Schmit. It’s pretty common for simple ideas to be discovered several times. The amazing thing is that these other authors also called these things ‘structured cospans’!

• José Luiz Fiadeiro and Vincent Schmitt, Structured co-spans: an algebra of interaction protocols, in International Conference on Algebra and Coalgebra in Computer Science, Springer, Berlin, 2007.

These earlier authors did not do everything we’ve done, so I’m not upset. Their work proves I chose the right name.

Applied Category Theory 2020 (Part 2)

23 March, 2020

Due to the coronavirus outbreak, many universities are moving activities online. This is a great opportunity to open up ACT2020 to a broader audience, with speakers from around the world.

The conference will take place July 6-10 online, coordinated by organizers in Boston USA. Each day there will be around six hours of live talks, which will be a bit more spaced out than usual to accommodate the different time zones of our speakers. All the talks will be both live streamed and recorded on YouTube. We will also have chat rooms and video chats in which participants can discuss various themes in applied category theory.

We will give more details as they become available and post updates on our official webpage:

http://act2020.mit.edu

Since there is no need to book travel, we were able to postpone the acceptance notification, and hence the submission deadline. If you would like to speak, please prepare an abstract or a conference paper according to the instructions here:

http://act2020.mit.edu/#papers

Important dates (all in 2020)

• Submission of contributed papers: May 10
• Tutorial day: July 5
• Main conference: July 6-10

Registration will now be free; please register for the conference ahead of time here:

http://act2020.mit.edu/#registration

We will send registering participants links to the live stream, the recordings, and the chat rooms, and we’ll use the list to inform participants of any changes.

Submissions

To give a talk at ACT2020, you have to submit a paper. You can submit either original research papers or extended abstracts of work submitted/accepted/published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume.

Here’s how to submit papers. Two types of submissions are accepted, which will be reviewed to the same standards:

Proceedings Track. Original contributions of high quality work consisting of a 5–12 page extended abstract that provides evidence for results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submissions of works in progress are encouraged, but must be more substantial than a research proposal.

Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure these pages contain sufficient evidence of the quality and rigor of your work.

Submissions should be prepared using LaTeX, and must be submitted in PDF format. Submission is currently open, and can be perfomed at the following web page:

https://easychair.org/conferences/?conf=act2020

One or more best paper awards may be given out at the discretion of the PC chairs. Selected contributions will be offered extended keynote slots in the program.

Organizers

Here are the local organizers:

• Brendan Fong
• David Jaz Myers (logistics)
• Paolo Perrone (publicity)
• David Spivak

Here is the committee running the school:

• Carmen Constantin
• Eliana Lorch
• Paolo Perrone

Here is the steering committee:

• John Baez
• Bob Coecke
• David Spivak
• Christina Vasilakopoulou

Here is the program committee:

• Mathieu Anel, CMU
• John Baez, University of California, Riverside
• Richard Blute, University of Ottawa
• Tai-Danae Bradley, City University of New York
• Andrea Censi, ETC Zurich
• Bob Coecke, University of Oxford
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Ross Duncan, University of Strathclyde
• Eric Finster, University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Richard Garner, Macquarie University
• Fabrizio Romano Genovese, Statebox
• Amar Hadzihasanovic, IRIF, Université de Paris
• Helle Hvid Hansen, Delft University of Technology
• Jules Hedges, Max Planck Institute for Mathematics in the Sciences
• Kathryn Hess Bellwald, Ecole Polytechnique Fédérale de Lausanne
• Chris Heunen, The University of Edinburgh
• Joachim Kock, UAB
• Tom Leinster, The University of Edinburgh
• Martha Lewis, University of Amsterdam
• Daniel R. Licata, Wesleyan University
• David Jaz Myers, Johns Hopkins University
• Paolo Perrone, MIT
• Vaughan Pratt, Stanford University
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
David I. Spivak, MIT (co-chair)
• Walter Tholen, York University
• Todd Trimble, Western Connecticut State University
Jamie Vicary, University of Birmingham (co-chair)
• Maaike Zwart, University of Oxford

Applied Category Theory at NIST (Part 3)

22 February, 2020

Sadly, this workshop has been cancelled due to the coronavirus pandemic. It may be postponed to a later date.

My former student Blake Pollard is working at the National Institute of Standards and Technology. He’s working with Spencer Breiner and Eswaran Subrahmanian, who are big advocates of using category theory to organize design and manufacturing processes. In the spring of 2018 they had a workshop on applied category theory with a lot of honchos from industry and government in attendance—you can see videos by clicking the link.

This spring they’re having another workshop on this topic!

Applied Category Theory Workshop, April 8-9, 2020, National Institute of Standards and Technology, Gaithersburg, Maryland. Organized by Spencer Breiner, Blake Pollard and Eswaran Subrahmanian.

The focus of this workshop in on fostering the development of tooling and use-cases supporting the applied category theory community. We are particularly interested in bringing together practitioners who are engaged with susceptible domains as well as those involved in the implementation, support, and utilization of software and other tools. There will be a number of talks/demos showcasing existing approaches as well as ample time for discussion.

Here are the speakers listed so far:

• John Baez, University of California, Riverside

• Arquimedes Canedo, Siemens

• Daniel Cicala, New Haven University

• James Fairbanks, Georgia Tech Research Institute

• Jules Hedges, Max Planck Institute for the Mathematical Sciences

• Jelle Herold, Statebox

• Evan Patterson, Stanford University

• Qunfen Qi, University of Huddersfield

• Christian Williams, University of California, Riverside

• Ryan Wisnesky, Conexus.ai

I’ll also be giving a separate talk on “ecotechnology” at NIST on Friday April 10th; more about that later!

Applied Category Theory 2020 — Adjoint School

23 December, 2019

Like last year and the year before, there will be a school associated to this year’s international conference on applied category theory! If you’re trying to get into applied category theory, this is the best possible way.

The school will consist of online meetings from February to June 2020, followed by a research week June 29–July 3, 2020 at MIT in Cambridge Massachusetts. The conference follows on July 6–10, 2020, and if you attend the school you should also go to the conference.

The deadline to apply is January 15 2020; apply here.

There will be 4 mentors teaching courses at the school:

• Michael Johnson, Categories of maintainable relations.

• Valeria de Paiva, Dialectica categories of Petri nets.

• Michael Shulman, A practical type theory for symmetric monoidal categories.

Click on the links for more detailed information!

Who should apply?

Anyone, from anywhere in the world, who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example—is encouraged.

We will consider advanced undergraduates, PhD students, post-docs, as well as people working outside of academia. Members of minorities, and of any groups which are underrepresented in the mathematics and computer science communities, are especially encouraged to apply.

Structure of the school

Every participant will be assigned to one of the groups above, according to their preference (and to the availability of places within the groups). Each group will consist of a mentor, a TA, and 4-5 students.

Online meetings

Between February and June 2020 there will be an online reading seminar. Each group will have a reading list of two papers, which they will study, and then present to the rest of the school during weekly online meetings. Every member of the school is encouraged to take part in the discussion of every paper, first during the meeting via live chat, and then, in written form, on an online forum. After the presentation and the forum discussion the students of each group will write a blog post about their assigned paper on the n-Category Café.

During this period, the TAs will be there to help the students, answer any question they might have, and moderate the discussions. This way, all the participants will build the necessary background to take part in the research activities during the week at MIT.

Research week

After the online meetings, there will be a two-week event at MIT, from June 29th to July 10th 2020. The first week is dedicated exclusively to the participants of the school. They will work in groups on the research projects outlined above, led by their mentors, with the help of their TAs.

During the second week the ACT 2020 Conference will take place, which is open to a wider audience. The member of each group of the school will have the possibility to present their activity to the audience of the conference, and share their ideas. The conference is not technically part of the school, but is about very similar topics, and participation is very much encouraged. The online meetings should prepare students to be able to follow some of the conference presentations to a reasonable degree, and introduce them to the main problems and techniques of the field.

Questions?

For any questions or doubts please write us at the address act adjoint school at gmail dot com.

Applied Category Theory Meeting at UCR (Part 3)

15 November, 2019

We had a special session on applied category theory here at UCR:

Applied category theory, Fall Western Sectional Meeting of the AMS, 9–10 November 2019, U.C. Riverside.

I was bowled over by the large number of cool ideas. I’ll have to blog about some of them. A bunch of people stayed for a few days afterwards, and we had lots of great conversations.

The biggest news was that Brendan Fong and David Spivak definitely want to set up an applied category theory in the San Francisco Bay Area, which they’re calling the Topos Institute. They are now in the process of raising funds for this institute! I plan to be involved, so I’ll be saying more about this later.

But back to the talks. We didn’t make videos, but here are the slides. Click on talk titles to see abstracts of the talks. For a multi-author talk, the person whose name is in boldface is the one who gave the talk. You also might enjoy comparing the 2017 talks.

Saturday November 9, 2019

8:00 a.m.
Fibrations as generalized lens categoriestalk slides.
David I. Spivak, Massachusetts Institute of Technology

9:00 a.m.
Supplying bells and whistles in symmetric monoidal categoriestalk slides.
Brendan Fong, Massachusetts Institute of Technology
David I. Spivak, Massachusetts Institute of Technology

9:30 a.m.
Philip Hackney, University of Louisiana at Lafayette
Gabriel C. Drummond-Cole, IBS Center for Geometry and Physics

10:00 a.m.
Duality of relationstalk slides.
Alexander Kurz, Chapman University

10:30 a.m.
A synthetic approach to stochastic maps, conditional independence, and theorems on sufficient statisticstalk slides.
Tobias Fritz, Perimeter Institute for Theoretical Physics

3:00 p.m.
Constructing symmetric monoidal bicategories functoriallytalk slides.
Michael Shulman, University of San Diego
Linde Wester Hansen, University of Oxford

3:30 p.m.
Structured cospanstalk slides.
Kenny Courser, University of California, Riverside
John C. Baez, University of California, Riverside

4:00 p.m.
Generalized Petri netstalk slides.
Jade Master, University of California, Riverside

4:30 p.m.
Formal composition of hybrid systemstalk slides and website.

Paul Gustafson, Wright State University
Jared Culbertson, Air Force Research Laboratory
Dan Koditschek, University of Pennsylvania
Peter Stiller, Texas A&M University

5:00 p.m.
Strings for cartesian bicategoriestalk slides.
M. Andrew Moshier, Chapman University

5:30 p.m.
Defining and programming generic compositions in symmetric monoidal categoriestalk slides.
Dmitry Vagner, Los Angeles, CA

Sunday November 10, 2019

8:00 a.m.
Mathematics for second quantum revolutiontalk slides.
Zhenghan Wang, UCSB and Microsoft Station Q

9:00 a.m.
A compositional and statistical approach to natural languagetalk slides.

9:30 a.m.
Exploring invariant structure in neural activity with applied topology and category theorytalk slides.
Krista Perks, UC San Diego
Timothy Q Gentner, UC San Diego

10:00 a.m.
Of monks, lawyers and villages: new insights in social network science — talk cancelled due to illness.
Nina Otter, Mathematics Department, UCLA
Mason A. Porter, Mathematics Department, UCLA

10:30 a.m.
Functorial cluster embeddingtalk slides.

Steve Huntsman, BAE Systems FAST Labs

2:00 p.m.
Quantitative equational logictalk slides.
Prakash Panangaden, School of Computer Science, McGill University
Gordon D. Plotkin, University of Edinburgh

3:00 p.m.
Brakes: an example of applied category theorytalk slides in PDF and Powerpoint.
Eswaran Subrahmanian, Carnegie Mellon University / National Institute of Standards and Technology

3:30 p.m.
Intuitive robotic programming using string diagramstalk slides.
Blake S. Pollard, National Institute of Standards and Technology

4:00 p.m.
Metrics on functor categoriestalk slides.
Vin de Silva, Department of Mathematics, Pomona College

4:30 p.m.
Hausdorff and Wasserstein metrics on graphs and other structured datatalk slides.
Evan Patterson, Stanford University

Quantales from Petri Nets

6 October, 2019

A referee pointed out this paper to me:

• Uffe Engberg and Glynn Winskel, Petri nets as models of linear logic, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1990, pp. 147–161.

It contains a nice observation: we can get a commutative quantale from any Petri net.

I’ll explain how in a minute. But first, what does have to do with linear logic?

In linear logic, propositions form a category where the morphisms are proofs and we have two kinds of ‘and’: $\&$, which is a cartesian product on this category, and $\otimes$, which is a symmetric monoidal structure. There’s much more to linear logic than this (since there are other connectives), and maybe also less (since we may want our category to be a mere poset), but never mind. I want to focus on the weird business of having two kinds of ‘and’.

Since $\&$ is cartesian we have $P \Rightarrow P \& P$ as usual in logic.

But since $\otimes$ is not cartesian we usually don’t have $P \Rightarrow P \otimes P.$ This other kind of ‘and’ is about resources: from one copy of a thing $P$ you can’t get two copies.

Here’s one way to think about it: if $P$ is “I have a sandwich”, $P \& P$ is like “I have a sandwich and I have a sandwich”, while $P \otimes P$ is like “I have two sandwiches”.

A commutative quantale captures these two forms of ‘and’, and more. A commutative quantale is a commutative monoid object in the category of cocomplete posets: that is, posets where every subset has a least upper bound. But it’s a fact that any cocomplete poset is also complete: every subset has a greatest lower bound!

If we think of the elements of our commutative quantale as propositions, we interpret $x \le y$ as “$x$ implies $y$”. The least upper bound of any subset of proposition is their ‘or’. Their greatest lower bound is their ‘and’. But we also have the commutative monoid operation, which we call $\otimes.$ This operation distributes over least upper bounds.

So, a commutative quantale has both the logical $\&$ (not just for pairs of propositions, but arbitrary sets of them) and the $\otimes$ operation that describes combining resources.

To get from a Petri net to a commutative quantale, we can compose three functors.

First, any Petri net gives a commutative monoidal category—that is, a commutative monoid object in $\mathsf{Cat}$. Indeed, my student Jade has analyzed this in detail and shown the resulting functor from the category of Petri nets to the category of commutative monoidal categories is a left adjoint:

• Jade Master, Generalized Petri nets, Section 4.

Second, any category gives a poset where we say $x \le y$ if there is a morphism from $x$ to $y.$ Moreover, the resulting functor $\mathsf{Cat} \to \mathsf{Poset}$ preserves products. As a result, every commutative monoidal category gives a commutative monoidal poset: that is, a commutative monoid object in the category of Posets.

Composing these two functors, every Petri net gives a commutative monoidal poset. Elements are of this poset are markings of the Petri net, the partial order is “reachability”, and the commutative monoid structure is addition markings.

Third, any poset $P$ gives another poset $\widehat{P}$ whose elements are downsets of $P$: that is, subsets $S \subseteq P$ such that

$x \in S, y \le x \; \implies \; y \in S$

The partial order on downsets is inclusion. This new poset $\widehat{P}$ is ‘better’ than $P$ because it’s cocomplete. That is, any union of downsets is again a downset. Moreover, $\widehat{P}$ contains $P$ as a sub-poset. The reason is that each $x \in P$ gives a downset

$\downarrow x = \{y \in P : \; y \le x \}$

and clearly

$x \le y \; \iff \; \downarrow x \subseteq \downarrow y$

Composing this third functor with the previous two, every Petri net gives a commutative monoid object in the category of cocomplete posets. But this is just a commutative quantale!

What is this commutative quantale like? Its elements are downsets of markings of our Petri net: sets of markings such that if $x$ is in the set and $x$ is reachable from $y$ then $y$ is also in the set.

It’s good to contemplate this a bit more. A marking can be seen as a ‘resource’. For example, if our Petri net has a place in it called sandwich there is a marking 2sandwich, which means you have two sandwiches. Downsets of markings are sets of markings such that if $x$ is in the set and $x$ is reachable from $y$ then $y$ is also in the set! An example of a downset would be “a sandwich, or anything that can give you a sandwich”. Another is “two sandwiches, or anything that can give you two sandwiches”.

The tensor product $\otimes$ comes from addition of markings, extended in the obvious way to downsets of markings. For example, “a sandwich, or anything that can give you a sandwich” tensored with “a sandwich, or anything that can give you a sandwich” equals “two sandwiches, or anything that can give you two sandwiches”.

On the other hand, the cartesian product $\&$ is the logical ‘and’:
if you have “a sandwich, or anything that can give you a sandwich” and you have “a sandwich, or anything that can give you a sandwich”, then you just have “a sandwich, or anything that can give you a sandwich”.

So that’s the basic idea.

Applied Category Theory Meeting at UCR (Part 2)

30 September, 2019

Joe Moeller and I have finalized the schedule of our meeting on applied category theory:

Applied Category Theory, special session of the Fall Western Sectional Meeting of the AMS, U. C. Riverside, Riverside, California, 9–10 November 2019.

It’s going to be really cool, with talks on everything from brakes to bicategories, from quantum physics to social networks, and more—with the power of category theory as the unifying theme!

You can get information on registration, hotels and such here. If you’re coming, you might also want to attend Eugenia Cheng‘s talk on the afternoon of Friday November 8th.   I’ll announce the precise title and time of her talk, and also the location of all the following talks, as soon as I know!

In what follows, the person actually giving the talk has an asterisk by their name. You can click on talk titles to see abstracts of the talks.

Saturday November 9, 2019, 8:00 a.m.-10:50 a.m.

• 8:00 a.m.David I. Spivak*, Massachusetts Institute of Technology
• 9:00 a.m.Brendan Fong*, Massachusetts Institute of Technology
David I. Spivak, Massachusetts Institute of Technology
• 9:30 a.m.Gabriel C. Drummond-Cole, IBS Center for Geometry and Physics
Philip Hackney*, Department of Mathematics, University of Louisiana at Lafayette
• 10:00 a.m.
Duality of relations.
Alexander Kurz*, Chapman University
• 10:30 a.m.Tobias Fritz*, Perimeter Institute for Theoretical Physics

Saturday November 9, 2019, 3:00 p.m.-5:50 p.m.

Sunday November 10, 2019, 8:00 a.m.-10:50 a.m.

Sunday November 10, 2019, 2:00 p.m.-4:50 p.m.