Foundations of Math and Physics One Century After Hilbert

10 October, 2019

I wrote a review of this book with chapters by Penrose, Witten, Connes, Atiyah, Smolin and others:

• John Baez, review of Foundations of Mathematics and Physics One Century After Hilbert: New Perspectives, edited by Joseph Kouneiher, Notices of the American Mathematical Society 66 no. 11 (November 2019), 1690–1692.

It gave me a chance to say a bit—just a tiny bit—about the current state of fundamental physics and the foundations of mathematics.

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.

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.

The Binary Octahedral Group

29 August, 2019

The complex numbers together with infinity form a sphere called
the Riemann sphere. The 6 simplest numbers on this sphere lie at points we could call the north pole, the south pole, the east pole, the west pole, the front pole and the back pole. They’re the corners of an octahedron!

On the Earth, I’d say the “front pole” is where the prime meridian meets the equator at 0°N 0°E. It’s called Null Island, but there’s no island there—just a buoy. Here it is:

Where’s the back pole, the east pole and the west pole? I’ll leave two of these as puzzles, but I discovered that in Singapore I’m fairly close to the east pole:

If you think of the octahedron’s corners as the quaternions \pm i, \pm j, \pm k, you can look for unit quaternions q such that whenever x is one of these corners, so is qxq^{-1}. There are 48 of these! They form a group called the binary octahedral group.

By how we set it up, the binary octahedral group acts as rotational symmetries of the octahedron: any transformation sending x to qxq^{-1} is a rotation. But this group is a double cover of the octahedron’s rotational symmetry group! That is, pairs of elements of the binary octahedral group describe the same rotation of the octahedron.

If we go back and think of the Earth’s 6 poles as points 0, \pm 1,\pm i, \infty on the Riemann sphere instead of \pm i, \pm j, \pm k, we can think of the binary octahedral group as a subgroup of \mathrm{SL}(2,\mathbb{C}), since this acts as conformal transformations of the Riemann sphere!

If we do this, the binary octahedral group is actually a subgroup of \mathrm{SU}(2), the double cover of the rotation group—which is isomorphic to the group of unit quaternions. So it all hangs together.

It’s fun to actualy see the unit quaternions in the binary octahedral group. First we have 8 that form the corners of a cross-polytope (the 4d analogue of an octahedron):

\pm 1, \pm i , \pm j , \pm k

These form a group on their own, called the quaternion group. Then we have 16 that form the corners of a hypercube (the 4d analogue of a cube, also called a tesseract or 4-cube):

\displaystyle{ \frac{\pm 1 \pm i \pm j \pm k}{2} }

These don’t form a group, but if we take them together with the 8 previous ones we get a 24-element subgroup of the unit quaternions called the binary tetrahedral group. They’re also the vertices of a 24-cell, which is yet another highly symmetrical shape in 4 dimensions (a 4-dimensional regular polytope that doesn’t have a 3d analogue).

That accounts for half the quaternions in the binary octahedral group! Here are the other 24:

\displaystyle{  \frac{\pm 1 \pm i}{\sqrt{2}}, \frac{\pm 1 \pm j}{\sqrt{2}}, \frac{\pm 1 \pm k}{\sqrt{2}},  }

\displaystyle{  \frac{\pm i \pm j}{\sqrt{2}}, \frac{\pm j \pm k}{\sqrt{2}}, \frac{\pm k \pm i}{\sqrt{2}} }

These form the vertices of another 24-cell!

The first 24 quaternions, those in the binary tetrahedral group, give rotations that preserve each one of the two tetrahedra that you can fit around an octahedron like this:

while the second 24 switch these tetrahedra.

The 6 elements

\pm i , \pm j , \pm k

describe 180° rotations around the octahedron’s 3 axes, the 16 elements

\displaystyle{   \frac{\pm 1 \pm i \pm j \pm k}{2} }

describe 120° clockwise rotations of the octahedron’s 8 triangles, the 12 elements

\displaystyle{  \frac{\pm 1 \pm i}{\sqrt{2}}, \frac{\pm 1 \pm j}{\sqrt{2}}, \frac{\pm 1 \pm k}{\sqrt{2}} }

describe 90° clockwise rotations holding fixed one of the octahedron’s 6 vertices, and the 12 elements

\displaystyle{  \frac{\pm i \pm j}{\sqrt{2}}, \frac{\pm j \pm k}{\sqrt{2}}, \frac{\pm k \pm i}{\sqrt{2}} }

describe 180° clockwise rotations of the octahedron’s 6 opposite pairs of edges.

Finally, the two elements

\pm 1

do nothing!

So, we can have a lot of fun with the idea that a sphere has 6 poles.

2020 Category Theory Conferences

9 August, 2019


Yes, my last post was about ACT2019, but we’re already planning next year’s applied category theory conference and school! I’m happy to say that Brendan Fong and David Spivak have volunteered to run it at MIT on these dates:

• Applied Category Theory School: June 29–July 3, 2020.
• Applied Category Theory Conference: July 6–10, 2020.

The precise dates for the other big category theory conference, CT2020, have not yet been decided. However, it will take place in Genoa sometime in the interval June 18–28, 2020.

There may also be an additional applied theory school in Marrakesh from May 25–29, 2020. More on that later, with any luck!

And don’t forget to submit your abstracts for the November 2019 applied category theory special session at U. C. Riverside by September 3rd! We’ve got a great lineup of speakers, but anyone who wants to give a talk—including the invited speakers—needs to submit an abstract to the AMS website by September 3rd. The AMS has no mercy about this.

Applied Category Theory 2019 Talks

20 July, 2019

Applied Category Theory 2019 happened last week! It was very exciting: about 120 people attended, and they’re pushing forward to apply category theory in many different directions. The topics ranged from ultra-abstract to ultra-concrete, sometimes in the same talk.

The talks are listed above — click for a more readable version. Below you can read what Jules Hedges and I wrote about all those talks:

• Jules Hedges, Applied Category Theory 2019.

I tend to give terse summaries of the talks, with links to the original papers or slides. Jules tends to give his impressions of their overall significance. They’re nicely complementary.

You can also see videos of some talks, created by Jelle Herold with help from Fabrizio Genovese:

• Giovanni de Felice, Functorial question answering.

• Antonin Delpeuch, Autonomization of monoidal categories.

• Colin Zwanziger, Natural model semantics for comonadic and adjoint modal type theory.

• Nicholas Behr, Tracelets and tracelet analysis Of compositional rewriting systems.

• Dan Marsden, No-go theorems for distributive laws.

• Christian Williams, Enriched Lawvere theories for operational semantics.

• Walter Tholen, Approximate composition.

• Erwan Beurier, Interfacing biology, category theory & mathematical statistics.

• Stelios Tsampas, Categorical contextual reasoning.

• Fabrizio Genovese, idris-ct: A library to do category theory in Idris.

• Michael Johnson, Machine learning and bidirectional transformations.

• Bruno Gavranović, Learning functors using gradient descent

• Zinovy Diskin, Supervised learning as change propagation with delta lenses.

• Bryce Clarke, Internal lenses as functors and cofunctors.

• Ryan Wisnewsky, Conexus AI.

• Ross Duncan, Cambridge Quantum Computing.

• Beurier Erwan, Memoryless systems generate the class of all discrete systems.

• Blake Pollard, Compositional models for power systems.

• Martti Karvonen, A comonadic view of simulation and quantum resources.

• Quanlong Wang, ZX-Rules for 2-qubit Clifford+T quantum circuits, and beyond.

• James Fairbank, A Compositional framework for scientific model augmentation.

• Titoan Carette, Completeness of graphical languages for mixed state quantum mechanics.

• Antonin Delpeuch, A complete language for faceted dataflow languages.

• John van der Wetering, An effect-theoretic reconstruction of quantum mechanics.

• Vladimir Zamdzhiev, Inductive datatypes for quantum programming.

• Octavio Malherbe, A categorical construction for the computational definition of vector spaces.

• Vladimir Zamdzhiev, Mixed linear and non-linear recursive types.

Applied Category Theory 2019 Program

3 July, 2019

Bob Coecke, David Spivak, Christina Vasilakopoulou and I are running a conference on applied category theory:

Applied Category Theory 2019, 15–19 July, 2019, Lecture Theatre B of the Department of Computer Science, 10 Keble Road, Oxford.

You can now see the program here, or below. Hope to see you soon!