Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: community: our work

Topic: Chad Nester

Chad Nester (Feb 11 2024 at 16:09):

Hello everyone,

I've got a few new papers to advertise.

First, Protocol Choice and Iteration for the Free Cornering, together with @Niels Voorneveld. This extends the free cornering of a monoidal category to support additional protocol types, in particular branching protocols, in which one of the participants chooses which of two continuations will happen and the other must respond, and iterated protocols, in which the participants repeat all or part of a protocol some number of times, based on choices made during the process. If you have access to JLAMP you can get the "official" version, but frankly I think the preprint is more legible.

Chad Nester (Feb 11 2024 at 16:12):

Second, my PhD thesis, Partial and Relational Algebraic Theories has been successfully defended and is available from the university library. The thesis is a more careful development of the partial algebraic theories and relational algebraic theories from my published work.

I'll mention that only the first ~150 pages of the document on that website are the thesis monograph, with the rest being copies of my papers. It isn't that scary!

Evan Patterson (Feb 11 2024 at 20:04):

Congrats on the nice looking thesis! You should post it to arXiv (minus the copied papers). That will help people find it.

Matteo Capucci (he/him) (Feb 12 2024 at 07:58):

Congrats!

Chad Nester (Feb 12 2024 at 10:13):

Evan Patterson said:

Congrats on the nice looking thesis! You should post it to arXiv (minus the copied papers). That will help people find it.

I don't know whether or not I should do this. I'm planning to publish journal version of the two associated conference papers at some point using material from the thesis, so it might be better to wait. I don't really know.

Kevin Arlin (Feb 12 2024 at 21:20):

What downside are you envisioning?

Mike Shulman (Feb 12 2024 at 21:32):

I don't know what Chad is thinking, but my own thesis is put together from several papers, and I never put my thesis itself on the arXiv because I would rather that people read the papers instead, as they are more polished. However, this only works if the individual papers actually do get written.

Chad Nester (Apr 17 2024 at 15:31):

Tomorrow at 14:00 EEST (UTC+3) I'm giving a talk in Tallinn titled Elgot Categories and Abacus Programs. The talk will be broadcast via Zoom, and if you're interested in listening in send me a message here and I'll send you the details.

Abstract:
This talk concerns the categorical representation of the partial
recursive functions. Specifically, I will introduce Elgot
categories, which are a sort of structured rig category in which
all partial recursive functions are representable. Specifically, an
Elgot category is a (uniform) traced cocartesian rig category
with a distinguished isomorphism I+N→N for some object N.

I will construct an initial Elgot category, the morphisms of
which will coincide with the abacus programs of Lambek. Finally,
I will show that in this initial Elgot category, the class of
strongly representable partial functions is precisely the class
of partial recursive functions.

Chad Nester (Apr 17 2024 at 15:34):

I guess the main references are:

• Partial Recursive Functions and Finality by Plotkin.
• Deconstructing the Calculus of Relations with Tape Diagrams by Bonchi, Di Giorgio, and Santamaria.

Chad Nester (May 13 2024 at 13:18):

Today is my first day at my new job as a Research Fellow at the University of Tartu. It's a permanent position, which is exciting.

Chad Nester (May 24 2024 at 09:35):

Mike Shulman said:

I don't know what Chad is thinking, but my own thesis is put together from several papers, and I never put my thesis itself on the arXiv because I would rather that people read the papers instead, as they are more polished. However, this only works if the individual papers actually do get written.

I do eventually hope to publish the results from my MSc thesis :sweat_smile:

Chad Nester (May 24 2024 at 09:41):

In other news, I'll be attending a few conferences this summer:

• ACT/MFPS in Oxford, June 17-21. Here I'll give a talk about my thesis work on "Partial and Relational Algebraic Theories".
• CT in Santiago de Compostela, June 23-39.
• FSCD in Tallinn, July 10-13.

If you'll be at one or more of these and would like to talk about something specific, let me know and I can prepare a bit in advance :)

Chad Nester (Jul 02 2024 at 11:16):

On Monday, July 8th at 14:30 in Tallinn I'll be speaking at MSFP 2024 about my paper "Protocol Choice and Iteration for the Free Cornering" with Niels Voorneveld.

Chad Nester (Mar 28 2025 at 12:34):

I've put up a new thing on the arXiv: https://arxiv.org/pdf/2503.21434

It's about representing the partial recursive functions in distributive monoidal categories. The short version is that you need to be traced on the coproduct, and to have an isomorphism $I+N \to N$ hanging around somewhere. I think it's fun.

Chad Nester (Sep 17 2025 at 14:42):

I'd like to ponder something out loud here:

Let $\mathsf{List}(A)$ be the set of lists with elements in $A$, defined as usual to be the initial algebra of the endofunctor $X \mapsto 1 + (A \times X)$ on $\mathsf{Set}$. In particular let's write the initial algebra as $\langle \mathsf{nil} \mid \mathsf{cons} \rangle : 1 + (A \times \mathsf{List}(A)) \to \mathsf{List}(A)$, so that out lists look like the ones from functional programming.

Let $W$ be a set, and suppose that we have partial functions $\mathsf{push} : A \times W \to W$ and $\mathsf{pop} = \langle \mathsf{head},\mathsf{tail} \rangle : W \to A \times W$ such that $\mathsf{push};\mathsf{pop} = 1_{A \times W}$. Note as an aside that an immediate consequence of this equation is that $\mathsf{push}$ is total.

There is a total function $h : W \to \mathsf{List}(A)$ defined by $h(x) = \begin{cases} \mathsf{nil} & \text{ if } \mathsf{pop}(x)\uparrow \\ \mathsf{cons}(\mathsf{head}(x),h(\mathsf{tail}(x))) & \text{ otherwise}\end{cases}$

So for each $x \in W$ we have a list, $h(x)$. We do not, however, seem to be able to construct an element of $W$ for each element of $\mathsf{List}(A)$. In particular, it is unclear what we would map $\mathsf{nil}$ to.

Nonetheless, I can do quite a few list-like things with $W$. So long as I'm happy to have my function become undefined the moment it attempts to inspect an "empty" element of $W$ (on which $\mathsf{pop}$ is undefined), there would seem to be nothing I cannot do.

Chad Nester (Sep 17 2025 at 14:45):

Ah: a problem with this is that $\mathsf{pop}$ may in fact be total, in which case $W$ is a stream and my $h$ isn't well-defined, since I never reach a $\mathsf{nil}$.

Chad Nester (Sep 17 2025 at 14:58):

I guess I have the same thing happening, but with $\mathsf{CoList}(A)$ instead of $\mathsf{List}(A)$. Here by $\mathsf{CoList}(A)$ I mean the terminal coalgebra of the endofunctor $X \mapsto 1 + (A \times X)$. So a colist is a "possibly finite stream" or equivalently a "possibly infinite list".

Chad Nester (Sep 17 2025 at 15:10):

I would imagine that $h : W \to \mathsf{CoList}(A)$ is injective, but not surjective. I think I probably need to work out some examples if I want to understand this...

Mike Shulman (Sep 17 2025 at 15:12):

I presume you meant your $h$ to be recursive on tail in the otherwise case.

Chad Nester (Sep 17 2025 at 15:12):

Yes, thank you. I've fixed it.

Mike Shulman (Sep 17 2025 at 15:13):

Of course, a partial function $\mathsf{pop} : W \to A\times W$ is the same as a total function $W \to 1 + (A \times W)$, so then your $h$ is exactly the unique map from a coalgebra to a terminal coalgebra.

Mike Shulman (Sep 17 2025 at 15:15):

In general that won't be injective or surjection, and I don't see see why the additional presence of push would make it injective.

Chad Nester (Sep 17 2025 at 15:17):

Hmm, we do know that $\mathsf{push}$ is injective because it is a section... which doesn't really seem to help here.

Chad Nester (Sep 17 2025 at 15:22):

Right: if $\mathsf{pop}$ is undefined on two distinct elements of $W$ then $h$ is not an injection.

Chad Nester (Sep 17 2025 at 15:48):

I think this might be a good way to talk about what's going on in Lisp with car/cdr and "improper lists"

Chad Nester (Nov 24 2025 at 11:37):

A new preprint today: Combinatory Completeness in Structured Multicategories

If you like combinatory logic and know what a multicategory is, you might like it.

I'll copy the abstract here:
We give a general notion of combinatory completeness with respect to a faithful cartesian club and use it systematically to obtain characterisations of a number of different kinds of applicative system. Each faithful cartesian club determines a notion of structured multicategory, with the different notions of structured multicategory obtained in this way giving different notions of polynomial over an applicative system, which in turn give different notions of combinatory completeness. We obtain the classical characterisation of combinatory algebras as combinatory complete applicative systems as a specific instance.

fosco (Nov 24 2025 at 16:22):

I already asked Ülo this question but maybe you have something to add: a $\mathfrak S$-multicategory is just:tm: a multicategory with an action of the club, which is also a monoid, in a sense: is that correct?

Chad Nester (Nov 25 2025 at 07:19):

In a sense, sure. I don't know which sense.

Chad Nester (Nov 25 2025 at 07:26):

I'd like to better understand the more general notion of "club".

James Deikun (Nov 25 2025 at 07:44):

Thanks for introducing me to Shulman's notion of $\mathfrak S$-multicategory; it's providing valuable hints for me.

fosco (Nov 25 2025 at 08:04):

Chad Nester said:

I'd like to better understand the more general notion of "club".

What I know, I learned it from @Todd Trimble, I would just produce a pale imitation. But the original paper "clubs and doctrines" is not too obscure, as far as I could read it!

Mike Shulman (Nov 25 2025 at 18:18):

A general club is itself a kind of generalized multicategory, namely a Burroni-Leinster span-based generalized multicategory relative to a cartesian monad $T$ on Cat. What I called a "faithful cartesian club" is a club where $T$ is the monad for cartesian strict monoidal categories and the map from the club to $T$ is faithful. Such a club presents another cartesian monad on Cat, which usually (?) extends to Prof, and what I called an $\mathfrak{S}$-multicategory is a generalized multicategory for this monad on Prof.

Chad Nester (Nov 26 2025 at 09:28):

I see. That's very helpful. I had been wondering about how it all fit together.

James Deikun (Nov 29 2025 at 22:16):

What exactly does it mean to say "the map from the club to $T$ is faithful"? Is it that the natural transformation from the club-induced monad to $T$ is componentwise faithful?

Mike Shulman (Dec 01 2025 at 16:17):

Yes. But that's equivalent to the single functor $M1 \to T1$ being faithful, since the natural transformation $M\to T$ is cartesian, and the category $M1$ over $T1$ with its induced structure is what's generally referred to as the club itself.

Chad Nester (Feb 12 2026 at 16:41):

An update: our work on Combinatory Completeness for in Structured Multicategories has been accepted for publication in the proceedings of RAMICS 2026. There were a few non-examples in the original preprint, and the new version (now on arXiv) is improved in other ways as well.

Chad Nester (Feb 12 2026 at 16:42):

Also, if you have nothing to do for the next hour or so, I'll be giving an online talk about it at the Topos Institute Colloquium in about 15 minutes.

Mike Shulman (Feb 12 2026 at 17:58):

Nice work, and nice talk! It makes me happy to see the notion of faithful cartesian club used for this sort of thing, because it's exactly the sort of reason that I wrote down that definition in the first place: it seemed to be the level of generality for generalized multicategories that corresponded most naturally to "syntax". The next time I revise my catlog notes I will certainly be including a reference to your work.

Chad Nester (Feb 12 2026 at 18:08):

Thanks!

Chad Nester (Mar 20 2026 at 04:07):

A few more pre-prints of conference submissions today.

First, Monoidal Categories Graded by Partial Commutative Monoids, with Matt Earnshaw and Mario Roman.

The idea is to capture monoidal-category-like structures in which the tensor product is not always defined by assigning morphisms a grade drawn from some partial commutative monoid. The tensor product of two morphisms is defined in case the partial monoid operation is defined on their grades. Grading in the right partial monoid recovers the notion of e.g., effectful categories.

For zulip I'll highlight the fact that if $E$ is an effect algebra then we recover an effectful category from any $E$-graded monoidal category, in a small victory for nominative determinism.

Chad Nester (Mar 20 2026 at 04:16):

Second, A Simple Categorical Calculus of Interacting Processes, with Niels Voorneveld.

After a number of failed attempts, we've come up with a term rewriting system that presents something close to the free cornering of a monoidal category. We start with a multicategory, whose morphisms we think of as non-interacting processes, and build a simple message-passing calculus out of it. In particular, terms of the calculus modulo the convertibility relation form a virtual double category. We construct a functor relating all this to the free cornering construction.

I'm quite pleased with this. There are a lot of places we'd like to take this, and it feels like we're finally starting to get somewhere.

John Onstead (Mar 24 2026 at 06:25):

Chad Nester said:

First, Monoidal Categories Graded by Partial Commutative Monoids, with Matt Earnshaw and Mario Roman.

I just finished reading through this paper, and I wanted to post one of my thoughts on it in case someone else had a similar thought! Hope that's ok to do here.

John Onstead (Mar 24 2026 at 06:25):

At the end of the paper, a monoidal category $V(E, M)$ is constructed such that a monoid in this monoidal category is precisely a $E$-graded monoidal category with an underlying monoid of objects $M$. This made me wonder if instead we could construct a $V(E)$ such that a monoid in this monoidal category is precisely an $E$-graded monoidal category with any underlying monoid of objects. I think such a category would be helpful to have, since then we can define a notion of delooping of an $E$-graded monoidal category to be a one object $V(E)$-enriched category. In addition, there's hope that if $E$ is the singleton (so than an $E$-graded monoidal category is exactly a usual monoidal category), then we have some sort of equivalence $V(E) \cong \mathrm{Cat}$ that allows us to reduce this construction down to the usual case of "a monoidal category is a monoid in Cat".

I thought about this for a bit, but came up short on how it might be done. My first attempt was to just take a coproduct in $\mathrm{MonCat}$ or monoidal fibration (grothendieck fibration in the monoidal category world) of $V(E, M)$ for each $M$, but any such process would necessarily add in new objects for every pair of objects living in different $V(E, M)$. This probably adds in so much extra "stuff" that we could no longer conclude a direct correspondence between monoids in the resulting category and $E$-graded monoidal categories!

John Baez (Mar 24 2026 at 06:52):

What's $E$, an arbitrary monoid? If so, there is definitely a monoidal category such that monoids in there are $E$-graded monoids. It's the category of $E$-graded sets, i.e. sets over $E$, with a certain monoidal structure such that the tensor product of $S \to E$ and $S' \to E$ is $S \times S' \to E \times E \stackrel{m}{\longrightarrow} E$, where $m$ is the multiplication in $E$.

fosco (Mar 24 2026 at 10:01):

...and that "certain monoidal structure" is [[Day convolution]], when $Set/E$ is identified with the functor category $[E,Set]$ (which is not the monoid $E$ regarded as a category with a single object, but instead the monoid $E$ regarded as a monoidal 0-category).

fosco (Mar 24 2026 at 10:01):

(added just for the sake of completeness)

Chad Nester (Mar 25 2026 at 00:46):

$E$ is an arbitrary partial commutative monoid. I'm going to ping @Matt Earnshaw, since I think he's probably the best person to talk to about these things.

John Onstead (Mar 25 2026 at 05:36):

John Baez said:

It's the category of $E$-graded sets, i.e. sets over $E$, with a certain monoidal structure such that the tensor product of $S \to E$ and $S' \to E$ is $S \times S' \to E \times E \stackrel{m}{\longrightarrow} E$, where $m$ is the multiplication in $E$.

fosco said:

...and that "certain monoidal structure" is [[Day convolution]], when $Set/E$ is identified with the functor category $[E,Set]$ (which is not the monoid $E$ regarded as a category with a single object, but instead the monoid $E$ regarded as a monoidal 0-category).

Ah, that's quite interesting! Thanks for the help.

fosco (Mar 25 2026 at 06:33):

(I do not know how to phrase something similar for a PCM, and I do not remember Matt mentioning whether this is possible when he talked about this paper, so don't misunderstand my comment as a way of saying that it can be done)

fosco (Mar 25 2026 at 06:33):

I like the result though!

Matt Earnshaw (Mar 25 2026 at 10:10):

John Onstead said:

I thought about this for a bit, but came up short on how it might be done. My first attempt was to just take a coproduct in $\mathrm{MonCat}$ or monoidal fibration (grothendieck fibration in the monoidal category world) of $V(E, M)$ for each $M$, but any such process would necessarily add in new objects for every pair of objects living in different $V(E, M)$. This probably adds in so much extra "stuff" that we could no longer conclude a direct correspondence between monoids in the resulting category and $E$-graded monoidal categories!

I think one has to play a different game here, namely to assemble these monoidal categories into the (endo)homs of a bicategory, and talk of monads there. Just as (enriched) categories are monads in $\mathcal{V}\text{-}\mathsf{Mat}$, the data of a lax monoidal functor $\mathbb{C}^{\text{op}}_{\text{obj}} \times \mathbb{C}_{\text{obj}} \to [E,\mathsf{Set}]$ is akin to a $[E,\mathsf{Set}]$-matrix. (In fact, it's precisely a monoid in $\mathbb{C}_{\text{obj}}$ indexed matrices, in the sense of nlab, Proposition 4.3, so the construction in the paper can be unravelled further, and you get a "free E-graded monoidal category" construction for free, starting from a bare "matrix" or "signature", and taking free monoids twice, with respect to two different monoidal structures).

See also Remark 6.7: if you switch the operations under which grades combine, then you can again talk about monoids rather than monads. I think there's more to be said about the connection between these, but I'm not totally sure yet what it is.

John Onstead (Mar 25 2026 at 19:07):

Matt Earnshaw said:

I think one has to play a different game here, namely to assemble these monoidal categories into the (endo)homs of a bicategory, and talk of monads there. Just as (enriched) categories are monads in $\mathcal{V}\text{-}\mathsf{Mat}$, the data of a lax monoidal functor $\mathbb{C}^{\text{op}}_{\text{obj}} \times \mathbb{C}_{\text{obj}} \to [E,\mathsf{Set}]$ is akin to a $[E,\mathsf{Set}]$-matrix.

Ok, I think I understand- we should have a bicategory where there's an object for every monoid, a monad over that monoid is a $V(E, M)$ monoidal category, so that all $E$-graded monoidal categories are given as some monad over some object in this bicategory.

John Onstead (Mar 25 2026 at 19:07):

I don't want to speculate too much, but this seems very similar to the idea of an indexed enriched category for a monoidal fibration. Given any indexed monoidal category $F: C^{op} \to \mathrm{MonCat}$, I think you can form a (virtual) double category $\mathrm{Mat}(F)$ whose objects are those of $C$ and the loose arrows from $X$ to $Y$ are objects in $F(X \times Y)$. For instance, define a indexed monoidal category $F: \mathrm{Mon}^{op} \to \mathrm{MonCat}$ such that $F(M) = \mathrm{LaxMon}[M, [E, \mathrm{Set}]]$. Then an endo-loose arrow for $\mathrm{Mat}(F)$ on $M$ would be the same thing as a lax monoidal functor $M \times M \to [E, \mathrm{Set}]$. If $F$ really does define a valid functor and monoidal fibration, perhaps then $\mathrm{Mat}(F)$ might be similar to the entity where monads would be $E$-graded monoidal categories.